# Approximation of rational sequences via linear recurrences of small order

I wish to approximate a sequence of rational numbers using a linear recurrence of order $$k$$ for some small $$k$$ (preferably as small as possible). The Berlekamp-Massey algorithm solves the exact version of this problem, finding the optimal such $$k$$, and even the coefficients of the linear recurrence generating the sequence.

However, a sequence might have a shorter approximation than the exact solution if we allow some error. For example the sequence -1,0,-1.02,-2.05,-5,-12.03,-29 is well-approximated by the recurrence $$a_n = 2a_{n-1} + a_{n-2}$$ to within a total error of $$\varepsilon \leq 1$$.

Is there an algorithm that, given a sequence of rational numbers, a target order $$k$$ and a target error bound $$\varepsilon > 0$$, tells me whether there is a linear recurrence of order $$\leq k$$ that approximates the given sequence with a total (square / absolute / etc.) error less than $$\varepsilon$$, and if possible exhibits such a linear recurrence?

[Note that this is a duplicate of this Mathematics SO question which has been unanswered since October 2020.]

• – D.W.
Jun 15, 2021 at 19:01

Your problem appears to be an instance of the following: given a $$m \times k$$ matrix $$M$$, does there exist a $$k$$-vector $$x \in \mathbb{Z}^k$$ such that $$\|Mx\| \le \epsilon$$. (Here $$x$$ represents the linear recurrence weights, and $$M$$ is derived from the sequence.) This is essentially an instance of a shortest vector problem, which appears to be NP-hard (depending on the norm). You might be able to find a reasonable approximation using LLL lattice reduction or similar methods.
I don't know if there are any methods that take advantage of the special structure of $$M$$ in your situation to do better than solving a general SVP problem. So, this is not a proof of hardness for your particular problem.