×

zbMATH — the first resource for mathematics

Point source super-resolution via non-convex \(L_1\) based methods. (English) Zbl 1354.65125
In the super-resolution problem, one has to recover sparse signals \(x\in {\mathbb R}^N\) consisting only of separated peaks from frequency measurements up to a low frequency cutoff \(f_c\). Then \(\lambda_c = 1/f_c\) is called Rayleigh length of \(x\). If the peak separation \(\Delta\) of \(x\) fulfills \(\Delta \geq 2\lambda_c N\), then such sparse signal \(x\) can be recovered by \(\ell_1\) minimization (see [E. J. Candès and C. Fernandez-Granda, Commun. Pure Appl. Math. 67, No. 6, 906–956 (2014; Zbl 1350.94011)]).
In this paper, the authors analyze the so-called minimum separation factor MSF = \(\Delta/(\lambda_c\, N)\). Thus MSF \(\geq 2\) guarantees the exact recovery by \(\ell_1\) minimization. Numerical tests show that \(\ell_1\) minimization often fails when MSF \(< 1\). In this case, the authors investigate the recovery of \(x =(x_j)_{j=1}^N\) by non-convex \(\ell_1\) based minimization with the regularization term \(R(x) = \| x\|_1 - \| x\|_2\) or \[ R(x) = \sum_{j=1}^N \min \{|x_j|, \,\alpha\} \] with some \(\alpha>0\). The non-convex \(\ell_1\) based minimization problem is solved via a difference of convex algorithms such that local minimizers are obtained. The authors show several properties of the local minimizers. Numerical experiments for signals and images are examined.

MSC:
65K05 Numerical mathematical programming methods
94A12 Signal theory (characterization, reconstruction, filtering, etc.)
65J22 Numerical solution to inverse problems in abstract spaces
65T40 Numerical methods for trigonometric approximation and interpolation
90C26 Nonconvex programming, global optimization
Software:
BLOOMP
PDF BibTeX Cite
Full Text: DOI
References:
[1] Aubel, C., Stotz, D., Bölcskei, H.: A theory of super-resolution from short-time fourier transform measurements. Tech. rep., arXiv preprint arXiv:1509.01047 (2015)
[2] Azais, JM; De-Castro, Y; Gamboa, F, Spike detection from inaccurate samplings, Appl. Comput. Harmon. Anal., 38, 177-195, (2015) · Zbl 1308.94046
[3] Borman, S., Stevenson, R.L.: Super-resolution from image sequences—a review. In: Midwest Symposium on Circuits and Systems, pp. 374-378 (1998)
[4] Candes, E; Romberg, J; Tao, T, Stable signal recovery from incomplete and inaccurate measurements, Commun. Pure Appl. Math., 59, 1207-1223, (2006) · Zbl 1098.94009
[5] Candès, EJ; Fernandez-Granda, C, Super-resolution from noisy data, J. Fourier Anal. Appl., 19, 1229-1254, (2013) · Zbl 1312.94015
[6] Candès, EJ; Fernandez-Granda, C, Towards a mathematical theory of super-resolution, Commun. Pure Appl. Math., 67, 906-956, (2014) · Zbl 1350.94011
[7] Chartrand, R, Exact reconstruction of sparse signals via nonconvex minimization, IEEE Signal Process. Lett., 10, 707-710, (2007)
[8] Chartrand, R., Yin, W.: Iteratively reweighted algorithms for compressive sensing. In: International Conference on Acoustics, Speech, and Signal Processing (ICASSP), pp. 3869-3872 (2008) · Zbl 1268.49038
[9] Chen, X; Xu, F; Ye, Y, Lower bound theory of nonzero entries in solutions of \(L_{2}{-}L_{p}\) minimization, SIAM J. Sci. Comput., 32, 2832-2852, (2010) · Zbl 1242.90174
[10] De-Castro, Y; Gamboa, F, Exact reconstruction using Beurling minimal extrapolation, J. Math. Anal. Appl., 395, 336-354, (2012) · Zbl 1302.94019
[11] Demanet, L., Nguyen, N.: The recoverability limit for superresolution via sparsity. Tech. rep., arXiv preprint arXiv:1502.01385 (2015) · Zbl 1261.62020
[12] Donoho, DL, Superresolution via sparsity constraints, SIAM J. Math. Anal., 23, 1309-1331, (1992) · Zbl 0769.42007
[13] Donoho, DL, Compressed sensing, IEEE Trans. Inf. Theory, 52, 1289-1306, (2006) · Zbl 1288.94016
[14] Donoho, D.L., Johnstone, I.M., Hoch, J.C., Stern, A.S.: Maximum entropy and the nearly black object. J. R. Sat. Soc. Series B (Methodological), 41-81 (1992) · Zbl 0788.62103
[15] Duval, V; Peyré, G, Exact support recovery for sparse spikes deconvolution, Found. Comput. Math., 15, 1-41, (2015) · Zbl 1327.65104
[16] Facchinei, F., Pang, J.S.: Finite-dimensional variational inequalities and complementarity problems. Springer, Berlin (2007) · Zbl 1062.90002
[17] Fannjiang, A; Liao, W, Coherence pattern-guided compressive sensing with unresolved grids, SIAM J. Imaging Sci., 5, 179-202, (2012) · Zbl 1250.65035
[18] Fernandez-Granda, C.: Super-resolution of point sources via convex programming. Tech. rep., arXiv preprint arXiv:1507.07034 (2015) · Zbl 1386.94027
[19] Goodman, J.W.: Introduction to Fourier Optics. Roberts and Company Publishers, Englewood (2005)
[20] Lai, MJ; Xu, Y; Yin, W, Improved iteratively reweighted least squares for unconstrained smoothed lq minimization, SIAM J. Numer. Anal., 5, 927-957, (2013) · Zbl 1268.49038
[21] Lou, Y., Osher, S., Xin, J.: Computational aspects of constrained L1-L2 minimization for compressive sensing. In: Modelling, Computation and Optimization in Information Systems and Management Sciences, pp. 169-180. Springer (2015) · Zbl 1370.90176
[22] Lou, Y; Yin, P; He, Q; Xin, J, Computing sparse representation in a highly coherent dictionary based on difference of l1 and l2, J. Sci. Comput., (2014) · Zbl 1327.65111
[23] Mallat, S; Yu, G, Super-resolution with sparse mixing estimators, IEEE Trans. Image Process., 19, 2889-2900, (2010) · Zbl 1371.94252
[24] Marquina, A; Osher, S, Image super-resolution by TV-regularization and Bregman iteration, J. Sci. Comput., 37, 367-382, (2008) · Zbl 1203.94014
[25] Morgenshtern, V.I., Candès, E.J.: Super-resolution of positive sources: the discrete setup. Tech. rep., arXiv preprint arXiv:1504.00717 (2015)
[26] Park, SC; Park, MK; Kang, MG, Super-resolution image reconstruction: a technical overview, IEEE Signal Process. Mag., 20, 21-36, (2003)
[27] Peleg, D; Meir, R, A bilinear formulation for vector sparsity optimization, Signal Process., 88, 375-389, (2008) · Zbl 1186.94273
[28] Pham-Dinh, T; Le-Thi, HA, Convex analysis approach to dc programming: theory, algorithms and applications, Acta Math. Vietnam., 22, 289-355, (1997) · Zbl 0895.90152
[29] Pham-Dinh, T; Le-Thi, HA, A DC optimization algorithm for solving the trust-region subproblem, SIAM J. Optim., 8, 476-505, (1998) · Zbl 0913.65054
[30] Pham-Dinh, T; Le-Thi, HA, The dc (difference of convex functions) programming and dca revisited with dc models of real world nonconvex optimization problems, Ann. Oper. Res., 133, 23-46, (2005) · Zbl 1116.90122
[31] Protter, M; Elad, M; Takeda, H; Milanfar, P, Generalizing the non-local-means to super-resolution reconstruction, IEEE Trans. Image Process., 18, 36-51, (2009) · Zbl 1371.94300
[32] Shahram, M; Milanfar, P, Statistical and information-theoretic analysis of resolution in imaging, IEEE Trans. Inf. Theory, 8, 3411-3437, (2006) · Zbl 1309.94031
[33] Shen, X; Pan, W; Zhu, Y, Likelihood-based selection and sharp parameter estimation, J. Am. Stat. Assoc., 107, 223-232, (2012) · Zbl 1261.62020
[34] Tang, G; Bhaskar, BN; Recht, B, Near minimax line spectral estimation, IEEE Trans. Inf. Theory, 61, 499-512, (2015) · Zbl 1359.94181
[35] Tropp, J, Greed is good: algorithmic results for sparse approximation, IEEE Trans. Inf. Theory, 50, 2231-2242, (2004) · Zbl 1288.94019
[36] Tropp, J; Gilbert, A, Signal recovery from random measurements via orthogonal matching pursuit, IEEE Trans. Inf. Theory, 53, 4655-4666, (2007) · Zbl 1288.94022
[37] Wang, Z; Liu, H; Zhang, T, Optimal computational and statistical rates of convergence for sparse nonconvex learning problems, Ann. Stat., 42, 2164, (2014) · Zbl 1302.62066
[38] Xu, Z; Chang, X; Xu, F; Zhang, H, \(L_{1/2}\) regularization: a thresholding representation theory and a fast solver, IEEE Trans. Neural Netw., 23, 1013-1027, (2012)
[39] Yang, J; Wright, J; Huang, T; Ma, Y, Image super-resolution via sparse representation, IEEE Trans. Image Process., 19, 2861-2873, (2010) · Zbl 1371.94429
[40] Yin, P; Lou, Y; He, Q; Xin, J, Minimization of \(l_1{-}l_2\) for compressed sensing, SIAM J. Sci. Comput., 37, a536-a563, (2015) · Zbl 1316.90037
[41] Zhang, T.: Multi-stage convex relaxation for learning with sparse regularization. In: Advances in Neural Information Processing Systems, pp. 1929-1936 (2009) · Zbl 1316.90037
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.