"Most Similar Vector Problem" on an Integer Lattice

Question

I am currently working on problem that I think could be expressed as an integer lattice problem, and hoping to find some guidance on this forum.

Given $u \in \mathbb{R}^n$ and a bounded integer lattice $L = \mathbb{Z}^n \cap [-M,M]^n$, I would like to find an integer vector $v \in L$ such that the angle between $u$ and $v$ is as small as possible. That is, I would like $$v \in \text{argmax}_{w \in L} \frac{u.w}{\|u\|\|w\|}$$

Here, the objective function is just the cosine between the vectors $u$ and $w$.

I am wondering if this problem can be formulated as a well-known integer lattice problem (such as a closest vector problem). If so, is there an algorithm that I could use to solve it? Any help or resources would be greatly appreciated.

Answer 1

I don't know of a good approach to this, or whether there's any literature on it.

However, if you're completely stuck, one possible approach is to use integer quadratic programming and binary search.

WLOG we can assume $\|u\|=1$ (otherwise replace $u$ with $u/\|u\|$). Now the decision problem is, given $\alpha$, to determine whether there exists $w$ such that $u \cdot w / \|w\| \ge \alpha$, i.e., such that $(u \cdot w)^2 \ge \alpha^2 \|w\|^2$. Define

$$\Phi(w) = \alpha \|w\|^2 - (u \cdot w)^2.$$

Note that $\Phi$ is a quadratic function in the unknowns $w_1,\dots,w_n$, and the decision problem can be solved by maximizing $\Phi(w)$ subject to the constraints $-M \le w_i \le M$. The answer to the decision problem is yes iff there's a solution to this integer quadratic program where $\Phi(w) \ge 0$. Now if you could solve the decision problem, you could use binary search on $\alpha$ to find the largest $\alpha$ for which a solution exists.

Unfortunately this requires integer quadratic programming, which might be very hard. One heuristic approach might be to relax to semidefinite programming instance (with real numbers instead of integers), look for a solution (in the reals), round to the nearest integer point, and see if that gives you a valid solution. This is not likely to give you an exact solution but it's possible it might give you some kind of approximation to the correct answer. Unfortunately, I have no idea how good or bad an approximation it might be.