×

zbMATH — the first resource for mathematics

Super-resolution by means of Beurling minimal extrapolation. (English) Zbl 1439.43004
Summary: We investigate the super-resolution capabilities of total variation minimization. Namely, given a finite set \(\Lambda\subseteq\mathbb{Z}^d\) and spectral data \(F=\hat{\mu}|_{\Lambda}\), where \(\mu\) is an unknown bounded Radon measure on the torus \(\mathbb{T}^d\), the problem is to find the measures with smallest norm whose Fourier transforms agree with \(F\) on \(\Lambda\). Our main theorem shows that solutions to the problem depend crucially on a set \(\Gamma\subseteq\Lambda\), defined in terms of \(F\) and \(\Lambda \). For example, when \(\#\Gamma=0\), the solutions are singular measures supported in the zero set of an analytic function, and when \(\#\Gamma\geq 2\), the solutions are singular measures supported in the intersection of \(\binom{\#\Gamma}{2}\) hyperplanes. By theory and example, we show that the case \(\#\Gamma=1\) is different from other cases, and is deeply connected with the existence of positive solutions. This theorem has implications to the possibility and impossibility of uniquely recovering \(\mu\) from \(F\) on \(\Lambda\). We illustrate how to apply our theory to both directions, by computing pertinent analytical examples. These examples are of interest in both super-resolution and deterministic compressed sensing. Our concept of an admissibility range fundamentally connects Beurling’s theory of minimal extrapolation [A. Beurling, The collected works of Arne Beurling. Volume 1: Complex analysis. Volume 2: Harmonic analysis. Ed. by Lennart Carleson, Paul Malliavin, John Neuberger, John Wermer. Boston etc.: Birkhäuser Verlag (1989; Zbl 0732.01042)] with Candès and Fernandez-Granda’s work on super-resolution [E. J. Candès and C. Fernandez-Granda, J. Fourier Anal. Appl. 19, No. 6, 1229–1254 (2013; Zbl 1312.94015)]. This connection is exploited to address situations where current algorithms fail to compute a numerical solution to the total variation minimization problem.

MSC:
43A25 Fourier and Fourier-Stieltjes transforms on locally compact and other abelian groups
46E27 Spaces of measures
46N10 Applications of functional analysis in optimization, convex analysis, mathematical programming, economics
94A12 Signal theory (characterization, reconstruction, filtering, etc.)
Software:
PDCO
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Au-Yeung, Enrico; Benedetto, John J., Generalized Fourier frames in terms of balayage, J. Fourier Anal. Appl., 21, 3, 472-508 (2015) · Zbl 1327.42033
[2] Aubel, Céline; Stotz, David; Bölcskei, Helmut, A theory of super-resolution from short-time Fourier transform measurements, J. Fourier Anal. Appl., 1-63 (2017) · Zbl 1388.42014
[3] Azaïs, Jean-Marc; De Castro, Yohann; Gamboa, Fabrice, Spike detection from inaccurate samplings, Appl. Comput. Harmon. Anal., 38, 2, 177-195 (2015) · Zbl 1308.94046
[4] Benedetto, John J., Harmonic Analysis and Applications (1996), CRC Press Inc. · Zbl 0860.43001
[5] Benedetto, John J.; Czaja, Wojciech, Integration and Modern Analysis (2009), Birkhäuser Boston, Inc.: Birkhäuser Boston, Inc. Boston · Zbl 1191.28001
[7] Beurling, Arne, Balayage of Fourier-Stieltjes transforms, (The Collected Works of Arne Beurling, vol. 2 (1989)), 341-350
[8] Beurling, Arne, Interpolation for an interval in R1, (The Collected Works of Arne Beurling, vol. 2 (1989)), 351-365
[9] Bhaskar, Badri Narayan; Tang, Gongguo; Recht, Benjamin, Atomic norm denoising with applications to line spectral estimation, IEEE Trans. Signal Process., 61, 23, 5987-5999 (2013) · Zbl 1394.94079
[10] Boyd, Nicholas; Schiebinger, Geoffrey; Recht, Benjamin, The alternating descent conditional gradient method for sparse inverse problems, SIAM J. Optim., 27, 2, 616-639 (2017) · Zbl 1365.90195
[11] Candès, Emmanuel J.; Fernandez-Granda, Carlos, Super-resolution from noisy data, J. Fourier Anal. Appl., 19, 6, 1229-1254 (2013) · Zbl 1312.94015
[12] Candès, Emmanuel J.; Fernandez-Granda, Carlos, Towards a mathematical theory of super-resolution, Comm. Pure Appl. Math., 67, 6, 906-956 (2014) · Zbl 1350.94011
[13] Candès, Emmanuel J.; Romberg, Justin K.; Tao, Terence, Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inform. Theory, 52, 2, 489-509 (2006) · Zbl 1231.94017
[14] Chandrasekaran, Venkat; Recht, Benjamin; Parrilo, Pablo A.; Willsky, Alan S., The convex geometry of linear inverse problems, Found. Comput. Math., 12, 6, 805-849 (2012) · Zbl 1280.52008
[15] Chen, Scott S.; Donoho, David L.; Saunders, Michael A., Atomic decomposition by basis pursuit, SIAM Rev., 43, 1, 129-159 (2001) · Zbl 0979.94010
[16] Childers, Donald G., Modern Spectrum Analysis (1978), IEEE Press: IEEE Press Piscataway, New Jersey
[17] De Castro, Yohann; Gamboa, Fabrice, Exact reconstruction using Beurling minimal extrapolation, J. Math. Anal. Appl., 395, 1, 336-354 (2012) · Zbl 1302.94019
[18] De Castro, Yohann; Gamboa, Fabrice; Henrion, Didier; Lasserre, J-B., Exact solutions to super resolution on semi-algebraic domains in higher dimensions, IEEE Trans. Inform. Theory, 63, 1, 621-630 (2017) · Zbl 1359.94030
[19] Donoho, David L., Compressed sensing, IEEE Trans. Inform. Theory, 52, 4, 1289-1306 (2006) · Zbl 1288.94016
[20] Dumitrescu, Bogdan, Positive Trigonometric Polynomials and Signal Processing Applications (2007), Springer: Springer Dordrecht · Zbl 1126.93005
[21] Duval, Vincent; Peyré, Gabriel, Exact support recovery for sparse spikes deconvolution, Found. Comput. Math., 15, 5, 1315-1355 (2015) · Zbl 1327.65104
[22] Esseen, Carl-Gustav, Fourier analysis of distribution functions. A mathematical study of the Laplace-Gaussian law, Acta Math., 77, 1, 1-125 (1945) · Zbl 0060.28705
[23] Esseen, Carl-Gustav, A note on Fourier-Stieltjes transforms and absolutely continuous functions, Math. Scand., 2, 153-157 (1954) · Zbl 0055.33501
[24] Fatemi, Mitra; Amini, Arash; Baboulaz, Loic; Vetterli, Martin, Shapes from pixels, IEEE Trans. Image Process., 25, 3, 1193-1206 (2016) · Zbl 1408.94176
[25] Fernandez-Granda, Carlos, Super-resolution of point sources via convex programming, Inform. Inference, 1-53 (2016) · Zbl 1386.94027
[26] Greenspan, Hayit, Super-resolution in medical imaging, Comput. J., 52, 1, 43-63 (2009)
[27] Hewitt, Edwin; Rubin, Herman, The maximum value of a Fourier-Stieltjes transform, Math. Scand., 3, 97-102 (1955) · Zbl 0065.01602
[28] Hille, Einar; Tamarkin, J. D., Remarks on a known example of a monotone continuous function, Amer. Math. Monthly, 36, 5, 255-264 (1929) · JFM 55.0142.06
[29] Kahane, Jean-Pierre; Salem, Raphaël, Ensembles Parfaits et Séries Trigonométriques (1963), Hermann: Hermann Paris · Zbl 0112.29304
[30] Katznelson, Yitzhak, An Introduction to Harmonic Analysis (2004), Cambridge University Press · Zbl 1055.43001
[31] Khaidukov, Valery; Landa, Evgeny; Moser, Tijmen Jan, Diffraction imaging by focusing-defocusing: an outlook on seismic superresolution, Geophysics, 69, 6, 1478-1490 (2004)
[32] Landau, Henry J., Maximum entropy and the moment problem, Bull. Amer. Math. Soc., 16, 1, 47-77 (1987) · Zbl 0617.42004
[33] Lindberg, Jari, Mathematical concepts of optical superresolution, J. Opt., 14, 8, Article 083001 pp. (2012)
[34] Ongie, Greg; Biswas, Sampurna; Jacob, Mathews, Convex recovery of continuous domain piecewise constant images from non-uniform Fourier samples, IEEE Trans. Signal Process., 66, 1, 236-250 (2017) · Zbl 1414.94869
[35] Ongie, Greg; Jacob, Mathews, Off-the-grid recovery of piecewise constant images from few Fourier samples, SIAM J. Imaging Sci., 9, 3, 1004-1041 (2016) · Zbl 1372.94198
[36] Pan, Hanjie; Blu, Thierry; Dragotti, Pier Luigi, Sampling curves with finite rate of innovation, IEEE Trans. Signal Process., 62, 2, 458-471 (2014) · Zbl 1394.94831
[37] Park, Sung C.; Park, Min K.; Kang, Moon G., Super-resolution image reconstruction: a technical overview, IEEE Signal Process. Mag., 20, 3, 21-36 (2003)
[38] Puschmann, K. G.; Kneer, F., On super-resolution in astronomical imaging, Astron. Astrophys., 436, 1, 373-378 (2005)
[39] Rieke, Fred, Spikes: Exploring the Neural Code (1999), MIT press · Zbl 0912.92004
[40] Rudin, Walter, Fourier Analysis on Groups (1962), John Wiley & Sons, Inc.: John Wiley & Sons, Inc. New York · Zbl 0105.09504
[41] Salem, Raphaël, On singular monotonic functions of the Cantor type, J. Math. Phys., 21, 69-82 (1942) · Zbl 0060.18606
[42] Tang, Gongguo; Bhaskar, Badri N.; Recht, Benjamin, Near minimax line spectral estimation, IEEE Trans. Inform. Theory, 61, 1, 499-512 (2015) · Zbl 1359.94181
[43] Tang, Gongguo; Bhaskar, Badri N.; Shah, Parikshit; Recht, Benjamin, Compressed sensing off the grid, IEEE Trans. Inform. Theory, 59, 11, 7465-7490 (2013) · Zbl 1364.94168
[44] Turán, Paul, On rational polynomials, Acta Univ. Szeged., Sect. Sci., 106-113 (1946) · Zbl 0060.05406
[45] Xu, Weiyu; Cai, Jian-Feng; Mishra, Kumar V.; Cho, Myung; Kruger, Anton, Precise semidefinite programming formulation of atomic norm minimization for recovering d-dimensional (D≥2) off-the-grid frequencies, (Information Theory and Applications Workshop. Information Theory and Applications Workshop, 2014 (2014), IEEE), 1-4
[46] Zygmund, Antoni, Trigonometric Series, vol. 1, 2002 (1959), Cambridge University Press · Zbl 0085.05601
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.