Let $\{ {\bf v}_1,{\bf v}_2 \}$ be two linearly independent vectors. An orthogonal base $\{{\bf u}_1,{\bf u}_2 \}$ of the vector space $\mathrm{span}\{ {\bf v}_1,{\bf v}_2 \}$ can be computed using Gram-Schmidt Orthogonalization process (GSO) which is summarized by the formulas $${\bf u}_1={\bf v}_1 \quad\text{and}\quad {\bf u}_2={\bf v}_2-\mu_{2,1}{\bf u}_1 \quad\text{where}\quad\mu_{2,1}=\frac{{\bf v}_2 \cdot {\bf u}_1}{||{\bf u}_1||^2}$$ Geometrically it is given as

enter image description here

In order to get ${\bf u}_2$ i.e., orthogonal to ${\bf u}_1$ project ${\bf v}_2$ onto ${\bf u}_1$ and the length of the projection on ${\bf u}_1$ is given by $\frac{|{\bf v}_2 \cdot {\bf u}_1|}{||{\bf u}_1||}$ and to get the direction we multiply the length by the unit vector $\frac{{\bf u}_1}{||{\bf u}_1||}$ and the $\mathrm{proj}_{{\bf u}_1} {\bf v}_2= \frac{{\bf v}_2 \cdot {\bf u}_1}{||{\bf u}_1||}\times \frac{{\bf u}_1}{||{\bf u}_1||},$ where the length of the projection is $\frac{|{\bf v}_2 \cdot {\bf u}_1|}{||{\bf u}_1||}$. In GSO process $\mu_{2,1}=\frac{\text{length of the projection of \(v_2\) on \(u_1\)}}{||{\bf u}_1||}$ what does $\mu_{2,1}$ represent geometrically?

If $\{ {\bf v}_1,{\bf v}_2 \}$ is the basis of the lattice to solve the shortest vector problem, our aim is to find the orthogonal basis. But orthogonal vectors computed using GSO need not be a basis because $\mu_{2,1}$ need not be an integer.

Since SVP is a hard problem, the LLL algorithm solves approximate SVP. In defining an LLL reduced basis the first requirement is $\mu_{2,1} \le \frac{1}{2}$ (size reduction condition). What does this imply?

up vote 1 down vote accepted

Say you have an integer lattice $\mathcal{L}$ with (ordered) basis $B=\{{\bf b}_1,\ldots,{\bf b}_n \},$ ${\bf b}_j\in {\bf Z}^m$, $n\leq m$. As you wrote the first condition of the LLL reduced basis $\{ {\bf u}_1,\ldots,{\bf u}_n\}$ is the process of size reduction. That is $|\mu_{i,j}|\leq \frac{1}{2}$, $j<i$. If you set $M_i=\mathrm{span}({\bf b}_1,\ldots,{\bf b}_i),\ i<n$ then this condition shortens the projection $\mathrm{proj}_{M_i}({\bf b}_{i+1})$, while the second condition (Lovász) shortens the projection $\mathrm{proj}_{M_i^\perp}({\bf b}_{i+1})= {\bf b}_{i+1}^*$.

References

Phong Q. Nguyen and Damien Stehlé. An LLL algorithm with quadratic complexity. Siam J. Comput., 2009. doi:10.1137/070705702 [PDF]

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.