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?)

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Should there be an exponent on $[-M,\hspace{-0.02 in}M\hspace{.03 in}]$? $\;$ $\endgroup$
    – user5810
    Commented 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.
    Commented 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.
    Commented Aug 2, 2015 at 21:00
  • $\begingroup$ Cross-posted on CS.SE. Please don't cross-post on multiple sites. $\endgroup$
    – D.W.
    Commented Sep 22, 2015 at 21:07

3 Answers 3

Reset to default
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.

Improve this answer
$\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.
    Commented 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.
    Commented 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.
    Commented Sep 20, 2015 at 18:51
  • $\begingroup$ FYI I also posted a follow-up question here $\endgroup$
    – Berk U.
    Commented 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.)

Improve this answer
$\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.
    Commented Aug 1, 2015 at 1:16
  • $\begingroup$ @BerkU.: Sorry! $\endgroup$
    – Joseph O'Rourke
    Commented 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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ By original article, are you refering to the one that @Joseph O'Rourke linked? $\endgroup$
    – Berk U.
    Commented 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$
    – Joseph O'Rourke
    Commented Aug 2, 2015 at 19:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .