×

Exact support recovery for sparse spikes deconvolution. (English) Zbl 1327.65104

Summary: This paper studies sparse spikes deconvolution over the space of measures. We focus on the recovery properties of the support of the measure (i.e., the location of the Dirac masses) using total variation of measures (TV) regularization. This regularization is the natural extension of the \(\ell^1\) norm of vectors to the setting of measures. We show that support identification is governed by a specific solution of the dual problem (a so-called dual certificate) having minimum \(L^2\) norm. Our main result shows that if this certificate is non-degenerate (see the definition below), when the signal-to-noise ratio is large enough TV regularization recovers the exact same number of Diracs. We show that both the locations and the amplitudes of these Diracs converge toward those of the input measure when the noise drops to zero. Moreover, the non-degeneracy of this certificate can be checked by computing a so-called vanishing derivative pre-certificate. This proxy can be computed in closed form by solving a linear system. Lastly, we draw connections between the support of the recovered measure on a continuous domain and on a discretized grid. We show that when the signal-to-noise level is large enough, and provided the aforementioned dual certificate is non-degenerate, the solution of the discretized problem is supported on pairs of Diracs which are neighbors of the Diracs of the input measure. This gives a precise description of the convergence of the solution of the discretized problem toward the solution of the continuous grid-free problem, as the grid size tends to zero.

MSC:

65J20 Numerical solutions of ill-posed problems in abstract spaces; regularization
46E27 Spaces of measures
49K40 Sensitivity, stability, well-posedness

Software:

PDCO; BLOOMP
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] J-M. Azais, Y. De Castro, and F. Gamboa. Spike detection from inaccurate samplings. Applied and Computational Harmonic Analysis, to appear, 2014. · Zbl 1308.94046
[2] B.N. Bhaskar and B. Recht. Atomic norm denoising with applications to line spectral estimation. In 2011 49th Annual Allerton Conference on Communication, Control, and Computing, pages 261-268, 2011.
[3] T. Blu, P.-L. Dragotti, M. Vetterli, P. Marziliano, and L. Coulot. Sparse sampling of signal innovations. IEEE Signal Processing Magazine, 25(2):31-40, 2008.
[4] K. Bredies and H.K. Pikkarainen. Inverse problems in spaces of measures. ESAIM: Control, Optimisation and Calculus of Variations, 19(1):190-218, 2013. · Zbl 1266.65083
[5] H. Brézis, P.G. Ciarlet, and J.L. Lions. Analyse fonctionnelle: Théorie et applications. Collection Mathématiques appliquées pour la maîtrise. Dunod, 1999.
[6] M. Burger and S. Osher. Convergence rates of convex variational regularization. Inverse Problems, 20(5):1411-1421, 2004. · Zbl 1068.65085
[7] E. J. Candès and C. Fernandez-Granda. Super-resolution from noisy data. Journal of Fourier Analysis and Applications, 19(6):1229-1254, 2013. · Zbl 1312.94015
[8] E. J. Candès and C. Fernandez-Granda. Towards a mathematical theory of super-resolution. Communications on Pure and Applied Mathematics, 67(6):906-956, 2014. · Zbl 1350.94011
[9] S.S. Chen, D.L. Donoho, and M.A. Saunders. Atomic decomposition by basis pursuit. SIAM journal on scientific computing, 20(1):33-61, 1999. · Zbl 0919.94002
[10] J. F. Claerbout and F. Muir. Robust modeling with erratic data. Geophysics, 38(5):826-844, 1973.
[11] L. Condat and A. Hirabayashi. Cadzow denoising upgraded: A new projection method for the recovery of dirac pulses from noisy linear measurements. Sampling Theory in Signal and Image Processing, to appear, 2014. · Zbl 1346.94023
[12] Y. de Castro and F. Gamboa. Exact reconstruction using beurling minimal extrapolation. Journal of Mathematical Analysis and Applications, 395(1):336-354, 2012. · Zbl 1302.94019
[13] L. Demanet, D. Needell, and N. Nguyen. Super-resolution via superset selection and pruning. CoRR, abs/1302.6288, 2013.
[14] D. L. Donoho. Superresolution via sparsity constraints. SIAM J. Math. Anal., 23(5):1309-1331, September 1992. · Zbl 0769.42007
[15] C. Dossal and S. Mallat. Sparse spike deconvolution with minimum scale. In Proceedings of SPARS, pages 123-126, November 2005.
[16] M. F. Duarte and R. G. Baraniuk. Spectral compressive sensing. Applied and Computational Harmonic Analysis, 35(1):111-129, 2013. · Zbl 1336.94016
[17] I. Ekeland and R. Témam. Convex Analysis and Variational Problems. Number, vol. 1 in Classics in Applied Mathematics. Society for Industrial and Applied Mathematics, 1976. · Zbl 0322.90046
[18] A. Fannjiang and W. Liao. Coherence pattern-guided compressive sensing with unresolved grids. SIAM J. Img. Sci., 5(1):179-202, February 2012. · Zbl 1250.65035
[19] C. Fernandez-Granda. Support detection in super-resolution. Proc. Proceedings of the 10th International Conference on Sampling Theory and Applications, pages 145-148, 2013.
[20] J.J. Fuchs. On sparse representations in arbitrary redundant bases. IEEE Transactions on Information Theory, 50(6):1341-1344, 2004. · Zbl 1284.94018
[21] M. Grasmair, O. Scherzer, and M. Haltmeier. Necessary and sufficient conditions for linear convergence of \[\ell_1\] ℓ1-regularization. Communications on Pure and Applied Mathematics, 64(2):161-182, 2011. · Zbl 1217.65095
[22] B. Hofmann, B. Kaltenbacher, C. Poschl, and O. Scherzer. A convergence rates result for tikhonov regularization in Banach spaces with non-smooth operators. Inverse Problems, 23(3):987, 2007. · Zbl 1131.65046
[23] S. Levy and P. Fullagar. Reconstruction of a sparse spike train from a portion of its spectrum and application to high-resolution deconvolution. Geophysics, 46(9):1235-1243, 1981.
[24] J. Lindberg. Mathematical concepts of optical superresolution. Journal of Optics, 14(8):083001, 2012.
[25] D. A. Lorenz and D. Trede. Greedy Deconvolution of Point-like Objects. In Rémi Gribonval, editor, SPARS’09, Saint Malo, France, 2009.
[26] J. W. Odendaal, E. Barnard, and C. W. I. Pistorius. Two-dimensional superresolution radar imaging using the MUSIC algorithm. IEEE Transactions on Antennas and Propagation, 42(10):1386-1391, October 1994.
[27] S.C. Park, M.K. Park, and M.G. Kang. Super-resolution image reconstruction: a technical overview. IEEE Signal Processing Magazine, 20(3):21-36, 2003.
[28] F. Santosa and W.W. Symes. Linear inversion of band-limited reflection seismograms. SIAM Journal on Scientific and Statistical Computing, 7(4):1307-1330, 1986. · Zbl 0602.73113
[29] O. Scherzer and B. Walch. Sparsity regularization for radon measures. In Scale Space and Variational Methods in Computer Vision, volume 5567 of Lecture Notes in Computer Science, pages 452-463. Springer, Berlin Heidelberg, 2009.
[30] G. Tang, B. Narayan Bhaskar, and B. Recht. Near minimax line spectral estimation. CoRR, abs/1303.4348, 2013. · Zbl 1359.94181
[31] R. Tibshirani. Regression shrinkage and selection via the Lasso. Journal of the Royal Statistical Society. Series B. Methodological, 58(1):267-288, 1996. · Zbl 0850.62538
[32] P. Turán. On rational polynomials. Acta Univ. Szeged, Sect. Sci. Math., pages 106-113, 1946. · Zbl 0060.05406
[33] S. Vaiter, G. Peyré, C. Dossal, and J. Fadili. Robust sparse analysis regularization. IEEE Transactions on Information Theory, 59(4):2001-2016, 2013. · Zbl 1364.94172
[34] P. Zhao and B. Yu. On model selection consistency of Lasso. J. Mach. Learn. Res., 7:2541-2563, December 2006. · Zbl 1222.62008
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.