×

zbMATH — the first resource for mathematics

Learning algebraic decompositions using Prony structures. (English) Zbl 1442.13091
The recovery of a structured function from sampled data is a fundamental problem in signal processing. The classical Prony method recovers all parameters of a univariate exponential sum from sampled data. Up to now, several variants and multivariate generalizations of the classical Prony method are known.
In this paper, the authors analyze the purely algebraic nature of Prony’s reconstruction method. Therefore they introduce a general algebraic framework called Prony structures for reconstruction methods. This new approach allows a simultaneous treatment of decomposition problems for multivariate exponential sums, for multivariate polynomials, multivariate Gaussian sums, spherical harmonic sums, and eigenfunction sums.
MSC:
13P25 Applications of commutative algebra (e.g., to statistics, control theory, optimization, etc.)
94A12 Signal theory (characterization, reconstruction, filtering, etc.)
13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
15B05 Toeplitz, Cauchy, and related matrices
30E05 Moment problems and interpolation problems in the complex plane
Software:
FOXBOX
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Adámek, J.; Herrlich, H.; Strecker, G. E., Abstract and Concrete Categories—The Joy of Cats (1990), John Wiley & Sons, Inc.: John Wiley & Sons, Inc. New York, Chichester, Brisbane, Toronto, Singapore, Revised (2004/2005) version available online at · Zbl 0695.18001
[2] Arnold, A.; Giesbrecht, M.; Roche, D. S., Faster sparse multivariate polynomial interpolation of straight-line programs, J. Symb. Comput., 75, 4-24 (July 2016), Special issue on the conference ISSAC 2014: Symbolic computation and computer algebra
[3] Batenkov, D.; Yomdin, Y., Geometry and singularities of the Prony mapping, Proceedings of the 12th International Workshop on Singularities. Proceedings of the 12th International Workshop on Singularities, São Carlos, 2012. Proceedings of the 12th International Workshop on Singularities. Proceedings of the 12th International Workshop on Singularities, São Carlos, 2012, J. Singul., 10, 1-25 (2014) · Zbl 1353.94014
[4] Ben-Or, M.; Tiwari, P., A deterministic algorithm for sparse multivariate polynomial interpolation, (STOC’88 Proceedings of the Twentieth annual ACM Symposium on Theory of Computing. STOC’88 Proceedings of the Twentieth annual ACM Symposium on Theory of Computing, Chicago, May 02-04 (1988), ACM: ACM New York), 301-309
[5] Brachat, J.; Comon, P.; Mourrain, B.; Tsigaridas, E., Symmetric tensor decomposition, Linear Algebra Appl., 433, 11-12, 1851-1872 (December 2010)
[6] Clausen, M.; Dress, A.; Grabmeier, J.; Karpinski, M., On zero-testing and interpolation of k-sparse multivariate polynomials over finite fields, Theor. Comput. Sci., 84, 2, 151-164 (July 1991)
[7] Collowald, M.; Hubert, E., A moment matrix approach to computing symmetric cubatures (November 2015), 139 pages
[8] Collowald, M.; Hubert, E., Algorithms for computing cubatures based on moment theory, Stud. Appl. Math., 141, 4, 501-546 (November 2018)
[9] Cox, D. A.; Little, J.; O’Shea, D., Ideals, Varieties, and Algorithms (2015), Springer-Verlag: Springer-Verlag Cham, Heidelberg, New York, Dordrecht, London
[10] Cuyt, A., How well can the concept of Padé approximant be generalized to the multivariate case?, J. Comput. Appl. Math., 105, 1-2, 25-50 (1999) · Zbl 0945.41012
[11] Cuyt, A.; Lee, W.-s., Sparse interpolation of multivariate rational functions, Theor. Comput. Sci., 412, 16, 1445-1456 (April 2011)
[12] Cuyt, A.; Lee, W.-s., Multivariate exponential analysis from the minimal number of samples, Adv. Comput. Math., 44, 4, 987-1002 (August 2018)
[13] Díaz, A.; FoxBox, E. Kaltofen, A system for manipulating symbolic objects in black box representation, (ISSAC’98: Proceedings of the 1998 International Symposium on Symbolic and Algebraic Computation. ISSAC’98: Proceedings of the 1998 International Symposium on Symbolic and Algebraic Computation, Rostock (August 1998), ACM: ACM New York), 30-37 · Zbl 0918.68049
[14] Diederichs, B.; Iske, A., Parameter estimation for bivariate exponential sums, (Proceedings of the 11th International Conference on Sampling Theory and Applications. Proceedings of the 11th International Conference on Sampling Theory and Applications, D.C. Washington, May 25-29 (2015)), 493-497
[15] Diederichs, B.; Iske, A., Projection-based multivariate frequency estimation, (Proceedings of the 12th International Conference on Sampling Theory and Applications. Proceedings of the 12th International Conference on Sampling Theory and Applications, Tallinn, Estonia, July 3-7 (2017)), 360-363
[16] Dress, A.; Grabmeier, J., The interpolation problem for k-sparse polynomials and character sums, Adv. Appl. Math., 12, 1, 57-75 (March 1991)
[17] Ehler, M.; Kunis, S.; Peter, T.; Richter, C., A randomized multivariate matrix pencil method for superresolution microscopy, Electron. Trans. Numer. Anal., 51, 63-74 (2019) · Zbl 1436.65219
[18] Gallier, J.; Quaintance, J., Differential Geometry and Lie Groups: A Second Course, Geometry and Computing, vol. 13 (2020), Springer-Verlag, to appear
[19] Garg, S.; Schost, É., Interpolation of polynomials given by straight-line programs, Theor. Comput. Sci., 410, 27-29, 2659-2662 (June 2009)
[20] Grigoriev, D. Y.; Karpinski, M.; Singer, M. F., The interpolation problem for k-sparse sums of eigenfunctions of operators, Adv. Appl. Math., 12, 1, 76-81 (March 1991)
[21] Henrici, P., Applied and Computational Complex Analysis, Volume 1 (1974), John Wiley & Sons, Inc.: John Wiley & Sons, Inc. New York, London, Sydney, Toronto
[22] Horn, R. A.; Johnson, C. R., Matrix Analysis (2013), Cambridge University Press: Cambridge University Press Cambridge, New York, Melbourne, Madrid, Cape Town, Singapore, São Paulo, Delhi, Mexico City · Zbl 1267.15001
[23] Hubert, E.; Singer, M. F., Sparse interpolation in terms of multivariate Chebyshev polynomials (January 2020), 50 pages
[24] Imamoglu, E.; Kaltofen, E.; Yang, Z., Sparse polynomial interpolation with arbitrary orthogonal polynomial bases, (ISSAC’18: Proceedings of the 2018 International Symposium on Symbolic and Algebraic Computation. ISSAC’18: Proceedings of the 2018 International Symposium on Symbolic and Algebraic Computation, New York (July 2018), ACM: ACM New York), 223-230
[25] Josz, C.; Lasserre, J. B.; Mourrain, B., Sparse polynomial interpolation: sparse recovery, super-resolution, or Prony?, Adv. Comput. Math., 45, 3, 1401-1437 (June 2019)
[26] Kaltofen, E.; Lee, W.-s., Early termination in sparse interpolation algorithms, J. Symb. Comput., 36, 3-4, 365-400 (September-October 2003)
[27] Kaltofen, E.; Yang, Z., On exact and approximate interpolation of sparse rational functions, (ISSAC’07: Proceedings of the 2007 International Symposium on Symbolic and Algebraic Computation. ISSAC’07: Proceedings of the 2007 International Symposium on Symbolic and Algebraic Computation, Waterloo, Ontario (July 2007), ACM: ACM New York), 203-210 · Zbl 1190.65019
[28] Kreuzer, M.; Robbiano, L., Computational Commutative Algebra 2 (2005), Springer-Verlag: Springer-Verlag Berlin, Heidelberg, New York · Zbl 1090.13021
[29] Kunis, S.; Möller, H. M.; Peter, T.; von der Ohe, U., Prony’s method under an almost sharp multivariate Ingham inequality, J. Fourier Anal. Appl., 24, 5, 1306-1318 (October 2018)
[30] Kunis, S.; Möller, H. M.; von der Ohe, U., Prony’s method on the sphere, SMAI J. Comput. Math., 5, 87-97 (2019) · Zbl 07198657
[31] Kunis, S.; Peter, T.; Römer, T.; von der Ohe, U., A multivariate generalization of Prony’s method, Linear Algebra Appl., 490, 31-47 (February 2016)
[32] Lakshman, Y. N.; Saunders, B. D., Sparse polynomial interpolation in nonstandard bases, SIAM J. Comput., 24, 2, 387-397 (April 1995)
[33] Lee, W.-s., From quotient-difference to generalized eigenvalues and sparse polynomial interpolation, (SNC’07: Proceedings of the 2007 International Workshop on Symbolic-Numeric Computation (2007), ACM: ACM New York), 110-116
[34] Mac Lane, S., Categories for the Working Mathematician, Graduate Texts in Mathematics, vol. 5 (1998), Springer-Verlag: Springer-Verlag New York, Berlin, Heidelberg, Barcelona, Budapest, Hong Kong, London, Milan, Paris, Singapore, Tokyo · Zbl 0906.18001
[35] H.M. Möller, A note on zero-dimensional radicals, unpublished note, November 2017.
[36] Mourrain, B., Polynomial-exponential decomposition from moments, Found. Comput. Math., 18, 6, 1435-1492 (December 2018)
[37] Peter, T.; Plonka, G., A generalized Prony method for reconstruction of sparse sums of eigenfunctions of linear operators, Inverse Probl., 29, 2, 1-21 (January 2013)
[38] Peter, T.; Plonka, G.; Schaback, R., Prony’s method for multivariate signals, Proc. Appl. Math. Mech., 15, 1, 665-666 (2015)
[39] Peter, T.; Potts, D.; Tasche, M., Nonlinear approximation by sums of exponentials and translates, SIAM J. Sci. Comput., 33, 4, 1920-1947 (2011) · Zbl 1243.65166
[40] Plonka, G.; Potts, D.; Steidl, G.; Tasche, M., Numerical Fourier Analysis, Applied and Numerical Harmonic Analysis, vol. 90 (2018), Birkhäuser/Springer Nature Switzerland AG: Birkhäuser/Springer Nature Switzerland AG Cham, Switzerland
[41] Potts, D.; Tasche, M., Parameter estimation for exponential sums by approximate Prony method, Signal Process., 90, 5, 1631-1642 (May 2010)
[42] Potts, D.; Tasche, M., Parameter estimation for multivariate exponential sums, Electron. Trans. Numer. Anal., 40, 204-224 (July 2013)
[43] Potts, D.; Tasche, M., Parameter estimation for nonincreasing exponential sums by Prony-like methods, Linear Algebra Appl., 439, 4, 1024-1039 (August 2013)
[44] Potts, D.; Tasche, M., Sparse polynomial interpolation in Chebyshev bases, Linear Algebra Appl., 441, 61-87 (January 2014)
[45] Riche, G. C.F. M.; de Prony, baron, Essai expérimental et analytique: Sur les lois de la Dilatabilité des 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, J. Éc. Polytech., 2, 24-76 (1795)
[46] Sauer, T., Prony’s method in several variables, Numer. Math., 136, 2, 411-438 (2017) · Zbl 1377.65048
[47] Sauer, T., Prony’s method in several variables: symbolic solutions by universal interpolation, J. Symb. Comput., 84, 95-112 (January-February 2018)
[48] Saxena, N., Progress on polynomial identity testing, Bull. Eur. Assoc. Theor. Comput. Sci., 99, 49-79 (October 2009)
[49] Saxena, N., Progress on polynomial identity testing-II, (Agrawal, M.; Arvind, V., Perspectives in Computational Complexity. Perspectives in Computational Complexity, Progress in Computer Science and Applied Logic, vol. 26 (2014), Springer International Publishing: Springer International Publishing Switzerland, Cham, Heidelberg, New York, Dordrecht, London), 131-146, Chapter 7 · Zbl 1345.68182
[50] Shpilka, A.; Yehudayoff, A., Arithmetic circuits: a survey of recent results and open questions, Found. Trends Theor. Comput. Sci., 5, 3-4, 207-388 (December 2010)
[51] Sidi, A., Interpolation at equidistant points by a sum of exponential functions, J. Approx. Theory, 34, 2, 194-210 (February 1982)
[52] Stampfer, K.; Plonka, G., The generalized operator based Prony method, Constr. Approx. (2020), in press
[53] Sylvester, J. J., An Essay on Canonical Forms, Supplement to a Sketch of a Memoir on Elimination, Transformation and Canonical Forms (1851), George Bell: George Bell Fleet Street, Reprinted in [55, Paper 34]
[54] Sylvester, J. J., On a remarkable discovery in the theory of canonical forms and of hyperdeterminants, Philos. Mag., 4, 2, 391-410 (1851), Reprinted in [55, Paper 41]
[55] Sylvester, J. J., The Collected Mathematical Papers of James Joseph Sylvester Volume I (1837-1853) (1904), Cambridge University Press: Cambridge University Press Cambridge
[56] von der Ohe, U., On the reconstruction of multivariate exponential sums (December 2017), Osnabrück University: Osnabrück University Germany, 92 pages, available online at
[57] Weiss, L.; McDonough, R. N., Prony’s method, z-transforms, and Padé approximation, SIAM Rev., 5, 2, 145-149 (1963) · Zbl 0114.32805
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.