5
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ This answer might be helpful. $\endgroup$
    – yyyyyyy
    Jan 15, 2017 at 21:47

1 Answer 1

2
$\begingroup$

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]

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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