3
$\begingroup$

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

$\endgroup$
1

1 Answer 1

3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.