×

zbMATH — the first resource for mathematics

Atomic norm minimization for decomposition into complex exponentials and optimal transport in Fourier domain. (English) Zbl 1455.42002
In this paper, atomic decompositions of complex vectors \(v = (v_m)_{m=-M}^M\) are studied. An atom is a vector \(a(z) = \big(\exp(- {\mathrm i}\,m\,{\mathrm{arg}}\,z)\big)_{m=-M}^M\) with \(z \in {\mathbb T} = \{z \in \mathbb C : \,|z|=1\}\). If the vector \(v\) has the atomic decomposition \[ v = \sum_{k=1}^K c_k \,a(z_k) \] with distinct \(z_k \in \mathbb T\) and \(c_k \in {\mathbb R} \setminus \{0\}\), then the discrete measure \[ \mu = \sum_{k=1}^K c_k \,\delta(z_k) \] explains \(v\), where \(\delta(z_k)\) is the Dirac measure. The author reviews properties of atomic decompositions, the close relationship with positive semidefinite Toeplitz matrices, and the Prony method to extract the parameters from a linear combination of atoms. He presents a characterization of the existence and uniqueness of a measure explaining \(v\) with minimal total variation norm. This minimal measure is numerically determined by a convex semidefinite program and Prony’s method. Further, the author explores the optimal transport between two measures, of which only a finite sequence of Fourier coefficients is known.
MSC:
42A10 Trigonometric approximation
42A70 Trigonometric moment problems in one variable harmonic analysis
65K05 Numerical mathematical programming methods
65T50 Numerical methods for discrete and fast Fourier transforms
90C22 Semidefinite programming
90C25 Convex programming
Software:
BLOOMP; PDCO
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Agueh, M.; Carlier, G., Barycenters in the Wasserstein space, SIAM J. Math. Anal., 43, 2, 904-924 (2011) · Zbl 1223.49045
[2] J. Alaux, E. Grave, M. Cuturi, A. Joulin, Unsupervised hyper-alignment for multilingual word embeddings, in: Proc. of ICLR, 2019.
[3] Alexeev, B.; Cahill, J.; Mixon, D. G., Full spark frames, J. Fourier Anal. Appl., 18, 6, 1167-1194 (2012) · Zbl 1257.42040
[4] Andersson, F.; Carlsson, M.; Tourneret, J.-Y.; Wendt, H., A new frequency estimation method for equally and unequally spaced data, 62, 21, 5761-5774 (2014) · Zbl 1394.94042
[5] Auton, J. R., Investigation of Procedures for Automatic Resonance Extraction from Noisy Transient Electromagnetics Data, vol. III (1981), Effects Technology Inc.: Effects Technology Inc. Santa Barbara, CA, Report, translation of Prony’s original paper and bibliography of Prony’s method
[6] Azaïs, J.-M.; De Castro, Y.; Gamboa, F., Spike detection from inaccurate samplings, Appl. Comput. Harmon. Anal., 38, 2, 177-195 (2015) · Zbl 1308.94046
[7] Bakonyi, M.; Lopushanskaya, E. V., Moment problems for real measures on the unit circle, (Recent Advances in Operator Theory in Hilbert and Krein Spaces. Recent Advances in Operator Theory in Hilbert and Krein Spaces, Operator Theory: Advances and Applications, vol. 198 (2010), Birkhäuser Basel), 49-60 · Zbl 1190.15030
[8] Bauschke, H. H.; Combettes, P. L., Convex Analysis and Monotone Operator Theory in Hilbert Spaces (2011), Springer: Springer New York · Zbl 1218.47001
[9] Benedetto, J. J.; Li, W., Super-resolution by means of Beurling minimal extrapolation, Appl. Comput. Harmon. Anal., 48, 1, 218-241 (2020) · Zbl 1439.43004
[10] Bhaskar, B. N.; Tang, G.; Recht, B., Atomic norm denoising with applications to line spectral estimation, IEEE Trans. Signal Process., 61, 23, 5987-5999 (2013) · Zbl 1394.94079
[11] T. Blu, The generalized annihilation property—A tool for solving finite rate of innovation problems, in: Proc. of Int. Workshop on Sampling Theory and Appl., SampTA, Marseille, France, 2009.
[12] Blu, T.; Dragotti, P.-L.; Vetterli, M.; Marziliano, P.; Coulot, L., Sparse sampling of signal innovations, IEEE Signal Process. Mag., 25, 2, 31-40 (2008), Special issue on Compressive Sampling
[13] Bourguignon, S.; Carfantan, H.; Idier, J., A sparsity-based method for the estimation of spectral lines from irregularly sampled data, IEEE J. Sel. Topics Signal Process., 1, 4, 575-585 (2007)
[14] Boyer, C.; Chambolle, A.; De Castro, Y.; Duval, V.; de Gournay, F.; Weiss, P., On representer theorems and convex regularization, SIAM J. Optim., 29, 1260-1281 (2019) · Zbl 1423.49036
[15] Bredies, K.; Pikkarainen, H. K., Inverse problems in spaces of measures, ESAIM Control Optim. Calc. Var., 19, 1, 190-218 (2013) · Zbl 1266.65083
[16] Cabrelli, C. A.; Molter, U. M., The Kantorovich metric for probability measures on the circle, J. Comput. Appl. Math., 57, 3, 345-361 (1995) · Zbl 0819.60001
[17] Candès, E. J.; Fernandez-Granda, C., Towards a mathematical theory of super-resolution, Comm. Pure Appl. Math., 67, 6, 906-956 (2014) · Zbl 1350.94011
[18] Carathéodory, C., Über den Variabilitätsbereich der Fourierschen Konstanten von positiven harmonischen Funktionen, Rend. Circ. Mat. Palermo (2), 32, 1, 193-217 (1911) · JFM 42.0429.01
[19] Carathéodory, C.; Fejér, L., Über den Zusammenhang der Extremen von harmonischen Funktionen mit ihren Koeffizienten und über den Picard-Landau’schen Satz, Rend. Circ. Mat. Palermo (2), 32, 1, 218-239 (1911) · JFM 42.0430.01
[20] Chambolle, A.; Pock, T., A first-order primal-dual algorithm for convex problems with applications to imaging, J. Math. Imaging Vision, 40, 1, 120-145 (2011) · Zbl 1255.68217
[21] Chandrasekaran, V.; Recht, B.; Parrilo, P. A.; Willsky, A. S., The convex geometry of linear inverse problems, Found. Comput. Math., 12, 805-849 (2012) · Zbl 1280.52008
[22] Chen, S. S.; Donoho, D. L.; Saunders, M. A., Atomic decomposition by basis pursuit, SIAM J. Sci. Comput., 20, 1, 33-61 (1998) · Zbl 0919.94002
[23] Chi, Y.; Pezeshki, A.; Scharf, L.; Pezeshki, A.; Calderbank, R., Sensitivity to basis mismatch in compressed sensing, IEEE Trans. Signal Process., 59, 5, 2182-2195 (2011) · Zbl 1392.94144
[24] Condat, L., A primal-dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms, J. Optim. Theory Appl., 158, 2, 460-479 (2013) · Zbl 1272.90110
[25] Condat, L., A convex approach to K-means clustering and image segmentation, (Pelillo, M.; Hancock, E., Proc. of EMMCVPR. Proc. of EMMCVPR, Lecture Notes in Computer Science, vol. 10746 (2017), Springer, 2018: Springer, 2018 Venice, Italy), 220-234
[26] Condat, L., Discrete total variation: New definition and minimization, SIAM J. Imaging Sci., 10, 3, 1258-1290 (2017) · Zbl 1379.68330
[27] L. Condat, A. Hirabayashi, Super-resolution of positive spikes by Toeplitz low-rank approximation, in: Proc. of EUSIPCO, Nice, France, 2015. · Zbl 1346.94023
[28] Condat, L.; Hirabayashi, A., Cadzow denoising upgraded: A new projection method for the recovery of Dirac pulses from noisy linear measurements, Sampl. Theory Signal Image Process., 14, 1, 17-47 (2015) · Zbl 1346.94023
[29] Condat, L.; Kitahara, D.; Contreras, A.; Hirabayashi, A., Proximal splitting algorithms: Relax them all! (2019), preprint arXiv:1912.00137
[30] L. Condat, D. Kitahara, A. Hirabayashi, A convex lifting approach to image phase unwrapping, in: Proc. of IEEE Int. Conf. on Acoustics, Speech and Signal Processing, ICASSP, Brighton, UK, 2019.
[31] Curto, R. E.; Fialkow, L. A., Recursiveness, positivity, and truncated moment problems, Houston J. Math., 17, 4, 603-635 (1991) · Zbl 0757.44006
[32] De Castro, Y.; Gamboa, F., Exact reconstruction using Beurling minimal extrapolation, J. Math. Anal. Appl., 395, 1, 336-354 (2012) · Zbl 1302.94019
[33] Donoho, D. L.; Elad, M., Optimally sparse representation in general (nonorthogonal) dictionaries via \(\ell^1\) minimization, Proc. Natl. Acad. Sci., 100, 5, 2197-2202 (2003) · Zbl 1064.94011
[34] Dragotti, P. L.; Vetterli, M.; Blu, T., Sampling moments and reconstructing signals of finite rate of innovation: Shannon meets strang-fix, IEEE Trans. Signal Process., 55, 5, 1741-1757 (2007) · Zbl 1391.94598
[35] Duarte, M. F.; Baraniuk, R. G., Spectral compressive sensing, Appl. Comput. Harmon. Anal., 35, 1, 111-129 (2013) · Zbl 1336.94016
[36] Duval, V.; Peyré, G., Exact support recovery for sparse spikes deconvolution, Found. Comput. Math., 15, 5, 1315-1355 (2015) · Zbl 1327.65104
[37] Elad, M., Sparse and Redundant Representations: From Theory to Applications in Signal and Image Processing (2010), Springer-Verlag New York · Zbl 1211.94001
[38] Fannjiang, A.; Liao, W., Coherence pattern-guided compressive sensing with unresolved grids, SIAM J. Imaging Sci., 5, 1, 179-202 (2012) · Zbl 1250.65035
[39] Fernandez-Granda, C., Super-resolution of point sources via convex programming, Inf. Inference, 5, 3, 251-303 (2016) · Zbl 1386.94027
[40] M. Ferreira Da Costa, W. Dai, A tight converse to the spectral resolution limit via convex programming, in: Proc. of IEEE International Symposium on Information Theory, 2018.
[41] Fisher, T., Existence, uniqueness, and minimality of the Jordan measure decomposition (2012), report arXiv:1206.5449v2
[42] Fisher, S. D.; Jerome, J. W., Spline solutions to L1 extremal problems in one and several variables, J. Approx. Theory, 13, 73-83 (1975) · Zbl 0295.49002
[43] Flamary, R.; Févotte, C.; Courty, N.; Emiya, V., Optimal spectral transportation with application to music transcription, (Advances in Neural Information Processing Systems (Proc. of NIPS) (2016)), 703-711
[44] Flinth, A.; Weiss, P., Exact solutions of infinite dimensional total-variation regularized problems, Inf. Inference: J. IMA, 8, 407-443 (2019)
[45] J.-J. Fuchs, Sparsity and uniqueness for some specific under-determined linear systems, in: Proc. of IEEE ICASSP, vol. 5, 2005, pp. 729-732.
[46] Hofmann, B.; Kaltenbacher, B.; Poeschl, C.; Scherzer, O., A convergence rates result for Tikhonov regularization in Banach spaces with non-smooth operators, Inverse Problems, 23, 987-1010 (2007) · Zbl 1131.65046
[47] Mallat, S.; Zhang, Z., Matching pursuit in a time-frequency dictionary, IEEE Trans. Signal Process., 41, 3397-3415 (1993) · Zbl 0842.94004
[48] Pereyra, V.; Scherer, G., Exponential data fitting, (Pereyra, V.; Scherer, G., Exponential Data Fitting and Its Applications (2010), Bentham Science Publ.), 1-26, (Chapter 1)
[49] Polisano, K.; Condat, L.; Clausel, M.; Perrier, V., A convex approach to super-resolution and regularization of lines in images, SIAM J. Imaging Sci., 12, 1, 211-258 (2019) · Zbl 1422.94008
[50] Potts, D.; Tasche, M., Nonlinear approximation by sums of nonincreasing exponentials, Appl. Anal., 90, 3-4, 609-626 (2011) · Zbl 1222.41025
[51] Rabin, J.; Delon, J.; Gousseau, Y., Transportation distances on the circle, J. Math. Imaging Vision, 41, 147 (2011) · Zbl 1255.68179
[52] Rabin, J.; Peyré, G.; Delon, J.; Bernot, M., Wasserstein barycenter and its application to texture mixing, (Proc. of Scale Space and Variational Methods in Computer Vision (SSVM) 2011. Proc. of Scale Space and Variational Methods in Computer Vision (SSVM) 2011, Lecture Notes in Computer Science, vol. 6667 (2012), Springer: Springer Berlin, Heidelberg)
[53] Riche de Prony, G. M., 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’eau et de la vapeur de l’alcool à différentes températures, J. l’École Polytech., 1, 22, 24-76 (1795)
[54] Rolet, A.; Seguy, V.; Blondel, M.; Sawada, H., Blind source separation with optimal transport non-negative matrix factorization, EURASIP J. Adv. Signal Process., 53 (2018)
[55] Santambrogio, F., Optimal Transport for Applied Mathematicians (2015), Birkhauser · Zbl 1401.49002
[56] Satorra, A.; Neudecker, H., A theorem on the rank of a product of matrices with illustration of its use in goodness of fit testing, Psychometrika, 79 (2014)
[57] Stoica, P.; Moses, R., Spectral Analysis of Signals (2005), Prentice Hall, NJ
[58] Tang, G.; Bhaskar, B. N.; Shah, P.; Recht, B., Compressed sensing off the grid, IEEE Trans. Inf. Theory, 59, 11, 7465-7490 (2013) · Zbl 1364.94168
[59] Unser, M.; Fageot, J.; Ward, J. P., Splines are universal solutions of linear inverse problems with generalized TV regularization, SIAM Rev., 59, 769-793 (2017) · Zbl 1382.41011
[60] Villani, C., (Topics in Optimal Transportation. Topics in Optimal Transportation, Graduate Studies in Mathematics (2003), American Mathematical Society) · Zbl 1106.90001
[61] Z. Yang, L. Xie, Spectral compressed sensing of real spikes, in: Proc. of IEEE International Conference on Ubiquitous Wireless Broadband, ICUWB, 2016.
[62] Yang, Z.; Xie, L., Exact joint sparse frequency recovery via optimization methods (2014), preprint arXiv:1405.6585v1
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.