An algebraic method to solve the minimal partial realization problem for scalar sequences (Q1106292): Difference between revisions

Let \(h_ 1,...,h_ N\) be a finite sequence of complex numbers. The minimal partial realization problem is to find the least n and complex numbers \(f_ 0,...,f_ n\) with \(f_ n=1\) such that \(f_ 0h_ r+f_ 1h_{r+1}+...+f_ nh_{n+r}=0\), for \(r=1,2,...,N-n\). This is related in an obvious way to finding rational approximations to \(h_ 1z^{- 1}+h_ 2z^{-2}+...+h_ Nz^{-N}\). After showing that an infinite Hankel matrix of rank n can be written as a product of a matrix with n columns and a matrix with n rows, the authors describe a straightforward method of solving the partial realization problem using linear algebra. Reviewer's remark: Although they mention Padé approximations in passing, the authors do not compare their method with other methods of solving the same problem. A well-known algorithm of E. R. Berlekamp and J. L. Massey uses an adaptation of the extended Euclidean algorithm for rational series to solve the partial realization problem; see, for example, Section 8.6 of \textit{R. Lidl} and \textit{H. Niederreiter} [Finite Fields (1984; Zbl 0554.12010)]. The reviewer has found it to be very effective over infinite as well as finite fields.