In this paper, we propose two classes of the approximations to the cardinality function via the Moreau envelope of the $ \ell_{1} $ norm. We show that these two approximations are good choices of the merit function for sparsity and are essentially the truncated $ \ell_{1} $ norm and the truncated $ \ell_{2} $ norm. Moreover, we apply the approximations to solve sparse signal recovery problems and then provide new weights for reweighted $ \ell_{1} $ minimization and reweighted least squares to find sparse solutions of underdetermined linear systems of equations. Finally, we present some numerical experiments to illustrate our results.
Citation: |
[1] |
Q. Berthet and P. Rigollet, Optimal detection of sparse principal components in high dimension, Annal. Statistics, 41 (2013), 1780-1815.
doi: 10.1214/13-AOS1127.![]() ![]() ![]() |
[2] |
Md. Z. A. Bhot, M. O. Ahmad and M. N. S. Swamy, An improved fast iterative shrinkage thresholding algorithm for image deblurring, SIAM J. Imaging Sci., 8 (2015), 1640-1657.
doi: 10.1137/140970537.![]() ![]() ![]() |
[3] |
A. M. Bruckstein, D. L. Donoho and M. Elad, From sparse solutions of systems of equations to sparse modeling of signals and images, SIAM Review, 51 (2009), 34-81.
doi: 10.1137/060657704.![]() ![]() ![]() |
[4] |
E.J. Candès and B. Recht, Exact matrix completion via convex optimization, Found. Comput. Math., 9 (2009), 717-772.
doi: 10.1007/s10208-009-9045-5.![]() ![]() ![]() |
[5] |
E. J. Candès, J. Romberg and T. Tao, Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inf. Theory, 52 (2006), 489-509.
doi: 10.1109/TIT.2005.862083.![]() ![]() ![]() |
[6] |
E. J. Candés, J. Romberg and T. Tao, Stable signal recovery from incomplete and inaccurate measurements, Comm. Pure Appl. Math., 59 (2006), 1207-1223.
doi: 10.1002/cpa.20124.![]() ![]() ![]() |
[7] |
E. J. Candès and T. Tao, Decoding by linear programming, IEEE Trans. Inf. Theory, 51 (2005), 4203-4215.
doi: 10.1109/TIT.2005.858979.![]() ![]() ![]() |
[8] |
E. J. Candès and T. Tao, Near-optimal signal recovery from random projections: Universal encoding strategies?, IEEE Trans. Inf. Theory, 52 (2006), 5406-5425.
doi: 10.1109/TIT.2006.885507.![]() ![]() ![]() |
[9] |
E. J. Candès, M. Wakin and S. Boyd, Enhancing sparsity by reweighted $\ell_{1}$ minimization, J. Fourier Anal. Appl., 14 (2008), 877-905.
doi: 10.1007/s00041-008-9045-x.![]() ![]() ![]() |
[10] |
R. Chartrand, Exact reconstruction of sparse signals via nonconvex minimization, IEEE Signal Process. Lett., 14 (2007), 707-710.
doi: 10.1109/LSP.2007.898300.![]() ![]() |
[11] |
R. Chartrand and W. Yin, Iteratively reweighted algorithms for compressive sensing, in: Proc. Int. Conf. Accoust. Speech, Signal Process., 2008, 3869–3872.
doi: 10.1109/ICASSP.2008.4518498.![]() ![]() |
[12] |
S. S. Chen, D. L. Donoho and M. A. Saunders, Atomic decomposition by basis pursuit, SIAM J. Sci. Comput., 43 (2001), 129-159.
doi: 10.1137/S003614450037906X.![]() ![]() ![]() |
[13] |
A. M. Christopher, M. Arian and G. B. Richard, From denoising to compressed sensing, IEEE Trans. Inf. Theory, 62 (2016), 5117-5144.
doi: 10.1109/TIT.2016.2556683.![]() ![]() ![]() |
[14] |
A. Cohen, W. Dahmen and R. DeVore, Compressed sensing and best k-term approximation, J. American Math. Soc., 22 (2009), 211-231.
doi: 10.1090/S0894-0347-08-00610-3.![]() ![]() ![]() |
[15] |
I. Daubechies, M. Defrise and M. C. De, An iterative thresholding algorithm for linear inverse problems with a sparsity constraint, Commun. Pur. Appl. Math., 57 (2004), 1413-1457.
doi: 10.1002/cpa.20042.![]() ![]() ![]() |
[16] |
D. L. Donoho, Compressed sensing, IEEE Trans. Inf. Theory, 52 (2006), 1289-1306.
doi: 10.1109/TIT.2006.871582.![]() ![]() ![]() |
[17] |
E. Esser, Y. F. Lou and J. Xin, A method for finding structured sparse solutions to nonnegative least squares problems with applications, SIAM J. maging Sci., 6 (2013), 2010-2046.
doi: 10.1137/13090540X.![]() ![]() ![]() |
[18] |
J. Fan and R. Li, Variable selection via nonconcave penalized likelihood and its oracle properties, J. Amer. Statist. Assoc., 96 (2001), 1348-1360.
doi: 10.1198/016214501753382273.![]() ![]() ![]() |
[19] |
M. Fornasier, S. Peter, H. Rauhut and S. Worm, Conjugate gradient acceleration of iteratively re-weighted least squares methods, Comput. Optim. Appl., 65 (2016), 205-259.
doi: 10.1007/s10589-016-9839-8.![]() ![]() ![]() |
[20] |
S. Foucart and H. Rauhut, A Mathematical Introduction to Compressive Sensing, Birkhaäuser, Basel, 2013.
doi: 10.1007/978-0-8176-4948-7.![]() ![]() ![]() |
[21] |
S. Foucart and M. Lai, Sparsest solutions of underdetermined linear systems via $\ell_{q}$-minimization for $0 <q\leq1$, ppl. Comput. Harmon. Anal., 26 (2009), 395-407.
doi: 10.1016/j.acha.2008.09.001.![]() ![]() ![]() |
[22] |
I. F. Gorodnitsky and B. D. Rao, Sparse signal reconstruction from limited data using FOCUSS, A re-weighted minimum norm algorithm, IEEE Trans. Signal Process., 45 (1997), 600-616.
doi: 10.1109/78.558475.![]() ![]() |
[23] |
J. Huang, Y. Jiao, B. Jin, J. Liu, X. Lu and C. Yang., A unified primal dual active set algorithm for nonconvex sparse recovery, arXiv: 1310.1147.
![]() |
[24] |
J. Huang, Y. Jiao, Y. Liu and X. Lu, A constructive approach to $L_{0}$-penalized regression, J. Mach. Learn. Res., 19 (2018), Paper No. 10, 37 pp.
![]() ![]() |
[25] |
Y. Jiao, B. Jin and X. Lu, A primal dual active set with continuation algorithm for the $\ell^{0}$-regularized optimization problem, Appl. Comput. Harmon. Anal., 39 (2015), 400-426.
doi: 10.1016/j.acha.2014.10.001.![]() ![]() ![]() |
[26] |
R. Kueng, H. Rauhut and U. Terstiege., Low rank matrix recovery from rank one measurements, Appl. Comput. Harmon. Anal., 42 (2017), 88-116.
doi: 10.1016/j.acha.2015.07.007.![]() ![]() ![]() |
[27] |
M. Lai and J. Wang, An unconstrained $\ell_{q}$ minimization with $0 < q\leq 1$ for sparse solution of underdetermined linear systems, SIAM J. Optim., 21 (2011), 82-101.
doi: 10.1137/090775397.![]() ![]() ![]() |
[28] |
Z. S. Lu, Iterative reweighted minimization methods for $\ell_{p}$ regularized unconstrained nonlinear programming, Mathematical Program., 147 (2014), 277-307.
doi: 10.1007/s10107-013-0722-4.![]() ![]() ![]() |
[29] |
Z. S. Lu and X. Li, Sparse recovery via partial regularization: Models, theory, and algorithms, Math. Oper. Res., 43 (2018), 1290-1316.
doi: 10.1287/moor.2017.0905.![]() ![]() ![]() |
[30] |
J. Lv and Y. Fan, A unified approach to model selection and sparse recovery using regularized least squares, Ann. Statist., 37 (2009), 3498-3528.
doi: 10.1214/09-AOS683.![]() ![]() ![]() |
[31] |
H. Mansour and R. Saab, Recovery analysis for weighted $\ell_{1}$-minimization using the null space property, Appl. Comput. Harmon. Anal., 43 (2017), 23-38.
doi: 10.1016/j.acha.2015.10.005.![]() ![]() ![]() |
[32] |
F. D. Marco, A. D. Mark and T. Dharmpal et al., Single-pixel imaging via compressive sampling, IEEE Trans. Signal Magazine, 25 (2008), 83-91.
doi: 10.1109/MSP.2007.914730.![]() ![]() |
[33] |
H. Mohimani, B. Z. Massoud and C. Jutten, A fast approach for overcomplete sparse decomposition based on smoothed $ \ell^{0} $ norm, IEEE Trans. Signal Process., 57 (2009), 289-301.
doi: 10.1109/TSP.2008.2007606.![]() ![]() ![]() |
[34] |
B. K. Natarajan, Sparse approximate solutions to linear systems, SIAM J. Comput., 24 (1995), 227-234.
doi: 10.1137/S0097539792240406.![]() ![]() ![]() |
[35] |
D. Needell and J. A. Tropp, CoSaMP: Iterative signal recovery from incomplete and inaccurate samples, Appl. Comput. Harmon. Anal., 26 (2009), 301-321.
doi: 10.1016/j.acha.2008.07.002.![]() ![]() ![]() |
[36] |
H. L. Royden and P. M. Fitzpatrick, Real Analysis, 4$^{nd}$ edition, Macmillan Publishing Company, New York, 2010.
![]() |
[37] |
I. Selesnick, Sparse regularization via convex analysis, IEEE Trans. Signal Process., 65 (2017), 4481-4494.
doi: 10.1109/TSP.2017.2711501.![]() ![]() ![]() |
[38] |
I. Selesnick and M. Farshchian, Sparse signal approximation via nonseparable regularization, IEEE Trans. Signal Process., 65 (2017), 2561-2575.
doi: 10.1109/TSP.2017.2669904.![]() ![]() ![]() |
[39] |
G. W. Stewart, On scaled projections and pseudoinverses, Linear Algebra Appl., 112 (1989), 189-193.
doi: 10.1016/0024-3795(89)90594-6.![]() ![]() ![]() |
[40] |
B. Tian, X. Yang and K. Meng, An interior-point $\ell_{\frac{1}{2}}$-penalty method for inequality constrained nonlinear optimization, J. Ind. Manag. Optim., 12 (2016), 949-973.
doi: 10.3934/jimo.2016.12.949.![]() ![]() ![]() |
[41] |
R. Tibshirani, Regression shrinkage and selection via the lasso, J. Roy. Statist. Soc. Ser. B, 58 (1996), 267-288.
doi: 10.1111/j.2517-6161.1996.tb02080.x.![]() ![]() ![]() |
[42] |
J. A. Tropp and A. C. Gilbert, Signal recovery from random measurements via orthogonal matching pursuit, IEEE Trans. Inf. Theory, 53 (2007), 4655-4666.
doi: 10.1109/TIT.2007.909108.![]() ![]() ![]() |
[43] |
J. Wang and X. T. Wang, Sparse approximate reconstruction decomposed by two optimization problems, Circ. Syst. Signal Process., 37 (2018), 2164-2178.
doi: 10.1007/s00034-017-0667-6.![]() ![]() ![]() |
[44] |
D. Wipf and S. Nagarajan, Iterative reweighted $\ell_1 $ and $\ell_2 $ methods for finding sparse solutions, IEEE J. Select. Topics Signal Process., 4 (2010), 317-329.
doi: 10.1109/JSTSP.2010.2042413.![]() ![]() |
[45] |
J. Wright, A. Y. Yang and G. Arvind et al., Robust face recognition via sparse representation, IEEE Trans. Pattern Analysis and Machine Intelligence, 31 (2008), 210-227.
doi: 10.1109/AFGR.2008.4813404.![]() ![]() |
[46] |
P. Yin, Y. Lou, Q. He and J. Xin, Minimization of $\ell_{1-2}$ for compressed sensing, SIAM J. Sci. Comput., 37 (2015), A536–A563.
doi: 10.1137/140952363.![]() ![]() ![]() |
[47] |
C.-H. Zhang, Nearly unbiased variable selection under minimax concave penalty, Statist. Sci., 2 (2010), 894-942.
doi: 10.1214/09-AOS729.![]() ![]() ![]() |
[48] |
C.-H. Zhang and T. Zhang, A general theory of concave regularization for high-dimensional sparse estimation problems, Statist. Sci., 27 (2012), 576-593.
doi: 10.1214/12-STS399.![]() ![]() ![]() |
[49] |
T. Zhang, Analysis of multi-stage convex relaxation for sparse regularization, J. Mach. Learn. Res., 11 (2010), 1081-1107.
![]() ![]() |
[50] |
Y.-B. Zhao, RSP-based analysis for sparsest and least $\ell_{1}$-norm solutions to underdetermined linear systems, IEEE Trans. Signal Process., 61 (2013), 5777-5788.
doi: 10.1109/TSP.2013.2281030.![]() ![]() ![]() |
[51] |
Y.-B. Zhao and M. Kocvara, A new computational method for the sparsest solutions to systems of linear equations, SIAM J. Optim., 25 (2015), 1110-1134.
doi: 10.1137/140968240.![]() ![]() ![]() |
[52] |
Y. Zhao and D. Li, Reweighted $\ell_{1}$-minimization for sparse solutions to underdetermined linear systems, SIAM J. Optim., 22 (2012), 1065-1088.
doi: 10.1137/110847445.![]() ![]() ![]() |
Comparison of success rates of finding the
Comparison of
Comparison of success rates of finding the
Comparison of