Super-resolution of point sources via convex programming. (English) Zbl 1386.94027
Summary: We consider the problem of recovering a signal consisting of a superposition of point sources from low-resolution data with a cutoff frequency \(f_c\). If the distance between the sources is under \(1/f_c\), this problem is not well posed in the sense that the low-pass data corresponding to two different signals may be practically the same. We show that minimizing a continuous version of the \(\ell_1\)-norm achieves exact recovery as long as the sources are separated by at least \(1.26/f_c\). The proof is based on the construction of a dual certificate for the optimization problem, which can be used to establish that the procedure is stable to noise. Finally, we illustrate the flexibility of our optimization-based framework by describing extensions to the demixing of sines and spikes and to the estimation of point sources that share a common support.
MSC:
| 94A12 | Signal theory (characterization, reconstruction, filtering, etc.) |
| 90C25 | Convex programming |
Keywords:
super-resolution; line-spectra estimation; convex optimization; dual certificates; sparse recovery; overcomplete dictionaries; group sparsity; multiple measurementsReferences:
| [1] | Ambrosio, L.; Fusco, N.; Pallara, D., \(Functions of Bounded Variation and Free Discontinuity Problems\), vol. 254, (2000) · Zbl 0957.49001 |
| [2] | Aubel, C.; Stotz, D.; Bolcskei, H., Super-resolution from short-time Fourier transform measurements, 40, (2014) |
| [3] | Azais, J.-M.; De Castro, Y.; Gamboa, F., Spike detection from inaccurate samplings, Appl. Comput. Harmonic Anal., 38, 195, (2015) · Zbl 1308.94046 · doi:10.1016/j.acha.2014.03.004 |
| [4] | Banerjee, N. S.; Geer, J. F., Exponentially accurate approximations to periodic Lipschitz functions based on Fourier series partial sums, J. Sci. Comput., 13, 460, (1998) · Zbl 0934.65146 · doi:10.1023/A:1023289301743 |
| [5] | Barbotin, Y.; Hormati, A.; Rangan, S.; Vetterli, M., Estimation of sparse MIMO channels with common support, IEEE Trans. Commun., 60, 3716, (2012) · doi:10.1109/TCOMM.2012.091112.110439 |
| [6] | Batenkov, D.; Yomdin, Y., Algebraic Fourier reconstruction of piecewise smooth functions, Math. Comput., 81, 2350, (2012) · Zbl 1237.42003 · doi:10.1090/S0025-5718-2011-02539-1 |
| [7] | Bendory, T.; Dekel, S.; Feuer, A., Exact recovery of dirac ensembles from the projection onto spaces of spherical harmonics, Constructive Approx., 42, 25, (2014) |
| [8] | Bendory, T.; Dekel, S.; Feuer, A., Exact recovery of non-uniform splines from the projection onto spaces of algebraic polynomials, J. Approx. Theory, 182, 17, (2014) · Zbl 1290.41002 · doi:10.1016/j.jat.2014.03.001 |
| [9] | Betzig, E.; Patterson, G. H.; Sougrat, R.; Lindwasser, O. W.; Olenych, S.; Bonifacino, J. S.; Davidson, M. W.; Lippincott-Schwartz, J.; Hess, H. F., Imaging intracellular fluorescent proteins at nanometer resolution, Science, 313, 1645, (2006) · doi:10.1126/science.1127344 |
| [10] | Beurling, A., Sur les intégrales de Fourier absolument convergentes et leur application a une transformation fonctionnelle, Ninth Scandinavian Mathematical Congress, 366, (1938) · JFM 65.0483.02 |
| [11] | Beurling, A., Interpolation for an interval on \[\mathbb{R}^1\], The Collected Works of Arne Beurling: Harmonic Analysis, vol. 2, 365, (1966) |
| [12] | Bhaskar, B. N.; Tang, G.; Recht, B., Atomic norm denoising with applications to line spectral estimation, IEEE Trans. Signal Process., 61, 5999, (2013) · Zbl 1394.94079 · doi:10.1109/TSP.2013.2273443 |
| [13] | Bienvenu, G., Influence of the spatial coherence of the background noise on high resolution passive methods, vol. 4, 309, (1979) |
| [14] | Blu, T.; Dragotti, P.; Vetterli, M.; Marziliano, P.; Coulot, L., Sparse sampling of signal innovations, IEEE Signal Process. Mag., 25, 40, (2008) · doi:10.1109/MSP.2007.914998 |
| [15] | Boyd, N.; Schiebinger, G.; Recht, B. |
| [16] | Bredies, K.; Pikkarainen, H. K., Inverse problems in spaces of measures, ESAIM: Control, Optimisation and Calculus of Variations, (2012) |
| [17] | Cadzow, J. A., Signal enhancement- a composite property mapping algorithm, IEEE Trans. Acoustics Speech Signal Process., 36, 62, (1988) · Zbl 0649.93059 · doi:10.1109/29.1488 |
| [18] | Candès, E. J.; Fernandez-Granda, C., Towards a mathematical theory of super-resolution, Commun. Pure Appl. Math., 67, 956, (2013) · Zbl 1350.94011 · doi:10.1002/cpa.v67.6 |
| [19] | Candès, E. J.; Fernandez-Granda, C., Super-resolution from noisy data, J. Fourier Anal. Appl., 19, 1254, (2013) · Zbl 1312.94015 · doi:10.1007/s00041-013-9292-3 |
| [20] | Candès, E. J.; Li, X.; Ma, Y.; Wright, J., Robust principal component analysis?, J. ACM, 58, 11, (2011) · Zbl 1327.62369 · doi:10.1145/1970392 |
| [21] | Candès, E. J.; Recht, B., Exact matrix completion via convex optimization, Found. Comput. Math., 9, 772, (2009) · Zbl 1219.90124 · doi:10.1007/s10208-009-9045-5 |
| [22] | Candès, E. J.; Romberg, J. K.; Tao, T., Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inf. Theory, 52, 509, (2006) · Zbl 1231.94017 · doi:10.1109/TIT.2005.862083 |
| [23] | Candès, E. J.; Tao, T., Decoding by linear programming, IEEE Trans. Inf. Theory, 51, 4215, (2005) · Zbl 1264.94121 · doi:10.1109/TIT.2005.858979 |
| [24] | Candès, E. J.; Tao, T., Near-optimal signal recovery from random projections: universal encoding strategies?, IEEE Trans. Inf. Theory, 52, 5425, (2006) · Zbl 1309.94033 · doi:10.1109/TIT.2006.885507 |
| [25] | Chandrasekaran, V.; Sanghavi, S.; Parrilo, P. A.; Willsky, A. S., Rank-sparsity incoherence for matrix decomposition, SIAM J. Optim., 21, 596, (2011) · Zbl 1226.90067 · doi:10.1137/090761793 |
| [26] | Claerbout, J. F.; Muir, F., Robust modeling with erratic data, Geophysics, 38, 844, (1973) · doi:10.1190/1.1440378 |
| [27] | Clergeot, H.; Tressens, S.; Ouamri, A., Performance of high resolution frequencies estimation methods compared to the Cramér-Rao bounds, IEEE Trans. Acoustics Speech Signal Process., 37, 1720, (1989) · Zbl 0691.93060 · doi:10.1109/29.46553 |
| [28] | De Castro, Y.; Gamboa, F., Exact reconstruction using Beurling minimal extrapolation, J. Math. Anal. Appl., 395, 354, (2012) · Zbl 1302.94019 · doi:10.1016/j.jmaa.2012.05.011 |
| [29] | De Castro, Y.; Mijoule, G., Non-uniform spline recovery from small degree polynomial approximation, J. Math. Anal. Appl., 430, 992, (2015) · Zbl 1357.94031 · doi:10.1016/j.jmaa.2015.05.034 |
| [30] | Demanet, L.; Nguyen, N. |
| [31] | Den Dekker, A. J.; Van den Bos, A., Resolution: a survey, JOSA A, 14, 557, (1997) · doi:10.1364/JOSAA.14.000547 |
| [32] | Donoho, D. L., Compressed sensing, IEEE Trans. Inf. Theory, 52, 1306, (2006) · Zbl 1288.94016 · doi:10.1109/TIT.2006.871582 |
| [33] | Donoho, D. L.; Tanner, J., Sparse nonnegative solutions of underdetermined linear equations by linear programming, Proc. Natl. Acad. Sci., 9451, (2005) · Zbl 1135.90368 |
| [34] | Dragotti, P.; Vetterli, M.; Blu, T., Sampling moments and reconstructing signals of finite rate of innovation: Shannon meets Strang-Fix, IEEE Trans. Signal Process., 55, 1757, (2007) · Zbl 1391.94598 · doi:10.1109/TSP.2006.890907 |
| [35] | Dumitrescu, B., Positive Trigonometric Polynomials and Signal Processing Applications, (2007) · Zbl 1126.93005 |
| [36] | Duval, V.; Peyré, G., Exact support recovery for sparse spikes deconvolution, Found. Comput. Math., 41, (2015) · Zbl 1327.65104 |
| [37] | Eckhoff, K. S., Accurate reconstructions of functions of finite regularity from truncated Fourier series expansions, Math. Comput., 64, 690, (1995) · Zbl 0830.65144 · doi:10.1090/S0025-5718-1995-1265014-7 |
| [38] | Ekanadham, C.; Tranchina, D.; Simoncelli, E. P., Recovery of sparse translation-invariant signals with continuous basis pursuit, IEEE Trans. Signal Process., 59, 4744, (2011) · Zbl 1392.94192 · doi:10.1109/TSP.2011.2160058 |
| [39] | Fernandez-Granda, C., Support detection in super-resolution, 148, (2013) |
| [40] | Fuchs, J. J., Sparsity and uniqueness for some specific underdetermined linear systems, 732, (2005) |
| [41] | Ghez, A. M.; Duchêne, G.; Matthews, K.; Hornstein, S. D.; Tanner, A.; Larkin, J.; Morris, M.; Becklin, E. E.; Salim, S.; Kremenek, T.; Thompson, D.; Soifer, B. T.; Neugebauer, G.; McLean, I., The first measurement of spectral lines in a short-period star bound to the Galaxy’s central black hole: a paradox of youth, Astrophys. J. Lett., 586, L127, (2003) · doi:10.1086/374804 |
| [42] | Grant, M.; Boyd, S., (2011) |
| [43] | Heckel, R.; Morgenshtern, V. I.; Soltanolkotabi, M. |
| [44] | Hess, S. T.; Girirajan, T. P.; Mason, M. D., Ultra-high resolution imaging by fluorescence photo- activation localization microscopy, Biophys. J., 91, 4258, (2006) · doi:10.1529/biophysj.106.091116 |
| [45] | Lajunen, L. H.; Perämäki, P., Spectrochemical Analysis by Atomic Absorption and Emission, (2004) |
| [46] | Levy, S.; Fullagar, P. K., Reconstruction of a sparse spike train from a portion of its spectrum and application to high-resolution deconvolution, Geophysics, 46, 1243, (1981) · doi:10.1190/1.1441261 |
| [47] | Li, X., Compressed sensing and matrix completion with constant proportion of corruptions, Constructive Approx., 37, 99, (2013) · Zbl 1258.93076 · doi:10.1007/s00365-012-9176-9 |
| [48] | Li, Y.; Chi, Y. |
| [49] | Liao, W.; Fannjiang, A., Music for single-snapshot spectral estimation: stability and super-resolution, Appl. Comput. Harmonic Anal., 40, 67, (2016) · Zbl 1416.94028 · doi:10.1016/j.acha.2014.12.003 |
| [50] | Lindberg, J., Mathematical concepts of optical superresolution, J. Optics, 14, 083001, (2012) · doi:10.1088/2040-8978/14/8/083001 |
| [51] | McCoy, M. B.; Tropp, J. A., Sharp recovery bounds for convex demixing, with applications, Found. Comput. Math., (2014) · Zbl 1312.94016 |
| [52] | Milanfar, P. (ed.), Super-Resolution Imaging, (2010) |
| [53] | Moitra, A., Super-resolution, extremal functions and the condition number of Vandermonde matrices, (2015) · Zbl 1321.68421 |
| [54] | Morgenshtern, V. I.; Candès, E. J., (2014) |
| [55] | Prony, R., Essai expérimental et analytique: sur les lois de la dilatabilité de fluides élastique et sur celles de la force expansive de la vapeur de l’alkool, à différentes températures, J. l’Ecole Polytechnique, 1, 76, (1795) |
| [56] | Rieke, F., Spikes: Exploring the Neural Code, (1999) |
| [57] | Rockafellar, R., Conjugate Duality and Optimization, (1974) · Zbl 0296.90036 |
| [58] | Roy, R.; Kailath, T., ESPRIT—estimation of signal parameters via rotational invariance techniques, IEEE Trans. Acoustics Speech Signal Process., 37, 995, (1989) · doi:10.1109/29.32276 |
| [59] | Rudin, L. I.; Osher, S.; Fatemi, E., Nonlinear total variation based noise removal algorithms, Phys. D: Nonlinear Phenom., 60, 268, (1992) · Zbl 0780.49028 · doi:10.1016/0167-2789(92)90242-F |
| [60] | Rust, M. J.; Bates, M.; Zhuang, X., Sub-diffraction-limit imaging by stochastic optical reconstruction microscopy (STORM), Nat. Methods, 3, 796, (2006) · doi:10.1038/nmeth929 |
| [61] | Santosa, F.; Symes, W. W., Linear inversion of band-limited reflection seismograms, SIAM J. Sci. Stat. Comput., 7, 1330, (1986) · Zbl 0602.73113 · doi:10.1137/0907087 |
| [62] | Schaeffer, A., Inequalities of A. Markoff and S. Bernstein for polynomials and related functions, Bull. Am. Math. Soc., 47, 579, (1941) · Zbl 0027.05205 · doi:10.1090/S0002-9904-1941-07510-5 |
| [63] | Schiebinger, G.; Robeva, E.; Recht, B. |
| [64] | Schmidt, R., Multiple emitter location and signal parameter estimation, IEEE Trans. Antennas Propag., 34, 280, (1986) · doi:10.1109/TAP.1986.1143830 |
| [65] | Slepian, D., Prolate spheroidal wave functions, Fourier analysis, and uncertainty. V—The discrete case, Bell Syst. Tech. J., 57, 1430, (1978) · Zbl 0378.33006 · doi:10.1002/bltj.1978.57.issue-5 |
| [66] | Smith, L. F.; Aller, L. H., On the classification of emission-line spectra of planetary nuclei, Astrophys. J., 157, 1245, (1969) · doi:10.1086/150151 |
| [67] | Soltanolkotabi, M., (2014) |
| [68] | Stoica, P.; Moses, R. L., Spectral Analysis of Signals, (2005) · Zbl 1194.94009 |
| [69] | Stoica, P.; Soderstrom, T., Statistical analysis of MUSIC and subspace rotation estimates of sinusoidal frequencies, IEEE Trans. Signal Process., 39, 1847, (1991) · Zbl 0729.62088 · doi:10.1109/78.91154 |
| [70] | Tang, G., Resolution limits for atomic decompositions via Markov-Bernstein type inequalities, 552, (2015) |
| [71] | Tang, G.; Bhaskar, B. N.; Recht, B., Near minimax line spectral estimation, IEEE Trans. Inf. Theory, 61, 512, (2015) · Zbl 1359.94181 · doi:10.1109/TIT.2014.2368122 |
| [72] | Tang, G.; Bhaskar, B. N.; Shah, P.; Recht, B., Compressed sensing off the grid, IEEE Trans. Inf. Theory, 59, 7490, (2013) · Zbl 1364.94168 · doi:10.1109/TIT.2013.2277451 |
| [73] | Tang, G.; Shah, P.; Bhaskar, B. N.; Recht, B., Robust line spectral estimation, 305, (2014) |
| [74] | Tibshirani, R., Regression shrinkage and selection via the lasso, J. R. Stat. Soc. Ser. B (Methodol.), 288, (1996) · Zbl 0850.62538 |
| [75] | Tropp, J. A., Algorithms for simultaneous sparse approximation. Part II: Convex relaxation, Signal Process., 86, 602, (2006) · Zbl 1163.94395 · doi:10.1016/j.sigpro.2005.05.031 |
| [76] | Tufts, D. W.; Kumaresan, R., Estimation of frequencies of multiple sinusoids: making linear prediction perform like maximum likelihood, Proc. IEEE, 70, 989, (1982) · doi:10.1109/PROC.1982.12428 |
| [77] | Vetterli, M.; Marziliano, P.; Blu, T., Sampling signals with finite rate of innovation, IEEE Trans. Signal Process., 50, 1428, (2002) · Zbl 1369.94309 · doi:10.1109/TSP.2002.1003065 |
| [78] | Yang, Z.; Xie, L. |
| [79] | Yuan, M.; Lin, Y., Model selection and estimation in regression with grouped variables, J. R. Stat. Soc.: Ser. B (Stat. Methodol.), 68, 67, (2006) · Zbl 1141.62030 · doi:10.1111/rssb.2006.68.issue-1 |
| [80] | Zhu, L.; Zhang, W.; Elnatan, D.; Huang, B., Faster STORM using compressed sensing, Nat. Methods, 9, 723, (2012) · doi:10.1038/nmeth.1978 |
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.
