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
Kunis, Stefan 1; Möller, H. Michael 2; von der Ohe, Ulrich 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 = {Kunis, Stefan and M\"oller, H.~Michael and von der Ohe, Ulrich},
     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 = {http://www.numdam.org/articles/10.5802/smai-jcm.53/}
}
TY  - JOUR
AU  - Kunis, Stefan
AU  - Möller, H. Michael
AU  - von der Ohe, Ulrich
TI  - Prony’s method on the sphere
JO  - The SMAI Journal of computational mathematics
PY  - 2019
SP  - 87
EP  - 97
VL  - S5
PB  - Société de Mathématiques Appliquées et Industrielles
UR  - http://www.numdam.org/articles/10.5802/smai-jcm.53/
DO  - 10.5802/smai-jcm.53
LA  - en
ID  - SMAI-JCM_2019__S5__87_0
ER  - 
%0 Journal Article
%A Kunis, Stefan
%A Möller, H. Michael
%A von der Ohe, Ulrich
%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 http://www.numdam.org/articles/10.5802/smai-jcm.53/
%R 10.5802/smai-jcm.53
%G en
%F 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. http://www.numdam.org/articles/10.5802/smai-jcm.53/

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[29] Moitra, A. 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), Association for Computing Machinery (2015), pp. 821-830 | DOI | MR | Zbl

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

[31] Müller, C. Spherical Harmonics, Springer, 1966 | DOI | Zbl

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

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

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

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

[36] Prony, B. G. R. de 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] Sauer, T. Prony’s method in several variables, Numer. Math., Volume 136 (2017) no. 2, pp. 411-438 | DOI | MR | Zbl

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

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

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

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

Cited by Sources: