0
$\begingroup$

Assume I have a matrix $A \in \mathbb{Z}^{m \times n}$, $m > n$, which forms a basis of a lattice. Given a vector target vector $t = Ax + e$, $t,e \in \mathbb{Z}^m$,$x \in \mathbb{Z}^n$, I want to find the (approximate) closest vector in the lattice $\mathcal{L}(A)$ to $t$.

I wanted to use Babai's nearest plane algorithm, in particular the NTL implementation NTL::NearVector to solve this problem (approximately) using LLL. However, it seems to me that in the literature and definitely in the software package, Babai's nearest plane algorithm requires a full-rank lattice?

What other techniques/embeddings can I use to solve the closest vector problem on an lattice with higher dimension than rank? Could I just extend the matrix with zero-vector columns?

$\endgroup$
1
  • $\begingroup$ In the $\ell_2$ norm, it should suffice to project your vector onto the (real) span of your lattice (which is a rank $n$ subspace), then orthogonally rotate this subspace to be isomorphic to $\mathbb{R}^n\times\{0\}^{m-n}$. I don't know how to do this in NTL in though, so will only leave the comment. $\endgroup$
    – Mark
    Sep 28 '21 at 20:45
1
$\begingroup$

no Babai's nearest plan algorithm doesn't necessary need a full rank lattice look at this paper here.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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