Abstract
Given the scalar sequence \(\{f_{m}\}^{\infty }_{m=0}\) that satisfies
where \(a_{i}, \zeta _{i}\in \mathbb {C}\) and ζi are distinct, the algorithm of Prony concerns the determination of the ai and the ζi from a finite number of the fm. This algorithm is also related to Padé approximants from the infinite power series \({\sum }^{\infty }_{j=0}f_{j}z^{j}\). In this work, we discuss ways of extending Prony’s algorithm to sequences of vectors \({\{\boldsymbol {f}_{m}\}}^{\infty }_{m=0}\) in \(\mathbb {C}^{N}\) that satisfy
where \(\boldsymbol {a}_{i}\in \mathbb {C}^{N}\) and \(\zeta _{i}\in \mathbb {C}\). Two distinct problems arise depending on whether the vectors ai are linearly independent or not. We consider different approaches that enable us to determine the ai and ζ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 ai being coupled. One of the applications we consider concerns the case in which
and we would like to approximate/determine of a number of the pairs (ζi, ai) for which |ζi| are largest. We present the related theory and provide numerical examples that confirm this theory. This application can be extended to the more general case in which
where \(\boldsymbol {p}_{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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Baker, G.A. Jr., Graves-Morris, P.R.: Padé Approximants, 2nd edn. Cambridge University Press, Cambridge (1996)
Ben-Or, M., Tiwari, P.: A deterministic algorithm for sparse multivariate polynomial interpolation. In: STOC ’88: Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, pp 301–309. ACM, New York (1988)
Chan, T.F.: An improved algorithm for computing the singular value decomposition. ACM Trans. Math. Software 8, 72–83 (1982)
Cuyt, A., Lee, W.-s.: Multivariate exponential analysis from the minimal number of samples. Adv. Comput. Math. 44, 987–1002 (2018)
Cuyt, A., Lee, W.-s., Yang, X.: On tensor decomposition, sparse interpolation and Padé approximation. Jaen J. Approx. 8, 33–58 (2016)
Dragotti, P.L., Vetterli, M., Blu, T.: Sampling moments and reconstructing signals of finite rate of innovation: Shannon meets Strang–Fix. IEEE Trans. Signal Process. 55, 1741–1757 (2007)
Gilewicz, J.: Approximants De Padé. Number 667 in Lecture Notes in Mathematics. Springer, New York (1978)
Golub, G.H., Milanfar, P., Varah, J.: A stable numerical method for inverting shape from moments. SIAM J. Sci Comput. 21, 1222–1243 (1999)
Hall, M.: Combinatorial Theory. Blaisdell, Waltham, Mass. (1967)
Hua, Y., Sarkar, T.K.: Matrix pencil method for estimating parameters of exponentially damped/undamped sinusoids in noise. IEEE Trans. Acoust. Speech Signal Process. 38, 814–824 (1990)
Peter, T., Plonka, G.: A generalized Prony method for reconstruction of sparse sums of eigenfunctions of linear operators. Inverse Problems 29. Article 025001 (2013)
Plonka, G., Tasche, M.: Prony methods for recovery of structured functions. GAMM–Mitt. 37, 239–258 (2014)
Potts, D., Tasche, M.: Parameter estimation for nonincreasing exponential sums by Prony-like methods. Linear Algebra Appl. 439, 1024–1039 (2013)
Potts, D., Tasche, M.: Fast ESPRIT algorithms based on partial singular value decompositions. Appl. Numer. Math. 88, 31–45 (2015)
de Prony, R.: Essai expérimental et analytique: sur les lois de la dilatabilité de fluides élastiques et sur celles de la force expansive de la vapeur de l’eau et de la vapeur de l’alkool, à différentes températures. Journal de l’École Polytechnique Paris 1, 24–76 (1795)
Roy, R., Kailath, T.: ESPRIT - estimation of signal parameters via rotational invariance techniques. IEEE Trans. Acoust. Speech Signal Process. 37, 984–994 (1989)
Schmidt, R.O.: A Signal Subspace Approach to Multiple Emitter Location and Spectral Estimation. Ph.D. thesis, Stanford University (1981)
Sidi, A.: Interpolation at equidistant points by a sum of exponential functions. J. Approx. Theory 34, 194–210 (1982)
Sidi, A.: Interpolation by a sum of exponential functions when some exponents are preassigned. J. Math. Anal. Appl. 112, 151–164 (1985)
Sidi, A.: Rational approximations from power series of vector-valued meromorphic functions. J. Approx. Theory 77, 89–111 (1994)
Sidi, A.: Application of vector-valued rational approximation to the matrix eigenvalue problem and connections with Krylov subspace methods. SIAM J Matrix Anal. Appl. 16, 1341–1369 (1995)
Sidi, A.: Practical Extrapolation Methods: Theory and Applications. Number 10 in Cambridge Monographs on Applied and Computational Mathematics. Cambridge University Press, Cambridge (2003)
Sidi, A.: Vector Extrapolation Methods with Applications. Number 17 in SIAM Series on Computational Science and Engineering. SIAM, Philadelphia (2017)
Sidi, A.: On the analytical structure of a vector sequence generated via a linear recursion. Technical Report CS-2018-03, Computer Science Dept., Technion–Israel Institute of Technology (2018)
Thefethen, L.N.: Approximation Theory and Approximation Practice. SIAM, Philadelphia (2013)
Weiss, L., McDonough, R.: Prony’s method, Z-transforms, and Padé approximation. SIAM Rev. 5, 145–149 (1963)
Wu, B., Li, Z., Li, S.: The implementation of a vector-valued rational approximate method in structural reanalysis problems. Comput. Methods Appl. Mech. Engrg. 192, 1773–1784 (2003)
Wu, B., Zhong, H.: Application of vector-valued rational approximations to a class of non-linear oscillations. Intern. J. Non-Linear Mech. 38, 249–254 (2003)
Acknowledgments
The author would like to thank Mr. Eitan Kaminski for carrying out the computations for the examples in Section 6.
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by: Lothar Reichel
Publisher’s note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Sidi, A. Vector versions of Prony’s algorithm and vector-valued rational approximations. Adv Comput Math 46, 30 (2020). https://doi.org/10.1007/s10444-020-09751-9
Received:
Accepted:
Published:
DOI: https://doi.org/10.1007/s10444-020-09751-9