# 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
BLOOMP
Full Text:
##### References:
  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)  Azais, JM; De-Castro, Y; Gamboa, F, Spike detection from inaccurate samplings, Appl. Comput. Harmon. Anal., 38, 177-195, (2015) · Zbl 1308.94046  Borman, S., Stevenson, R.L.: Super-resolution from image sequences—a review. In: Midwest Symposium on Circuits and Systems, pp. 374-378 (1998)  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  Candès, EJ; Fernandez-Granda, C, Super-resolution from noisy data, J. Fourier Anal. Appl., 19, 1229-1254, (2013) · Zbl 1312.94015  Candès, EJ; Fernandez-Granda, C, Towards a mathematical theory of super-resolution, Commun. Pure Appl. Math., 67, 906-956, (2014) · Zbl 1350.94011  Chartrand, R, Exact reconstruction of sparse signals via nonconvex minimization, IEEE Signal Process. Lett., 10, 707-710, (2007)  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  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  De-Castro, Y; Gamboa, F, Exact reconstruction using Beurling minimal extrapolation, J. Math. Anal. Appl., 395, 336-354, (2012) · Zbl 1302.94019  Demanet, L., Nguyen, N.: The recoverability limit for superresolution via sparsity. Tech. rep., arXiv preprint arXiv:1502.01385 (2015) · Zbl 1261.62020  Donoho, DL, Superresolution via sparsity constraints, SIAM J. Math. Anal., 23, 1309-1331, (1992) · Zbl 0769.42007  Donoho, DL, Compressed sensing, IEEE Trans. Inf. Theory, 52, 1289-1306, (2006) · Zbl 1288.94016  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  Duval, V; Peyré, G, Exact support recovery for sparse spikes deconvolution, Found. Comput. Math., 15, 1-41, (2015) · Zbl 1327.65104  Facchinei, F., Pang, J.S.: Finite-dimensional variational inequalities and complementarity problems. Springer, Berlin (2007) · Zbl 1062.90002  Fannjiang, A; Liao, W, Coherence pattern-guided compressive sensing with unresolved grids, SIAM J. Imaging Sci., 5, 179-202, (2012) · Zbl 1250.65035  Fernandez-Granda, C.: Super-resolution of point sources via convex programming. Tech. rep., arXiv preprint arXiv:1507.07034 (2015) · Zbl 1386.94027  Goodman, J.W.: Introduction to Fourier Optics. Roberts and Company Publishers, Englewood (2005)  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  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  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  Mallat, S; Yu, G, Super-resolution with sparse mixing estimators, IEEE Trans. Image Process., 19, 2889-2900, (2010) · Zbl 1371.94252  Marquina, A; Osher, S, Image super-resolution by TV-regularization and Bregman iteration, J. Sci. Comput., 37, 367-382, (2008) · Zbl 1203.94014  Morgenshtern, V.I., Candès, E.J.: Super-resolution of positive sources: the discrete setup. Tech. rep., arXiv preprint arXiv:1504.00717 (2015)  Park, SC; Park, MK; Kang, MG, Super-resolution image reconstruction: a technical overview, IEEE Signal Process. Mag., 20, 21-36, (2003)  Peleg, D; Meir, R, A bilinear formulation for vector sparsity optimization, Signal Process., 88, 375-389, (2008) · Zbl 1186.94273  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  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  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  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  Shahram, M; Milanfar, P, Statistical and information-theoretic analysis of resolution in imaging, IEEE Trans. Inf. Theory, 8, 3411-3437, (2006) · Zbl 1309.94031  Shen, X; Pan, W; Zhu, Y, Likelihood-based selection and sharp parameter estimation, J. Am. Stat. Assoc., 107, 223-232, (2012) · Zbl 1261.62020  Tang, G; Bhaskar, BN; Recht, B, Near minimax line spectral estimation, IEEE Trans. Inf. Theory, 61, 499-512, (2015) · Zbl 1359.94181  Tropp, J, Greed is good: algorithmic results for sparse approximation, IEEE Trans. Inf. Theory, 50, 2231-2242, (2004) · Zbl 1288.94019  Tropp, J; Gilbert, A, Signal recovery from random measurements via orthogonal matching pursuit, IEEE Trans. Inf. Theory, 53, 4655-4666, (2007) · Zbl 1288.94022  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  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)  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  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  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.