5
$\begingroup$

I am currently working on an integer lattice problem, called the "most similar vector problem," and wondering if can be solved correctly by a simple "zig-zagging" algorithm.

Given a real vector $u \in \mathbb{R}^n$, the most similar vector problem is to find a discrete vector $v$ from a bounded integer lattice $L \in \mathbb{Z}^n \cap [-10,10]^n$ that maximizes the cosine similarity between $u$ and $v$. That is,

$$v \in \text{argmax}_{w \in L} \frac{u.w}{\|u\|\|w\|}$$

In an earlier post on MathOverflow, someone proposed solving the most similar vector problem by "zig-zagging" across the lattice. Informally, this is a greedy algorithm that generates a sequence of lattice vectors $w^k$ by starting from the origin and taking steps of length one in the direction of $u$. On the $k^\text{th}$ iteration, the algorithm chooses $w^{k+1}$ as the most similar lattice vector that one unit away from $w^k$ in some dimension. The algorithm terminates in $K$ iterations after we hit the boundary of the lattice in each dimension.

Formally, the "zig-zagging" algorithm can be stated as follows:

INITIALIZATION $$\begin{align} w^0 &\longleftarrow (0,\ldots,0) &\text{(starting point)} \\ d &\longleftarrow \text{sign}(u) \in \{-1,0,1\}^n &\text{(step direction)} \\ \mathcal{J} &\longleftarrow \big\{1,\ldots,n ~\big|~ d_j \neq 0 \big\} &\text{(set of dimensions in which steps can be taken)} \end{align}$$

ALGORITHM

$\text{while } \mathcal{J} \neq \emptyset$

$$\begin{align} j^* &\longleftarrow \text{argmax}_{j \in \mathcal{J}} \frac{u \cdot(w^k + d \cdot e_j)}{\|u\|\|w^k + d \cdot e_j\|} & \text{(step in dimension $j$ that yields $w^{k+1}$ most similar to $u$)} \\ w^{k+1} &\longleftarrow w^k + d \cdot e_{j^*} \\ \mathcal{J} &\longleftarrow \mathcal{J} \setminus \big\{1,\ldots,n ~\big|~ |w_j^{k+1}|=10 \big\} & \text{(remove coordinates at boundary from consideration)} \\ k & \longleftarrow k + 1 \end{align}$$

Here $e_j$ is a unit vector with 1 in the $j^\text{th}$ coordinate and 0 elsewhere.

Once the algorithm terminates, we can use the sequence of generated lattice points $w^1,\ldots,w^K$ to find the most similar vector, $v$ as:

$$v \in \text{argmax}_{k=1,\ldots,K} \frac{u.w^k}{\|u\|\|w^k\|}$$

My question is as follows: Does the zig-zagging algorithm described above produce the most similar vector? If so, how can I prove it? If not, is there a counter example?

$\endgroup$
  • 1
    $\begingroup$ I think your algorithm formalization has some issues. What does $w^k+d_j$ mean? $w^k$ is a vector, but $d_j$ is a scalar. I'm guessing you mean to use $w^k+x$ where $x$ ranges over all vectors that are zero in all but one position, say $x_j\ne 0$, and $x_j=d_j$. Perhaps edit the question? $\endgroup$ – D.W. Sep 22 '15 at 20:53
  • 1
    $\begingroup$ Your problem looks similar to the Closest Vector Problem (CVP), which is known to be NP-hard. Have you tried looking for a reduction from CVP or SVP or some similar standard lattice problem, to see if you can show your problem is NP-hard? The main difference is cosine distance instead of Euclidean distance. $\endgroup$ – D.W. Sep 22 '15 at 20:56
  • $\begingroup$ Also posted on MathOverflow. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. If you don't get a satisfying answer after a week or so, feel free to flag for migration. $\endgroup$ – D.W. Sep 22 '15 at 21:02
  • $\begingroup$ @D.W. Thanks for letting me know. Sorry about the double posting - I was not aware that I could migrate the question between sites. That said, the question is now effectively migrated since the version on MathOverflow is closed. $\endgroup$ – Berk U. Sep 22 '15 at 21:54
  • $\begingroup$ @D.W. You're right the problem is very similar to the SVP/CVP. I looked into equivalences after posting the resource request but they did not seem promising. Part of the issue is that the cosine distance is scale-invariant / not a proper distance metric. The bound is also somewhat important here -- the zig-zagging algorithm is $O(Mn)$, where $M$ is the length of the boundary, so if the algorithm is correct, then I don't think that a reduction is possible, right? $\endgroup$ – Berk U. Sep 22 '15 at 22:17

Your Answer

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

Browse other questions tagged or ask your own question.