×

Polynomial-exponential decomposition from moments. (English) Zbl 1427.14119

A classical problem going back some centuries ago (see for instance [Baron Gaspard de Prony, “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’alcool, à différentes températures”, J. École Polytechnique 1, 24–76 (1795)]) is the following: given a function \(h\in C^\infty({\mathbb R},{\mathbb C})\) of the form \[ h(x)=\sum_{i=1}^r \omega_ie^{f_ix}=\sum_{j=0}^\infty h_j\frac{x^j}{j!}, \] recover the distinct frequences \(f_1,\ldots, f_r\) and the coefficients \(\omega_1,\ldots, \omega_r\) given a finite set of “moments” \(h_0,\ldots, h_m\). This problem also has an “approximation” variant: given some moments of any smooth function \(h(x)\) compute a representation of the form \(\sum_{i=1}^r \omega_ie^{f_ix}\) which “best” fit the function.
The resolution proposed in [N. E. Golyandina and K. D Usevich, in: Matrix methods. Theory, algorithms and applications. Dedicated to the memory of Gene Golub. Based on the 2nd international conference on matrix methods and operator equations, Moscow, Russia, July 23–27, 2007. Hackensack, NJ: World Scientific. 449–473 (2010; Zbl 1216.94012)] involves the use of Hankel matrices made from the input data, and eigenvalue decomposition. The generalization of this problem to the multivariate setting is straightforward, and several approaches have been proposed to tackle it, see [F. Andersson et al., Appl. Comput. Harmon. Anal. 29, No. 2, 198–213 (2010; Zbl 1196.42034); S. Kunis et al., Linear Algebra Appl. 490, 31–47 (2016; Zbl 1329.65312); D. Potts and M. Tasche, ETNA, Electron. Trans. Numer. Anal. 40, 204–224 (2013; Zbl 1305.65093)]. Also, the study of Hankel operators of finite rank in the multivariate case has been extensively studied, see for instance [C. Gu, Linear Algebra Appl. 288, No. 1–3, 269–281 (1999; Zbl 0947.47022); S. C. Power, Linear Algebra Appl. 48, 237–244 (1982; Zbl 0513.15007)].
The paper under review uses duality theory for polynomial systems introduced by F. S. Macaulay in [The algebraic theory of modular systems. With a new introduction by Paul Roberts. Reprint of the 1916 orig. Cambridge: Cambridge University Press (1994; Zbl 0802.13001; JFM 46.0167.01)] to generalize the classical challenge and tackle both multivariate problems. Via this duality, multivariate series of the form \(h(\mathbf{x})= \sum_{\alpha\in{\mathbb N}^n}\omega_\alpha\frac{\mathbf{x}^\alpha}{\alpha!}\) can be seen as elements in the dual space of an ideal of multivariate polynomials being “anihilated” by them. And the Hankel operator defined by it is of finite rank if and only it corresponds to “polynomial-exponential” series, i.e. there exist polynomials \(\omega_1(\mathbf{x}),\ldots, \omega_r(\mathbf{x})\in{\mathbb C}[x_1,\ldots, x_n]\) and \(\mathbf{\xi}_1,\ldots, \mathbf{\xi}_r\in{\mathbb C}^n\) with \(\mathbf{\xi}_i=(\xi_{i1},\ldots, \xi_{in}),\) such that \[ h(\mathbf{x}) = \sum_{i=1}^r \omega_i(\mathbf{x}) e^{\xi_{i1}x_1+\ldots\xi_{in} x_n}. \]
It is shown that such polynomial-exponential series correspond – in the algebraic language – to Artinian Gorenstein Algebras, and to decompose them from their first moments, very fine tools from computational algebra are used to compute bases of these Algebras and perform operations in them. As by-products of these approach, Kronecker-type theorems for convolution operators and for the reconstruction of measures as weighted sums of Dirac measures from moments are provided, and a new approach for the sparse interpolation of polylog functions from values is presented.

MSC:

14Q20 Effectivity, complexity and computational aspects of algebraic geometry
68W30 Symbolic computation and algebraic computation
47B35 Toeplitz operators, Hankel operators, Wiener-Hopf operators
15B05 Toeplitz, Cauchy, and related matrices
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Encyclopedia of Mathematics, April 2016.
[2] Naum I. Ahiezer and Mark G. Kreĭn. Some Questions in the Theory of Moments. American Mathematical Society, Providence, 1962.
[3] Andersson, Fredrik; Carlsson, Marcus, On General Domain Truncated Correlation and Convolution Operators with Finite Rank, Integral Equations and Operator Theory, 82, 339-370, (2015) · Zbl 1335.47014 · doi:10.1007/s00020-015-2217-6
[4] Fredrik Andersson and Marcus Carlsson. On the structure of positive semi-definite finite rank general domain Hankel and Toeplitz operators in several variables. Complex Analysis and Operator Theory, 11(4):755-784, 2017. · Zbl 1480.47038
[5] Andersson, Fredrik; Carlsson, Marcus; Hoop, Maarten V., Nonlinear approximation of functions in two dimensions by sums of wave packets, Appl. Comput. Harmon. Anal., 29, 198-213, (2010) · Zbl 1196.42034 · doi:10.1016/j.acha.2009.09.001
[6] George A. Baker and Peter Graves-Morris. Padé Approximants. Cambridge University Press, Cambridge England, New York, 2nd edition, 1996. · Zbl 0923.41001
[7] Barachart, Laurent, Sur la réalisation de Nerode des systèmes multi-indiciels, C. R. Acad. Sc. Paris, 301, 715-718, (1984) · Zbl 0589.93010
[8] Batenkov, Dmitry; Yomdin, Yosef, On the accuracy of solving confluent Prony systems, SIAM Journal on Applied Mathematics, 73, 134-154, (2013) · Zbl 1269.65047 · doi:10.1137/110836584
[9] Beckermann, Bernhard; Golub, Gene H.; Labahn, George, On the numerical condition of a generalized Hankel eigenvalue problem, Numerische Mathematik, 106, 41-68, (2007) · Zbl 1121.65036 · doi:10.1007/s00211-006-0054-x
[10] Beckermann, Bernhard; Labahn, George, A uniform approach for the fast computation of matrix-type Padé approximants, SIAM Journal on Matrix Analysis and Applications, 15, 804-823, (1994) · Zbl 0805.65008 · doi:10.1137/S0895479892230031
[11] Michael Ben-Or and Prasson Tiwari. A deterministic algorithm for sparse multivariate polynomial interpolation. In Proceedings of the twentieth annual ACM symposium on Theory of computing, STOC ’88, pages 301-309, New York, NY, USA, 1988. ACM.
[12] Berlekamp, Elwyn R., Nonbinary BCH decoding, IEEE Transactions on Information Theory, 14, 242-242, (1968) · doi:10.1109/TIT.1968.1054109
[13] Bernardi, Alessandra; Brachat, Jérôme; Comon, Pierre; Mourrain, Bernard, General tensor decomposition, moment matrices and applications, Journal of Symbolic Computation, 52, 51-71, (2013) · Zbl 1275.15017 · doi:10.1016/j.jsc.2012.05.012
[14] Jérémy Berthomieu, Brice Boyer, and Jean-Charles Faugère. Linear Algebra for Computing Gröbner Bases of Linear Recursive Multidimensional Sequences. In International Symposium on Symolic and Algebraic Compution, pages 61-68. ACM Press, 2015. · Zbl 1346.68269
[15] Beylkin, Gregory; Monzón, Lucas, On approximation of functions by exponential sums, Appl. Comput. Harmon. Anal., 19, 17-48, (2005) · Zbl 1075.65022 · doi:10.1016/j.acha.2005.01.003
[16] Brachat, Jérome; Comon, Pierre; Mourrain, Bernard; Tsigaridas, Elias, Symmetric tensor decomposition, Linear Algebra and Applications, 433, 1851-1872, (2010) · Zbl 1206.65141 · doi:10.1016/j.laa.2010.06.046
[17] Candès, Emmanuel J.; Romberg, Justin; Tao, Terence, Stable signal recovery from incomplete and inaccurate measurements, Communications on Pure and Applied Mathematics, 59, 1207-1223, (2006) · Zbl 1098.94009 · doi:10.1002/cpa.20124
[18] Constantin Carathéodory and Lipòt Fejér. Über den Zusammenhang der Extremen von Harmonischen Funktionen mit Ihren Koeffizienten und Über den Picard-Landauschen Satz. In Rendiconti del Circolo Matematico di Palermo (1884-1940), volume 32, pages 218-239. 1911.
[19] David A. Cox, John Little, and Donal O’Shea. Ideals, Varieties, and Algorithms. Undergraduate Texts in Mathematics. Springer, 1992. · Zbl 0756.13017 · doi:10.1007/978-1-4757-2181-2
[20] Raul E. Curto and Lawrence A. Fialkow. Solution of the Truncated Complex Moment Problem for Flat Data. Amer Mathematical Society, Providence, R.I, January 1996. · Zbl 0876.30033
[21] Cuyt, Annie, How well can the concept of Padé approximant be generalized to the multivariate case?, Journal of Computational and Applied Mathematics, 105, 25-50, (1999) · Zbl 0945.41012 · doi:10.1016/S0377-0427(99)00028-X
[22] Riche de Prony, Baron Gaspard, 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’alcool, à différentes températures, J. École Polytechnique, 1, 24-76, (1795)
[23] David Eisunbud. Commutative Algebra: With a View toward Algebraic Geometry, volume 150 of Graduate Texts in Mathematics. Springer-Verlag, 1994.
[24] Mohamed Elkadi and Bernard Mourrain. Introduction à la résolution des systèmes polynomiaux, volume 59 of Mathématiques & Applications. Springer, Berlin, 2007. · Zbl 1127.13001 · doi:10.1007/978-3-540-71647-1
[25] Emsalem, Jacques, Géométrie des points épais, Bulletin de la S.M.F., 106, 399-416, (1978) · Zbl 0396.13017
[26] Fischer, Ernst, Über das Carathéodory’sche Problem, Potenzreihen mit positivem reellen Teil betreffend, Rendiconti del Circolo Matematico di Palermo (1884-1940), 32, 240-256, (1911) · JFM 42.0277.03 · doi:10.1007/BF03014797
[27] Fitzpatrick, Patrick; Norton, Graham H., Finding a basis for the characteristic ideal of an n-dimensional linear recurring sequence, IEEE Transactions on Information Theory, 36, 1480-1487, (1990) · Zbl 0713.94012 · doi:10.1109/18.59953
[28] Fliess, Michel, Séries reconnaissables, rationnelles et algébriques, Bulletin des Sciences Mathématiques. Deuxième Série, 94, 231-239, (1970) · Zbl 0219.16003
[29] Giesbrecht, Mark; Labahn, George; Lee, Wen-shin, Symbolic-numeric sparse interpolation of multivariate polynomials, J. Symb. Comput., 44, 943-959, (2009) · Zbl 1167.65003 · doi:10.1016/j.jsc.2008.11.003
[30] Golub, Gene; Pereyra, Victor, Separable nonlinear least squares: The variable projection method and its applications, Inverse Problems, 19, r1-r26, (2003) · Zbl 1022.65014 · doi:10.1088/0266-5611/19/2/201
[31] N. E. Golyandina and K. D. Usevich. 2D-Extension of Singular Spectrum Analysis: Algorithm and Elements of Theory. In Matrix Methods: Theory, Algorithms and Applications, pages 449-473. World Scientific Publishing, 2010. · Zbl 1216.94012
[32] Stef Graillat and Philippe Trébuchet. A new algorithm for computing certified numerical approximations of the roots of a zero-dimensional system. In Proceedings of the 2009 International Symposium on Symbolic and Algebraic Computation, pages 167-174. ACM, 2009. · Zbl 1237.65046
[33] Wolfgang Gröbner. Über das Macaulaysche inverse System und dessen Bedeutung für die Theorie der linearen Differentialgleichungen mit konstanten Koeffizienten. In Abhandlungen Aus Dem Mathematischen Seminar Der Universität Hamburg, volume 12, Issue 1, pages 127-132. Springer, 1937.
[34] Caixing, Gu, Finite rank Hankel operators on the polydisk, Linear Algebra and its Applications, 288, 269-281, (1999) · Zbl 0947.47022 · doi:10.1016/S0024-3795(98)10223-9
[35] Hakopian, Hakop A.; Tonoyan, Mariam G., Partial differential analogs of ordinary differential equations and systems, New York J. Math, 10, 89-116, (2004) · Zbl 1073.35182
[36] Lars Hormander. An Introduction to Complex Analysis in Several Variables, volume 7. North Holland, Amsterdam; New York; N.Y., U.S.A., 3rd edition, 1990. · Zbl 0685.32001
[37] Anthony Iarrobino and Vassil Kanev. Power Sums, Gorenstein Algebras, and Determinantal Loci. Lecture Notes in Mathematics. Springer, 1999. · Zbl 0942.14026 · doi:10.1007/BFb0093426
[38] Leopold Kronecker. Zur Theorie der Elimination Einer Variabeln aus Zwei Algebraischen Gleichungen. pages 535-600, 1880. · JFM 13.0114.02
[39] Kunis, Stefan; Peter, Thomas; Römer, Tim; Ohe, Ulrich, A multivariate generalization of Prony’s method, Linear Algebra and its Applications, 490, 31-47, (2016) · Zbl 1329.65312 · doi:10.1016/j.laa.2015.10.023
[40] Lasserre, Jean-Bernard; Laurent, Monique; Mourrain, Bernard; Rostalski, Philipp; Trébuchet, Philippe, Moment matrices, border bases and real radical computation, Journal of Symbolic Computation, 51, 63-85, (2013) · Zbl 1276.13021 · doi:10.1016/j.jsc.2012.03.007
[41] Monique Laurent. Sums of squares, moment matrices and optimization over polynomials. In Emerging Applications of Algebraic Geometry, IMA Volumes in Mathematics and Its Applications, volume 149, pages 157-270. Springer, New York, 2009. · Zbl 1163.13021
[42] Laurent, Monique; Mourrain, Bernard, A generalized flat extension theorem for moment matrices, Archiv der Mathematik, 93, 87-98, (2009) · Zbl 1183.30030 · doi:10.1007/s00013-009-0007-6
[43] Lim, Lek-Heng; Comon, Pierre, Blind multilinear identification, IEEE Transactions on Information Theory, 60, 1260-1280, (2014) · Zbl 1364.94139 · doi:10.1109/TIT.2013.2291876
[44] Francis S. Macaulay. The Algebraic Theory of Modular Systems. Cambridge University Press, 1916.
[45] Jessie F. MacWilliams and Neil J. A. Sloane. The Theory of Error-Correcting Codes, Volume 16. North Holland Publishing Co., 1977. · Zbl 0369.94008
[46] Malgrange, Bernard, Existence et approximation des solutions des équations aux dérivées partielles et des équations de convolution, Annales de l’institut Fourier, 6, 271-355, (1956) · Zbl 0071.09002 · doi:10.5802/aif.65
[47] Massey, James, Shift-register synthesis and BCH decoding, IEEE transactions on Information Theory, 15, 122-127, (1969) · Zbl 0167.18101 · doi:10.1109/TIT.1969.1054260
[48] Mourrain, Bernard, Isolated points, duality and residues, J. of Pure and Applied Algebra, 117&118, 469-493, (1996) · Zbl 0896.13020
[49] Bernard Mourrain. A new criterion for normal form algorithms. In M. Fossorier, H. Imai, Shu Lin, and A. Poli, editors, Proc. AAECC, volume 1719 of LNCS, pages 430-443. Springer, Berlin, 1999. · Zbl 0976.12005
[50] Mourrain, Bernard; Pan, Victor Y., Multivariate Polynomials, Duality, and Structured Matrices, Journal of Complexity, 16, 110-180, (2000) · Zbl 0963.68232 · doi:10.1006/jcom.1999.0530
[51] Bernard Mourrain and Philippe Trébuchet. Generalized normal forms and polynomials system solving. In M. Kauers, editor, Proc. of the International Symposium on Symbolic and Algebraic Computation (ISSAC’05), pages 253-260, 2005. · Zbl 1360.68947
[52] Oberst, Ulrich; Pauer, Franz, The Constructive Solution of Linear Systems of Partial Difference and Differential Equations with Constant Coefficients, Multidimensional Systems and Signal Processing, 12, 253-308, (2001) · Zbl 1014.35015 · doi:10.1023/A:1011901522520
[53] Pedersen, Paul S., Basis for Power Series Solutions to Systems of Linear, Constant Coefficient Partial Differential Equations, Advances in Mathematics, 141, 155-166, (1999) · Zbl 0921.35034 · doi:10.1006/aima.1998.1782
[54] Peller, Vladimir V, An excursion into the theory of Hankel operators, Holomorphic spaces (Berkeley, CA, 1995), Math. Sci. Res. Inst. Publ, 33, 65-120, (1998) · Zbl 0998.47016
[55] Victor Pereyra and Godela Scherer, editors. Exponential Data Fitting and Its Applications. Bentham Science Publisher, 2012. · Zbl 1270.65008
[56] Peter, Thomas; Plonka, Gerlind, A generalized Prony method for reconstruction of sparse sums of eigenfunctions of linear operators, Inverse Problems, 29, 025001, (2013) · Zbl 1276.47093 · doi:10.1088/0266-5611/29/2/025001
[57] Plonka, Gerlind; Tasche, Manfred, Prony methods for recovery of structured functions, GAMM-Mitteilungen, 37, 239-258, (2014) · Zbl 1311.65012 · doi:10.1002/gamm.201410011
[58] Potts, Daniel; Tasche, Manfred, Parameter estimation for exponential sums by approximate prony method, Signal Processing, 90, 1631-1642, (2010) · Zbl 1194.94128 · doi:10.1016/j.sigpro.2009.11.012
[59] Potts, Daniel; Tasche, Manfred, Parameter estimation for multivariate exponential sums, Electronic Transactions on Numerical Analysis, 40, 204-224, (2013) · Zbl 1305.65093
[60] Power, Stephen C., Finite rank multivariable Hankel forms, Linear Algebra and its Applications, 48, 237-244, (1982) · Zbl 0513.15007 · doi:10.1016/0024-3795(82)90110-0
[61] Charles Riquier. Les systèmes d’équations aux dérivées partielles, volume XXVII. Gauthier-Villars, 1910. · JFM 40.0411.01
[62] Rochberg, Richard, Toeplitz and Hankel operators on the Paley-Wiener space, Integral Equations and Operator Theory, 10, 187-235, (1987) · Zbl 0634.47024 · doi:10.1007/BF01199078
[63] Richard Roy and Thomas Kailath. ESPRIT-estimation of signal parameters via rotational invariance techniques. IEEE Transactions on Acoustics, Speech, and Signal Processing, 37(7):984-995, 1989. · doi:10.1109/29.32276
[64] Sakata, Shojiro, Finding a minimal set of linear recurring relations capable of generating a given finite two-dimensional array, Journal of Symbolic Computation, 5, 321-337, (1988) · Zbl 0647.68044 · doi:10.1016/S0747-7171(88)80033-6
[65] Sauer, Tomas, Prony’s method in several variables, Numerische Mathematik, 136, 411-438, (2017) · Zbl 1377.65048 · doi:10.1007/s00211-016-0844-8
[66] Laurent Schwartz. Théorie des distributions. Editions Hermann, Paris, 1966. · Zbl 0149.09501
[67] The MUSIC Algorithm, A. Lee Swindlehurst and Thomas Kailath. A Performance Analysis of Subspace-Based Methods in the Presence of Model Errors - Part I, IEEE Trans. on Signal Processing, 40, 1758-1774, (1992) · Zbl 0850.62267 · doi:10.1109/78.143447
[68] James Joseph Sylvester. Essay on Canonical Form. The collected mathematical papers of J. J. Sylvester, Vol. I, Paper 34, Cambridge University Press. 1909 (XV und 688). G. Bell, London, 1851.
[69] Joachim von zur Gathen and Jürgen Gerhard. Modern Computer Algebra. Cambridge University Press, 3rd edition, 2013. · Zbl 1277.68002 · doi:10.1017/CBO9781139856065
[70] Yang, Zai; Xie, Lihua; Stoica, Petre, Vandermonde Decomposition of Multilevel Toeplitz Matrices With Application to Multidimensional Super-Resolution, IEEE Transactions on Information Theory, 62, 3685-3701, (2016) · Zbl 1359.94042 · doi:10.1109/TIT.2016.2553041
[71] Richard Zippel. Probabilistic algorithms for sparse polynomials. In Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, EUROSAM ’79, pages 216-226, London, UK, 1979. Springer-Verlag. · Zbl 0418.68040
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.