The LLL algorithm is used to approximate the Shortest Vector Problem, i.e., it outputs a reduced basis. Such a basis will satisfy two conditions: $$ \forall i \gt j. \quad \lvert\mu_{ij}\rvert \le \frac{1}{2} \qquad\text{[size-reduced]} $$ $$ \forall i.\quad \lVert b_i^*\rVert^2 \le \lVert b_{i+1}^*\rVert^2 + \mu_{i+1,i}^2\lVert b_i^*\rVert^2 \qquad\text{[Lovász condition]}$$

It seems the first condition assures the resulting basis is nearly orthogonal. But what does the Lovász condition mean and why is it used?

up vote 8 down vote accepted

The issue with the length-reduction criterion alone (and the reason the Lovász condition is included in the LLL algorithm) is that the following basis satisfies it:

A length-reduced lattice basis

(The grey arrow is the projection of $b_2$ to the orthogonal complement of $b_1$.)

Clearly, this basis is not very short, nor is it close to being orthogonal (i.e., note that length reduction alone does not imply almost-orthogonality!). The Lovász condition is suited to detect such a situation: If the order of the vectors is swapped, another length reduction can easily be performed, yielding the following LLL-reduced basis:

A LLL-reduced lattice basis

It seems that Lenstra, Lenstra, and Lovász have noticed that a situation in which length reduction alone is stuck with a very bad basis — as depicted in the first image — always has vectors which are in the "wrong" order comparing their lengths and which are far from being orthogonal, and that it helps in this case to exchange them and continue length-reducing.¹ That is really the core idea of the LLL algorithm.

I think of the Lovász condition mainly as a technical construction that just "turned out" to work well, but by rearranging the terms, one may get a feeling for why it enforces close-to-orthogonality:

$$ (\delta-\mu_{i+1,i}^2)\lVert b_i^\ast\rVert^2 \;\leq\; \lVert b_{i+1}^\ast\rVert^2 $$ (In your formula, $\delta=1$ is "hardcoded".)

The Gram-Schmidt coefficient $\mu_{i+1,i}$ measures the angle between $b_i^\ast$ and $b_{i+1}$; the angle is small iff $\mu$ is close to $1$, and it is large (i.e. almost orthogonal) iff $\mu$ is close to $0$. Note this talks about the angle between the orthogonalized vector $b_i^\ast$ and the lattice vector $b_{i+1}$, but $b_i^\ast$ is in turn forced to be "quite close" to $b_i$, hence this also bounds the angle between the lattice basis vectors depending on the orthogonalized vectors' lengths relative to each other.

In short: The Lovász condition is fulfilled if the vectors are close enough to being orthogonal, or if they are roughly ordered by length. Both of these properties lead to length reduction being quite effective.

¹ The procedure of changing the order of some vectors and length-reducing approximates another basis reduction concept, weight reduction, but there is no efficient algorithm to compute that one.

  • 2
    Minor edit: I think $\mu$ in the Lovasz condition needs to be squared: $(\delta-\mu^2_{i+1,i})\lVert b_i^\ast\rVert^2 \;\leq\; \lVert b_{i+1}^\ast\rVert^2$ – galvatron May 31 '17 at 20:34

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.