Prony’s method on the sphere
The SMAI journal of computational mathematics, Volume S5 (2019), pp. 87-97.

Eigenvalue analysis based methods are well suited for the reconstruction of finitely supported measures from their moments up to a certain degree. We give a precise description when Prony’s method succeeds in terms of an interpolation condition. In particular, this allows for the unique reconstruction of a measure from its trigonometric moments whenever its support is separated and also for the reconstruction of a measure on the unit sphere from its moments with respect to spherical harmonics. Both results hold in arbitrary dimensions and also yield a certificate for popular semidefinite relaxations of these reconstruction problems in the nonnegative case.

Published online:
DOI: 10.5802/smai-jcm.53
Classification: 65T40,  42C15,  30E05,  65F30
Keywords: frequency analysis, spectral analysis, exponential sum, moment problem, super-resolution
Stefan Kunis 1; H. Michael Möller 2; Ulrich von der Ohe 3

1 Osnabrück University, Institute of Mathematics and Research Center of Cellular Nanoanalytics, Germany
2 TU Dortmund, Fakultät für Mathematik, Germany
3 University of Genova, Department of Mathematics, Italy; Marie Skłodowska-Curie fellow of the Istituto Nazionale di Alta Matematica
@article{SMAI-JCM_2019__S5__87_0,
     author = {Stefan Kunis and H.~Michael M\"oller and Ulrich von der Ohe},
     title = {Prony{\textquoteright}s method on the sphere},
     journal = {The SMAI journal of computational mathematics},
     pages = {87--97},
     publisher = {Soci\'et\'e de Math\'ematiques Appliqu\'ees et Industrielles},
     volume = {S5},
     year = {2019},
     doi = {10.5802/smai-jcm.53},
     language = {en},
     url = {https://smai-jcm.centre-mersenne.org/articles/10.5802/smai-jcm.53/}
}
TY  - JOUR
TI  - Prony’s method on the sphere
JO  - The SMAI journal of computational mathematics
PY  - 2019
DA  - 2019///
SP  - 87
EP  - 97
VL  - S5
PB  - Société de Mathématiques Appliquées et Industrielles
UR  - https://smai-jcm.centre-mersenne.org/articles/10.5802/smai-jcm.53/
UR  - https://doi.org/10.5802/smai-jcm.53
DO  - 10.5802/smai-jcm.53
LA  - en
ID  - SMAI-JCM_2019__S5__87_0
ER  - 
%0 Journal Article
%T Prony’s method on the sphere
%J The SMAI journal of computational mathematics
%D 2019
%P 87-97
%V S5
%I Société de Mathématiques Appliquées et Industrielles
%U https://doi.org/10.5802/smai-jcm.53
%R 10.5802/smai-jcm.53
%G en
%F SMAI-JCM_2019__S5__87_0
Stefan Kunis; H. Michael Möller; Ulrich von der Ohe. Prony’s method on the sphere. The SMAI journal of computational mathematics, Volume S5 (2019), pp. 87-97. doi : 10.5802/smai-jcm.53. https://smai-jcm.centre-mersenne.org/articles/10.5802/smai-jcm.53/

[1] K. Atkinson; W. Han Spherical harmonics and approximations on the unit sphere: an introduction, Lecture Notes in Mathematics, Volume 2044, Springer, 2044

[2] F. S. V. Bazán Conditioning of rectangular Vandermonde matrices with nodes in the unit disk, SIAM J. Matrix Anal. Appl., Volume 21 (1999) no. 2, pp. 679-693 | Article | MR: 1742819

[3] T. Becker; V. Weispfenning Gröbner Bases: A Computational Approach to Commutative Algebra, Springer, 1993 | Zbl: 0772.13010

[4] T. Bendory; S. Dekel; A. Feuer Exact recovery of Dirac ensembles from the projection onto spaces of spherical harmonics, Constr. Approx., Volume 42 (2015) no. 2, pp. 183-207 | Article | MR: 3392487 | Zbl: 1329.33017

[5] T. Bendory; S. Dekel; A. Feuer Super-resolution on the sphere using convex optimization, IEEE Trans. Signal Process., Volume 64 (2015), pp. 2253-2262 | Article | MR: 3331998 | Zbl: 1394.94072

[6] K. Bredies; H. K. Pikkarainen Inverse problems in spaces of measures, ESAIM, Control Optim. Calc. Var., Volume 19 (2013), pp. 190-218 | Article | Numdam | MR: 3023066

[7] E. J. Candès; C. Fernandez-Granda Super-resolution from noisy data, J. Fourier Anal. Appl., Volume 19 (2013) no. 6, pp. 1229-1254 | Article | MR: 3132912 | Zbl: 1312.94015

[8] E. J. Candès; C. Fernandez-Granda Towards a mathematical theory of super-resolution, Commun. Pure Appl. Math., Volume 67 (2014) no. 6, pp. 906-956 | Article | MR: 3193963 | Zbl: 1350.94011

[9] D. Cox; J. Little; D. O’Shea Ideals, Varieties, and Algorithms, Springer, 2007

[10] R. Curto; L. A. Fialkow The truncated complex K-moment problem, Trans. Am. Math. Soc., Volume 352 (2000), pp. 2825-2855 | Article | MR: 1661305 | Zbl: 0955.47011

[11] S. Deslauriers-Gauthier; P. Marziliano Sampling signals with a finite rate of innovation on the sphere, IEEE Trans. Signal Process., Volume 61 (2013) no. 18, pp. 4552-4561 | Article | MR: 3096698 | Zbl: 1393.94679

[12] I. Dokmani; Y. M. Lu Sampling sparse signals on the sphere: Algorithms and applications, IEEE Trans. Signal Process., Volume 64 (2016) no. 1, pp. 189-202 | Article | MR: 3432971

[13] B. Dumitrescu Positive trigonometric polynomials and signal processing applications, Signals and Communication Technology, Springer, 2007 | Zbl: 1126.93005

[14] V. Duval; G. Peyré Exact support recovery for sparse spikes deconvolution, Found. Comput. Math., Volume 15 (2015), pp. 1315-1355 | Article | MR: 3394712 | Zbl: 1327.65104

[15] C. Fassino; H. M. Möller Multivariate polynomial interpolation with perturbed data, Numer. Algorithms, Volume 71 (2016), pp. 273-292 | Article | MR: 3452931 | Zbl: 1334.65026

[16] F. Filbir; K. Schröder Exact recovery of discrete measures from Wigner D-moments (2016) (https://arxiv.org/abs/1606.05306)

[17] R. A. Horn; C. R. Johnson Matrix Analysis, Cambridge University Press, 2013 | Zbl: 1267.15001

[18] C. Josz; J. B. Lasserre; B. Mourrain Sparse polynomial interpolation: sparse recovery, super-resolution, or Prony?, Adv. Comput. Math., Volume 45 (2018) no. 3, pp. 1401-1437 | Article | MR: 3955723 | Zbl: 1417.90112

[19] V. Komornik; P. Loreti Fourier Series in Control Theory, Springer, 2004

[20] M. Kreuzer; L. Robbiano Computational Commutative Algebra 1, Springer, 2000 | Article | Zbl: 0956.13008

[21] S. Kunis A note on stability results for scattered data interpolation on Euclidean spheres, Adv. Comput. Math., Volume 30 (2009), pp. 303-314 | Article | MR: 2495788 | Zbl: 1165.65006

[22] S. Kunis; H. M. Möller; T. Peter; U. von der Ohe Prony’s method under an almost sharp multivariate Ingham inequality, J. Fourier Anal. Appl., Volume 24 (2018) no. 5, pp. 1306-1318 | Article | MR: 3856230 | Zbl: 1397.65324

[23] S. Kunis; T. Peter; T. Römer; U. von der Ohe A multivariate generalization of Prony’s method, Linear Algebra Appl., Volume 490 (2016), pp. 31-47 | Article | MR: 3429031 | Zbl: 1329.65312

[24] S. Kunis; D. Potts Stability results for scattered data interpolation by trigonometric polynomials, SIAM J. Sci. Comput., Volume 29 (2007), pp. 1403-1419 | Article | MR: 2341793 | Zbl: 1146.65016

[25] S. Kunis; T. Römer; U. von der Ohe Learning algebraic decompositions using Prony structures (2019) (https://arxiv.org/abs/1907.01547)

[26] M. Laurent; B. Mourrain A generalized flat extension theorem for moment matrices, Arch. Math., Volume 93 (2009) no. 1, pp. 87-98 | Article | MR: 2520647 | Zbl: 1183.30030

[27] W. Liao MUSIC for multidimensional spectral estimation: stability and super-resolution, IEEE Trans. Signal Process., Volume 63 (2015) no. 23, pp. 6395-6406 | Article | MR: 3421047 | Zbl: 1395.94138

[28] J. Marzo; B. Pridhnani Sufficient conditions for sampling and interpolation on the sphere, Constr. Approx., Volume 40 (2014) no. 2, pp. 241-257 | Article | MR: 3254619 | Zbl: 1306.41003

[29] A. Moitra Super-resolution, extremal functions and the condition number of Vandermonde matrices, Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing (STOC ’15) (2015), pp. 821-830 | Article | MR: 3388262 | Zbl: 1321.68421

[30] B. Mourrain Polynomial–exponential decomposition from moments, Found. Comput. Math., Volume 18 (2018) no. 6, pp. 1435-1492 | Article | MR: 3875844 | Zbl: 06979420

[31] C. Müller Spherical Harmonics, Springer, 1966 | Article | Zbl: 0138.05101

[32] T. Peter; G. Plonka; R. Schaback Prony’s method for multivariate signals, Proc. Appl. Math. Mech., Volume 15 (2015), p. 665-666 | Article

[33] G. Plonka; M. Tasche Prony methods for recovery of structured functions, GAMM-Mitt., Volume 37 (2014), pp. 239-258 | Article | MR: 3285022 | Zbl: 1311.65012

[34] D. Potts; M. Tasche Parameter estimation for multivariate exponential sums, Electron. Trans. Numer. Anal., Volume 40 (2013), pp. 204-224 | MR: 3081570 | Zbl: 1305.65093

[35] D. Potts; M. Tasche Parameter estimation for nonincreasing exponential sums by Prony-like methods, Linear Algebra Appl., Volume 439 (2013), pp. 1024-1039 | Article | MR: 3061753 | Zbl: 1281.65021

[36] B. G. R. de Prony 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’alcool à différentes températures, J. Éc. Polytech., Volume 1 (1795) no. 22, pp. 24-76

[37] T. Sauer Prony’s method in several variables, Numer. Math., Volume 136 (2017) no. 2, pp. 411-438 | Article | MR: 3648093 | Zbl: 1377.65048

[38] K. Schröder Localized Kernels and Super-resolution on Special Manifolds (2018) (Ph. D. Thesis)

[39] P. Shukla; P. L. Dragotti Sampling schemes for multidimensional signals with finite rate of innovation, IEEE Trans. Signal Process., Volume 55 (2007) no. 7, pp. 3670-3686 | Article | MR: 2468671 | Zbl: 1391.94608

[40] G. Szegő Orthogonal Polynomials, American Mathematical Society, 1975

[41] M. Vetterli; P. Marziliano; T. Blu Sampling signals with finite rate of innovation, IEEE Trans. Signal Process., Volume 50 (2002) no. 6, pp. 1417-1428 | Article | MR: 1930786 | Zbl: 1369.94309

Cited by Sources: