Approximation of rational sequences via linear recurrences of small order

Question

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.]

Answer 1

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.