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?