Technical Report CS-2018-04

Title: Vector Versions of Prony's Algorithm and Vector-Valued Rational Approximations
Authors: Avram Sidi
PDFCurrently accessibly only within the Technion network
Abstract: Given the scalar sequence $\{f_m\}^\infty_{m=0}$ that satisfies $$f_m=\sum^k_{i=1}a_i\zeta_i^m,\quad m=0,1,\ldots,$$ where $a_i, \zeta_i\in \mathbb{C}$ and $\zeta_i$ are distinct, the algorithm of Prony concerns the determination of the $a_i$ and the $\zeta_i$ from a finite number of the $f_m$. This algorithm is also related to Pad\'{e} approximants from the infinite power series $\sum^\infty_{j=0}f_jz^j$.

In this work, we discuss ways of extending Prony's algorithm to sequences of vectors $\{\ff_m\}^\infty_{m=0}$ in $\mathbb{C}^N$ that satisfy $$\ff_m=\sum^k_{i=1}\aaa_i\zeta_i^m, \quad m=0,1,\ldots,$$ where $\aaa_i\in\mathbb{C}^N$ and $\zeta_i\in\mathbb{C}$. Two distinct problems arise depending on whether the vectors $\aaa_i$ are linearly independent or not. We consider different approaches that enable us to determine the $\aaa_i$ and $\zeta_i$ for these two problems, and develop suitable methods. We concentrate especially on extensions that take into account the possibility of the components of the $\aaa_i$ being coupled. One of the applications concern the determination of a number of the pairs $(\zeta_i,\aaa_i)$ for which $|\zeta_i|$ are largest. These applications can be applied to the more general case in which $$\ff_m=\sum^k_{i=1}\pp_i(m)\zeta_i^m, \quad m=0,1,\ldots,$$ where $\pp_i(m)\in\mathbb{C}^N$ are some (vector-valued) polynomials in $m$, and $\zeta_i\in\mathbb{C}$ are distinct. Finally, the methods suggested here can be extended to vector sequences in infinite dimensional spaces in a straightforward manner.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 2018
To the main CS technical reports page

Computer science department, Technion