Lovász Lattice Reduction - analysis

Recall that a basis $({\mathbf{b}}_1,\dots,{\mathbf{b}}_n)$ for a lattice is Lovász-reduced if it satisfies the relations:

1. $\vert\mu_{ij}\vert\leq \frac{1}{2}$,
2. $\Vert{\mathbf{b}}_{i+1}^*\Vert\geq\frac{1}{\sqrt{2}}\Vert{\mathbf{b}}_i^*\Vert$,

where ${\mathbf{b}}_1^*,\dots,{\mathbf{b}}_n^*$ is the Gram-Schmidt orthogonalized sequence and ${\mathbf{b}}_i={\mathbf{b}}_i^*=\sum_{j<i}\mu_{ij}{\mathbf{b}}_j^*$. In order to prove that Lovász' lattice reduction algorithm terminates, we introduce the potential function $\mathcal{P}$ of a basis defined as:

$$\mathcal{P} =$$vol$$({\mathbf{b}}_1)$$vol$$({\mathbf{b}}_1{\mathbf{b}}_2)\cdots$$vol$$({\mathbf{b}}_1\cdots{\mathbf{b}}_{n-1}) =\Vert{\mathbf{b}}_1^*\Vert^{n-1}\cdots\Vert{\mathbf{b}}_{n-1}^*\Vert^1$$.$$$$

We would like to show that the Lovász algorithm terminates by observing that in each round, the potential function decreases by a factor bounded above by some constant $c<1$. Because of this, and the fact that $\mathcal{P}^2$ is a positive integer, we know that the algorithm must terminate in a number of rounds logarithmic in the initial potential.

Recall that the ``coefficient reduction'' process reduces each $\mu_{ij}$ to $\vert\mu_{ij}\vert\le 1/2$ without affecting the orthogonalized sequence and therefore without affecting the potential function. Once ``coefficient reduction'' has been performed, we check the second property. If there is some $i$ with $\Vert{\mathbf{b}}_{i+1}^*\Vert<\frac{1}{\sqrt{2}}\Vert{\mathbf{b}}_i^*\Vert$, we simply swap these two elements. This will change the orthogonalized vectors ${\mathbf{b}}_i^*$ and ${\mathbf{b}}_{i+1}^*$, but the potential is only affected by:

$$\frac{\mathcal{P}_{\text{new}}}{\math... ...\mathbf{b}}_i^*)_{\text{new}}\Vert}{\Vert({\mathbf{b}}_i^*)_{\text{old}}\Vert}$$

Next we project along the direction of $\mathcal{U}_{i-1}=$Span$\{{\mathbf{b}}_1\cdots{\mathbf{b}}_{i-1}\}$. After this projection, the vectors ${\mathbf{b}}_1\cdots{\mathbf{b}}_{i-1}$ are taken to the zero vector. Denote the projection by ${\mathbf{x}}\mapsto{\mathbf{x'}}$. Now examining $V=$Span$\{{\mathbf{b'}}_i,{\mathbf{b'}}_{i+1}\}=$   Span$\{{\mathbf{b}}_i^*,{\mathbf{b}}_{i+1}^*\}$, we find that

$$({\mathbf{b'}}_i)_{\text{old}} = ({\mathbf{b}}_i^*)_{\text{old}}\notag$$ (1)

$$({\mathbf{b'}}_{i+1})_{\text{old}} = ({\mathbf{b}}_{i+1}^*)_{\text{old}}+\mu_{i+1,i}({\mathbf{b}}_i^*)_{\text{old}}\notag$$ (2)

$$({\mathbf{b'}}_i)_{\text{new}} = ({\mathbf{b'}}_{i+1})_{\text{old}}= ({\mathbf{b}}_i^*)_{\text{new}}\notag$$ (3)

$$({\mathbf{b'}}_{i+1})_{\text{new}} = ({\mathbf{b'}}_i)_{\text{old}}= ({\mathbf{b}}_i^*)_{\text{old}}\text{.}\notag$$ (4)

Therefore,

$$\frac{\mathcal{P}_{\text{new}}}{\math... ...({\mathbf{b'}}_i)_{\text{new}}\Vert}{\Vert({\mathbf{b'}}_i)_{\text{old}}\Vert}$$

Now, since $\mu_{ij}\leq 1/2$, the projection of ${\mathbf{b'}}_{i+1}$ onto ${\mathbf{b}}_i^*$ is prevented from being very large. The calculation follows.

$$\Vert({\mathbf{b'}}_{i})_{\text{new}}\Vert^2 = \Vert({\mathbf{b'}}_{i+1})_{\text{old}}\Vert^2\notag$$ (5)

$$= \Vert({\mathbf{b}}_{i+1}^*)_{\text{old}}\Vert^2+\mu_{i+1,i}^2\Vert ({\mathbf{b}}_{i}^*)_{\text{old}}\Vert^2\notag$$ (6)

$$\leq \left(\frac{1}{2}+ \frac{1}{4}\right)\Vert({\mathbf{b}}_{i}^*)_{\text{old}}\Vert^2\notag$$ (7)

$$\leq \frac{3}{4}\Vert({\mathbf{b'}}_{i})_{\text{old}}\Vert^2\text{,}\notag$$ (8)

so $\mathcal{P}_{\text{new}}/\mathcal{P}_{\text{old}}\leq \sqrt{3}/2$.

We see now that we could replace the second Lovász condition by:

($2_\delta$)

$\Vert{\mathbf{b}}_{i+1}^*\Vert\geq\delta\Vert{\mathbf{b}}_i^*\Vert$,

where $\delta$ is allowed to be any number such that $\sqrt{\delta^2+1/4}<1$, so $\delta<\sqrt{3}/2$. The running time and quality of the output would be expected to be greater for larger values of $\delta$.

Remark 1.1   These are the values of $\delta$ for which we know the algorithm terminates (and specifically in polynomial time). However, it is possible for the algorithm to terminate for special inputs and larger values of $\delta$. (For example, an orthogonal basis and any $\delta$ would produce an algorithm that terminates.)

Remark 1.2   Odlyzko and TeRiele used this algorithm to approximate 70 zeroes of the Riemann Zeta function. In their experiments, the lattice reduction algorithm terminated rather quickly even in the case $\delta=\sqrt{3}/2$, even though in this case we cannot prove termination, let alone termination in polynomial time. Moreover, this large value of $\delta$ produced outputs of far higher quality than predicted by the analysis. This is a case in which the search for a polynomial-time algorithm required an insight into the nature of the problem, and that insight lead to a solution that turned out to be ``unreasonably effective'' in practice.