Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $v_1,\ldots,v_n$ be linearly independent vector in $\mathbb{R}^n$, and let $\Lambda=\oplus_i^n \mathbb{Z}v_i$. The question is, given a vector $w$ find the element $v$ of the lattice $\Lambda$ closest to $w$. It is assumed that an inner product structure has been imposed on $\mathbb{R}^n$. This is called the CVP (for closest vector problem).

I've found various algorithms that can find the closest vector, but is there a particular algorithm that is especially simple to understand and to program? I want to test a few low dimensional examples, and easy to write computer code would be preferable.

Any suggestion?

share|improve this question
    
Hi, I've added the algorithms and numerical analysis tags - apologies if you think they're not appropriate. –  Zen Harper Mar 24 '11 at 8:20
3  

1 Answer 1

A nice rahter-simple option would be Babai's Nearest Plane Algorithm. This is an approximation algorithm which outputs a vector of the lattice which is "close" the given target $w$. The accuracy of the approximation depends on the rank $n$ of the lattice. The good things are: the algorithm runs in polynomial-time and it is fairly easy to implement.

Input: Basis $B\in\mathbb{Z}^{m\times n}, w\in\mathbb{Z}^{m}$

Output: A vector $x\in \mathcal{L}(B)$ such that $\lVert x - w\rVert \leq 2^{\frac{n}{2}} \:\text{dist}(w,\mathcal{L}(B))$

  1. Run $\delta$-LLL on $B$ with $\delta=3/4$.
  2. $b \leftarrow w$

    for $j = n$ to $1$ do

    $\qquad b=b-c_j b_j$ where $c_j = \lceil \langle b, \tilde{b}_j \rangle / \langle \tilde{b}_j, \tilde{b}_j \rangle\rfloor$

    Output $x:=w-b$

Above, $\delta$-LLL denotes the Lenstra-Lenstra-Lovasz algorithm, used as a subroutine to obtain a $\delta$-LLL Reduced Basis $\lbrace b_1,\ldots,b_n \rbrace$ of your original basis $\lbrace v_j \rbrace$. The vectors $\lbrace \tilde{b}_j \rbrace$ are the Gram-Schmidt orthogonalization of the LLL basis.

It seems that this algorithm is normally the first to be taught in university courses. I read these algorithms and definitions in Oded Regev's course about Lattices in Computer Science.

For exacts algorithms, this short review might be helpful. Alternatively, this text is more technical but rather complete.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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