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: 2020-01-29
DOI: https://doi.org/10.5802/smai-jcm.53
Classification: 65T40,  42C15,  30E05,  65F30
Keywords: frequency analysis, spectral analysis, exponential sum, moment problem, super-resolution
@article{SMAI-JCM_2019__S5__87_0,
     author = {Stefan Kunis and H.~Michael M\"oller and Ulrich von der Ohe},
     title = {Prony's method on the sphere},
     journal = {The SMAI journal of computational mathematics},
     publisher = {Soci\'et\'e de Math\'ematiques Appliqu\'ees et Industrielles},
     volume = {S5},
     year = {2019},
     pages = {87-97},
     doi = {10.5802/smai-jcm.53},
     language = {en},
     url = {smai-jcm.centre-mersenne.org/item/SMAI-JCM_2019__S5__87_0/}
}
Kunis, Stefan; Möller, H. Michael; von der Ohe, Ulrich. 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/item/SMAI-JCM_2019__S5__87_0/

[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