CODEWITHSUNDEEP
least-squaresdata-fitting
Hiro
Hiro

Reputation: 505

Fitting data to a square lattice (discrete points by multiple parameters)

I have measured points on a two dimensional square lattice.

data points.

How can I fit the data to a square lattice? I guess some methods like curve fitting or least square approximation would work, but I couldn't find any literature for the same problem.

Upvotes: 3

Views: 376

Answers (2)

pb1729
pb1729

Reputation: 101

Method

We can make use of the LLL algorithm here to find a lattice that closely matches the data points. Roughly speaking, the algorithm tries to find a set of basis vectors made of short, roughly orthogonal vectors. Unfortunately, just feeding our dataset directly to LLL will not work. GuiTaek's excellent answer shows that any fitting routine for lattices needs to penalize very closely spaced lattices. To make this work in our application, we take inspiration from the application of LLL to finding integer relations, and basically just steal the technique used there. The only difference is that rather than having the lower row of the matrix be real numbers, we add a whole block to the bottom of the matrix, each column of which is one of our data points. So rather than finding integer relations between real numbers, we're finding integer relations between vectors.

So the matrix we pass to LLL looks like this:

[     1                             ]
[             1                     ]
[                     1             ]
[                             1     ]
[   ζ*x1    ζ*x2    ζ*x3    ζ*x4    ]
[   ζ*y1    ζ*y2    ζ*y3    ζ*y4    ]
[   ζ*z1    ζ*z2    ζ*z3    ζ*z4    ]

Here, ζ is a parameter that tells us how much to allow a fine lattice. A larger value permits a finer lattice. Though integer relation algorithms typically use a very high value of ζ, we should use a more moderate value here, to put a greater penalty on finer lattices.

Now if we look at the output, we ignore the rows of the output that had the identity matrix, and just look at the rows that had our data in them (in the above example, the last 3 rows). If we've chosen ζ well, then the output will have a few long vectors (corresponding to the basis of the lattice) and some short vectors (corresponding to the noise in our measurements). Throw away the short ones, keep the long ones, and you've got your basis!

Code

Repo here: https://github.com/pb1729/latticefit

Just run python lattice_fit.py for a demonstration.

API: Call lattice_fit(dataset, zeta). The result will be a list of basis vectors, sorted from longest to shortest. These will approach zero length at some point, and it's your responsibility as the caller to cut off the list there. (Or perhaps you already know the size of the lattice basis.)

Caveats

Admittedly, due to the large (though still polynomial) time complexity of the LLL algorithm, this method scales poorly with the number of data points. The best suggestion I have so far here is just to run the algorithm on manageable subsets of the data, filter out the near-zero vectors, and then run the algorithm again on all the basis vectors found this way.

Disclaimer: If you know your lattice is 2d and square, there is probably a better method specialized to that case.

Upvotes: 0

GuiTaek
GuiTaek

Reputation: 484

TLDR; not possible (without punishment for fine lattices)

So I had the same question and I researched why it isn't possible. I show that for every n rational points, x1, ... , xn there exists some rational q, b such that for every i there exists an integer z such that xi = z * q + b.

Proof by induction:

base case:

We start at n=2, for that, choose q = x1 - x0 and b = x0

assumption:

let there be x1, ..., xn+1 rational points. Then for the first n points, there exists some rational q, b such that for every i<=n there exists an integer z such that xi = z * q + b

inductive step:

take q, b from the assumption. We find a natural number beta such that q' := q / s, b satisfies the assumption for i<=n+1.

Indeed, for every natural number and i<=n, when xi = z * q + b, then also xi = z * s * q' + b

Now we have to choose a natural s, such that x := xn+1 = z * q' + b for an integer z.

I will derive s and it will also be a proof that such a s exists. Define beta through x = beta * q + b. Because every number except beta is rational, so is beta:

beta = u / v

define s := v

Then it holds: x = beta * q + b = u / v * q + b = u / v * s * q' + b = u * q' + b where u is an integer.

Empirical Proof

using the formulas from the proof, I made a python program that finds for arbitrary fractions the perfect lattice:

from fractions import Fraction
import random

def random_fract():
    return Fraction(
        random.randint(2, 1_000),
        random.randint(2, 100)
    )

def test_one_lattice():
    x_vals = [random_fract() for i in range(1_000)]
    # remove duplicates -- the algorithm doesn't work for them
    x_vals = list(set(x_vals))
    q = x_vals[1] - x_vals[0]

    b = x_vals[0]
    for fract in x_vals[2:]:
        q /= ((fract-b) / q).denominator
    for x in x_vals:
        z = (x - b) / q
        assert z * q + b == x
        assert z % 1 == 0

if __name__ == "__main__":
    for _ in range(50):
        test_one_lattice()

keep in mind this also holds for multiple dimensions of the space (they are independent) and also for multiple dimensions of the lattice (just set the other vectors to zero)

Upvotes: 2

Related Questions