Ferkans — Interactive Telecom Tutor

The Wrong Basis Is Half the Problem

Two bases can generate the same lattice and yet produce radically different detection performance. A near-orthogonal basis makes linear detectors nearly ML; a nearly-collinear basis makes them catastrophic. Lattice reduction takes the channel matrix $\mathbf{H}$ and finds a unimodular transformation $\mathbf{T}$ such that $\mathbf{H} \mathbf{T}$ is well-conditioned. Detection then runs on the new basis; a final $\mathbf{T}$ -multiplication maps the decision back. The trick is Gauss's: change coordinates until the problem is easy.

Definition:
Lattice Basis and Unimodular Equivalence

A basis of the lattice $\Lambda$ is any matrix $\mathbf{B} \in \mathbb{R}^{n \times m}$ with linearly independent columns such that $\Lambda = \{\mathbf{B}\mathbf{z} : \mathbf{z} \in \mathbb{Z}^m\}$ . Two bases $\mathbf{B}$ and $\mathbf{B}'$ generate the same lattice if and only if $\mathbf{B}' = \mathbf{B} \mathbf{T}$ for some unimodular matrix $\mathbf{T} \in \mathbb{Z}^{m \times m}$ (integer entries, $|\det \mathbf{T}| = 1$ ).

Unimodularity is critical: only unimodular transformations preserve the integer structure of the lattice. Any other invertible integer matrix would shrink or expand the lattice in ways that break the one-to-one correspondence with $\mathbb{Z}^m$ .

Definition:
LLL-Reduced Basis

Let $\mathbf{b}_1^*, \ldots, \mathbf{b}_m^*$ be the Gram-Schmidt orthogonalization of the basis $\mathbf{b}_1, \ldots, \mathbf{b}_m$ , and let $\mu_{i,j} = \langle \mathbf{b}_i, \mathbf{b}_j^* \rangle / \|\mathbf{b}_j^*\|^2$ . The basis is $\delta$ -LLL-reduced for $\delta \in (1/4, 1)$ if

Size reduction: $|\mu_{i,j}| \leq 1/2$ for all $1 \leq j < i \leq m$ ;
Lovász condition: $\|\mathbf{b}_i^*\|^2 \geq (\delta - \mu_{i,i-1}^2) \|\mathbf{b}_{i-1}^*\|^2$ for $i = 2, \ldots, m$ . The standard choice is $\delta = 3/4$ .

Lovász's condition bounds how quickly the Gram-Schmidt norms can decrease along the basis. It is what gives LLL its exponential-in- $m$ guarantees on the shortest vector.

Lenstra-Lenstra-Lovász (LLL) Reduction

Complexity:

O(m^4 \log(\max_i \|\mathbf{b}_i\|))

for rational inputs

Input: Basis

\mathbf{B} = [\mathbf{b}_1,\ldots,\mathbf{b}_m]

, parameter

\delta \in (1/4,1)

Output:

\delta

-LLL-reduced basis

\mathbf{B}'

, unimodular

\mathbf{T}

1. Compute Gram-Schmidt orthogonalization

\{\mathbf{b}_i^*\}

, coefficients

\{\mu_{i,j}\}

2.

\mathbf{T} \leftarrow \mathbf{I}_m

;

k \leftarrow 2

3. while

k \leq m

do

4.

\quad

for

j = k-1

down to

1

do

\quad

/* size reduction */

5.

\qquad

if

|\mu_{k,j}| > 1/2

then

\mathbf{b}_k \leftarrow \mathbf{b}_k - \lfloor \mu_{k,j} \rceil \mathbf{b}_j

; update

\mathbf{T}

,

\{\mu_{k,\cdot}\}

6.

\quad

end for

7.

\quad

if

\|\mathbf{b}_k^*\|^2 < (\delta - \mu_{k,k-1}^2) \|\mathbf{b}_{k-1}^*\|^2

then

8.

\qquad

swap

\mathbf{b}_k

and

\mathbf{b}_{k-1}

; update Gram-Schmidt;

k \leftarrow \max(k-1, 2)

9.

\quad

else

k \leftarrow k+1

10. end while

11. return

\mathbf{B}' = \mathbf{B}\mathbf{T}

,

\mathbf{T}

The loop alternates size-reduction steps (line 5) with Lovász swap tests (line 7). Each swap decreases a strict potential, guaranteeing termination in polynomial time.

Theorem: LLL Approximation of the Shortest Vector

Let $\mathbf{b}_1$ be the first vector of a $\delta$ -LLL-reduced basis of lattice $\Lambda$ , and let $\lambda_1(\Lambda)$ denote the length of the shortest nonzero vector. Then $\|\mathbf{b}_1\| \leq \left(\frac{4}{4\delta - 1}\right)^{(m-1)/2} \lambda_1(\Lambda).$ For $\delta = 3/4$ , the constant is $2^{(m-1)/2}$ .

After LLL, the first basis vector is at most exponentially (in $m$ ) longer than the genuinely shortest vector. For modest $m$ (say, $m \leq 8$ ), the exponential factor is at most $\sim 8$ , and in practice LLL does vastly better than its worst-case bound.

Proof

Lovász chain

From the Lovász condition, $\|\mathbf{b}_i^*\|^2 \geq (\delta - 1/4) \|\mathbf{b}_{i-1}^*\|^2$ (using $|\mu_{i,i-1}| \leq 1/2$ from size reduction). Therefore $\|\mathbf{b}_1^*\|^2 = \|\mathbf{b}_1\|^2 \leq \alpha^{i-1} \|\mathbf{b}_i^*\|^2$ with $\alpha = 1/(\delta - 1/4) = 4/(4\delta - 1)$ .

Lower bound the shortest vector by Gram-Schmidt norms

For any nonzero $\mathbf{v} \in \Lambda$ , write $\mathbf{v} = \sum_{j} c_j \mathbf{b}_j$ with integer $c_j$ and let $i$ be the largest index with $c_i \neq 0$ . Then $\|\mathbf{v}\|^2 \geq c_i^2 \|\mathbf{b}_i^*\|^2 \geq \|\mathbf{b}_i^*\|^2$ . Hence $\lambda_1(\Lambda)^2 \geq \min_i \|\mathbf{b}_i^*\|^2$ .

Combine

$\|\mathbf{b}_1\|^2 \leq \alpha^{m-1} \min_i \|\mathbf{b}_i^*\|^2 \leq \alpha^{m-1} \lambda_1(\Lambda)^2$ . Taking square roots gives the claim. $\blacksquare$

Definition:
LLL-Aided Zero-Forcing Detector

Given the channel $\mathbf{H}$ , run LLL to obtain $\mathbf{H}' = \mathbf{H} \mathbf{T}$ with $\mathbf{T}$ unimodular. Detect in the transformed coordinates: $\mathbf{z} = \mathbf{T}^{-1} \mathbf{x} \Rightarrow \mathbf{y} = \mathbf{H}' \mathbf{z} + \mathbf{w}.$ Run ZF on $\mathbf{H}'$ : $\tilde{\mathbf{z}} = (\mathbf{H}'^H \mathbf{H}')^{-1} \mathbf{H}'^H \mathbf{y}$ , round to the nearest integer $\hat{\mathbf{z}} = \lfloor \tilde{\mathbf{z}} \rceil$ , then map back: $\hat{\mathbf{x}} = \mathbf{T} \hat{\mathbf{z}}$ , and finally slice onto the constellation $\mathcal{A}^{n_t}$ .

The rounding in the reduced basis is much more reliable because $(\mathbf{H}'^H \mathbf{H}')^{-1}$ has dramatically smaller diagonal entries than the original $(\mathbf{H}^{H} \mathbf{H})^{-1}$ — the noise enhancement per stream is compressed.

Theorem: LLL-Aided ZF Achieves Full Receive Diversity

For i.i.d. Rayleigh fading $\mathbf{H} \in \mathbb{C}^{n_r \times n_t}$ with $n_r \geq n_t$ , the LLL-aided ZF detector achieves the full receive diversity order $n_r$ in terms of BER versus SNR: $\text{BER} \doteq \text{SNR}^{-n_r} \quad \text{as SNR} \to \infty.$ In contrast, plain ZF achieves only diversity order $n_r - n_t + 1$ .

Plain ZF inherits the worst eigenvalue of $\mathbf{H}^{H} \mathbf{H}$ (diversity $n_r - n_t + 1$ ). LLL rebalances the eigenvalue spread in the effective lattice, recovering the full $n_r$ -fold diversity enjoyed by ML.

Proof

Diversity via minimum eigenvalue

The ZF detector's error probability is dominated by the smallest diagonal of $(\mathbf{H}^{H}\mathbf{H})^{-1}$ , which scales with the smallest eigenvalue $\lambda_{\min}(\mathbf{H}^{H}\mathbf{H})$ . For i.i.d. Rayleigh $\mathbf{H}$ , this eigenvalue's distribution has a tail $\sim \lambda^{n_r - n_t}$ near zero, yielding diversity $n_r - n_t + 1$ .

Lattice-reduction geometry

In the reduced basis, the relevant quantity is the minimum successive-minima product $\prod_i \|\mathbf{b}_i^*\|$ , which by Minkowski's theorem concentrates around $|\det \mathbf{H}|^{2/n_t}$ . For i.i.d. Gaussian $\mathbf{H}$ , $|\det \mathbf{H}|^2$ has the distribution of a product of $n_t$ chi-squared variables of increasing degrees — its tail is governed by $n_r$ d.o.f., not $n_r - n_t + 1$ .

Taricco-Biglieri diversity argument

Taricco and Biglieri (2008) and Jaldén-Elia (2010) formalize this: the error probability of LLL-aided ZF is bounded by the probability that any lattice point inside a ball of size $\sim{\sigma^2}^{1/2}$ around the received vector causes a wrong decision. Under LLL, this event has probability $\doteq \text{SNR}^{-n_r}$ by a direct Minkowski-volume argument.

Conclusion

Combining the steps, LLL-aided ZF achieves diversity $n_r$ , matching ML up to a constant SNR offset, while maintaining polynomial complexity. $\blacksquare$

,

Key Takeaway

LLL reduction turns the channel's worst feature — ill-conditioning — into a solved problem. Combined with any linear detector, it yields full-diversity near-ML performance at polynomial cost. It is the default "cheap near-ML" tool for MIMO detection.

LLL Basis Reduction in $\mathbb{R}^2$

Visualize how LLL transforms an ill-conditioned 2D basis into a near-orthogonal one. The lattice is invariant; only the basis changes.

Parameters

Initial skew2

LLL in Action: Basis Vectors Becoming Orthogonal

Animate the size-reduction and swap steps of LLL on a 2D lattice.

Each frame shows one LLL step: either a size reduction (projection onto a previous basis vector) or a Lovász swap.

MIMO Detector Comparison

Detector	Complexity	Near-ML?	Diversity
ML (exhaustive)	$O(\|\mathcal{A}\|^{n_t})$	Exact ML	$n_r$
ZF	$O(n_t^3)$	No (dB loss)	$n_r - n_t + 1$
MMSE	$O(n_t^3)$	Slight gain over ZF	$n_r - n_t + 1$
MMSE-SIC (V-BLAST)	$O(n_t^3)$	Near-ML with coding	Capacity-achieving
Sphere decoder	Expected $O(n_t^p)$	Exact ML on termination	$n_r$
LLL-aided ZF	$O(n_t^3)$ plus LLL	Near-ML	$n_r$
LLL-aided MMSE-SIC	$O(n_t^3)$ plus LLL	Very near-ML	$n_r$

Example: LLL Reduction on a $2 \times 2$ Ill-Conditioned Channel

Reduce the basis $\mathbf{B} = \mathbf{H} = \begin{bmatrix} 1.0 & 0.9 \\ 0.0 & 0.1 \end{bmatrix}$ using LLL with $\delta = 3/4$ .

Solution

Gram-Schmidt

$\mathbf{b}_1^* = \mathbf{b}_1 = (1.0, 0.0)^T$ , $\|\mathbf{b}_1^*\|^2 = 1.0$ . $\mu_{2,1} = \langle \mathbf{b}_2, \mathbf{b}_1^*\rangle / \|\mathbf{b}_1^*\|^2 = 0.9$ . $\mathbf{b}_2^* = \mathbf{b}_2 - \mu_{2,1} \mathbf{b}_1^* = (0, 0.1)^T$ , $\|\mathbf{b}_2^*\|^2 = 0.01$ .

Size reduction

$|\mu_{2,1}| = 0.9 > 0.5$ , so $\mathbf{b}_2 \leftarrow \mathbf{b}_2 - \lfloor 0.9 \rceil \mathbf{b}_1 = (0.9 - 1, 0.1)^T = (-0.1, 0.1)^T$ . Update $\mu_{2,1} = -0.1$ . Now $|\mu_{2,1}| \leq 0.5$ . $\checkmark$

Lovász test

Check $\|\mathbf{b}_2^*\|^2 \geq (\delta - \mu_{2,1}^2) \|\mathbf{b}_1^*\|^2$ . Left: $0.01$ . Right: $(0.75 - 0.01) \cdot 1.0 = 0.74$ . $0.01 < 0.74$ — swap required.

Swap

Exchange $\mathbf{b}_1$ and $\mathbf{b}_2$ : $\mathbf{B} \leftarrow \begin{bmatrix} -0.1 & 1.0 \\ 0.1 & 0.0 \end{bmatrix}$ . Recompute Gram-Schmidt: $\mathbf{b}_1^* = (-0.1, 0.1)^T$ , $\|\mathbf{b}_1^*\|^2 = 0.02$ . $\mu_{2,1} = -0.5$ , $\mathbf{b}_2^* = \mathbf{b}_2 - (-0.5)\mathbf{b}_1 = (0.95, 0.05)^T$ , $\|\mathbf{b}_2^*\|^2 = 0.905$ .

Size reduce and test again

$|\mu_{2,1}| = 0.5 \leq 0.5$ . OK. Lovász: $0.905 \geq (0.75 - 0.25) \cdot 0.02 = 0.01$ . $\checkmark$ LLL terminates. The reduced basis has two nearly-orthogonal columns with balanced norms — a far better starting point for any detector than the original.

Historical Note: LLL — A Polynomial Algorithm That Changed Cryptography and Communications

1982–2003

The LLL algorithm was published in 1982 by Arjen Lenstra, Hendrik Lenstra Jr., and László Lovász in "Factoring Polynomials with Rational Coefficients." It was invented for a different purpose — polynomial factoring — but its applications rippled outward: cryptography (attacks on knapsack cryptosystems, RSA with low exponents), integer programming, and, starting with Yao-Hwang (2002) and Windpassinger-Fischer (2003), MIMO detection. LLL is one of the rare polynomial-time algorithms whose impact spans theoretical computer science, number theory, and wireless engineering.

Common Mistake: Complex-Valued LLL

Mistake:

One runs real-valued LLL on a complex MIMO channel by treating real and imaginary parts as separate rows, doubling $n_t$ and $n_r$ .

Correction:

Complex-LLL (Gan-Ling-Mow, 2009) works directly on $\mathbb{C}^{n_t}$ using Gaussian-integer unimodular matrices. It avoids the dimension doubling and converges faster. For QAM constellations, the Gaussian integer basis is native — no real-valued unfolding is needed. In practice, complex-LLL runs roughly twice as fast as real-LLL applied to the unfolded $2n_t \times 2n_r$ channel, with identical detection performance.

🔧Engineering Note

LLL Runtime Considerations

In practice LLL terminates in far fewer swaps than the worst case. For $n_t = 4$ i.i.d. Rayleigh channels, the average swap count is roughly $2n_t$ , giving effectively linear complexity per channel realization. The LLL preprocessing is computed once per coherence interval — typically hundreds to thousands of symbols — so its cost is amortized heavily and dominated by the per-symbol linear detector that follows.

Practical Constraints

•
Average swap count: $O(n_t)$ empirically; worst case $O(n_t^2 \log \kappa(\mathbf{H}))$
•
Reuse $\mathbf{T}$ across tones in OFDM when channel statistics are smooth

Lattice

A discrete additive subgroup of $\mathbb{R}^n$ generated by integer combinations of a set of linearly independent basis vectors. The image $\mathbf{H}\mathbb{Z}^{n_t}$ under a full-rank channel matrix is a lattice; MIMO detection is a bounded closest-vector problem on this lattice.

LLL Algorithm

Polynomial-time lattice basis reduction algorithm due to Lenstra, Lenstra, and Lovász (1982). Produces a basis with short, near-orthogonal vectors, approximating the shortest vector within a factor $2^{(m-1)/2}$ .

Related: Lattice, Unimodular Matrix

Quick Check

Why must the LLL transformation matrix $\mathbf{T}$ be unimodular?

To preserve the lattice: unimodular = integer entries with $|\det| = 1$

To minimize the condition number

To allow complex entries

Because $\mathbf{T}$ represents a rotation