On constructing a shortest linear recurrence relation

Abstract

It has been shown in the literature that a formulation of the minimal partial realization problem in terms of exact modeling of a behavior lends itself to an iterative polynomial solution. For the scalar case, we explicitly present such a solution in full detail. Unlike classical solution methods based on Hankel matrices, the algorithm is constructive. It iteratively constructs a partial realization of minimal McMillan degree. The algorithm is known in information theory as the Berlekamp-Massey algorithm and is used for constructing a shortest linear recurrence relation for a finite sequence of numbers.