9
$\begingroup$

I am currently working on problem that I think could be expressed as an integer lattice problem.

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$ that minimizes the angle between $u$ and $v$. That is, I would like $$v \in \text{argmax}_{w \in L} \frac{u.w}{\|u\|\|w\|}$$

Here, the objective is maximizing the cosine of the angle between $u$ and $w$ (i.e. minimizing the angle between $u$ and $w$). The vectors $u$ and $w$ are said to be "similar" if this quantity is close to 1.

I am wondering:

  • Is this problem related to a well-known integer lattice problem (e.g. a closest vector problem)?

  • Could this problem be solved using existing lattice algorithms (e.g. the LLL algorithm?)

$\endgroup$
4
  • 1
    $\begingroup$ Should there be an exponent on $[-M,\hspace{-0.02 in}M\hspace{.03 in}]$? $\;$ $\endgroup$
    – user5810
    Jul 31, 2015 at 1:23
  • 3
    $\begingroup$ Curiously, why isn't this solvable by zig-zagging the lattice? For example if $n=2$, of the four points on the unit square, pick the closest to your vector. Lets say this point is $(1,1)$, in the positive quadrant. Look one step up and right and determine which location is closer to $u$. Move to that point, and repeat. Collect all distances this way, and pick the minimum one. You might have to repeat this with the initial best point in the opposite quadrant to check the other direction. It seems like this algorithm is $O(Mn)$. Or just find all unit boxes $u$ intersects and poll each vertex. $\endgroup$
    – Alex R.
    Aug 2, 2015 at 4:48
  • $\begingroup$ @AlexR This is really interesting. Would you mind writing it up as an answer so we can discuss it fully? $\endgroup$
    – Berk U.
    Aug 2, 2015 at 21:00
  • $\begingroup$ Cross-posted on CS.SE. Please don't cross-post on multiple sites. $\endgroup$
    – D.W.
    Sep 22, 2015 at 21:07

3 Answers 3

6
$\begingroup$

Writing up the comment: You just need to "pixelate" the line by finding all lattice boxes that it crosses:enter image description here

Then the answer vector $v$ must connect to one of the corners of the shaded boxes. Instead of first collecting the boxes, try the following zig-zag algorithm: start from the origin and poll the up and right nearest lattice points. One of them is closer to your vector $u$, so pick that one. Again, looking up and right, pick the closer vertex. Repeating this procedure will give you a list of distances for each point reached. Pick the minimum distance and that's your answer. This algorithm is $O(Mn)$, and perhaps can be sped up by someone more clever than me.

$\endgroup$
4
  • $\begingroup$ Thanks for this! I actually tried this method out and it works very nicely! I am wondering if it is possible to prove that this algorithm yields the globally optimal solution to the most similar vector problem (or does it just produce a good solution?) $\endgroup$
    – Berk U.
    Sep 15, 2015 at 19:44
  • $\begingroup$ @BerkU.: it should be the global best solution because the global solution must be located at one of the shaded box corners (you will have to check in the negative direction as well). $\endgroup$
    – Alex R.
    Sep 15, 2015 at 19:46
  • $\begingroup$ Hmm I agree that the global solution has to be located at one of the shaded box corners. In order for algorithm to find the global solution in this case, it would have to check the cosine similarity at all of the corners. Is this the case? (i.e. do you actually end up evaluating all of the points?) $\endgroup$
    – Berk U.
    Sep 20, 2015 at 18:51
  • $\begingroup$ FYI I also posted a follow-up question here $\endgroup$
    – Berk U.
    Sep 20, 2015 at 18:52
2
$\begingroup$

Not certain whether this "closest vector problem" will help...:

Babai, László. "On Lovász’ lattice reduction and the nearest lattice point problem." Combinatorica 6, no. 1 (1986): 1-13. (Springer journal link.):

Abstract: "... find a point of a given lattice, nearest within a factor of $c^d$ ($c$ = const.) to a given point in $\mathbb{R}^d$....

He is "answering a question of Vera Sós." But fundamentally, it seems Babai basically rounds coordinates to the nearest integer, to achieve a close vector. (Pardon the too-crude summary.)

$\endgroup$
2
  • $\begingroup$ Thank you! Unfortunately the problem is not the same. This paper is trying to find a point on the integer lattice $w \in L$ that minimizes the distance between $\|u-w\|$ as opposed to the point that minimizes the angle between $u$ and $w$. $\endgroup$
    – Berk U.
    Aug 1, 2015 at 1:16
  • $\begingroup$ @BerkU.: Sorry! $\endgroup$ Aug 1, 2015 at 15:53
2
$\begingroup$

Comment: You seem to be looking for best simultaneous diophantine approximations of a certain kind. In the original LLL article, "Factoring Polynomials with Rational Coefficients", the authors (Lenstra, Lenstra and Lovasz) describe how to find approximate solutions (in polynomial time) to very similar problems at the end of section 1.

$\endgroup$
2
  • $\begingroup$ By original article, are you refering to the one that @Joseph O'Rourke linked? $\endgroup$
    – Berk U.
    Aug 2, 2015 at 18:46
  • 3
    $\begingroup$ @BerkU.: He or she must mean: A. K. Lenstra, H. W. Lenstra, Jr. and L. Lovász, "Factoring polynomials with rational coefficients," Math. Ann. 261 (1982), 515–534. (Springer link.) $\endgroup$ Aug 2, 2015 at 19:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.