×

A generalized elastic net regularization with smoothed \(\ell _{q}\) penalty for sparse vector recovery. (English) Zbl 1387.90246

Summary: In this paper, we propose an iterative algorithm for solving the generalized elastic net regularization problem with smoothed \(\ell _{q}\) \((0<q \leq 1)\) penalty for recovering sparse vectors. We prove the convergence result of the algorithm based on the algebraic method. Under certain conditions, we show that the iterative solutions converge to a local minimizer of the generalized elastic net regularization problem and we also present an error bound. Theoretical analysis and numerical results show that the proposed algorithm is promising.

MSC:

90C30 Nonlinear programming
90C90 Applications of mathematical programming

Software:

PDCO
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Donoho, D.L.: Compressed sensing. IEEE Trans. Inf. Theory 52, 1289-1306 (2006) · Zbl 1288.94016 · doi:10.1109/TIT.2006.871582
[2] Lustig, M., Donoho, D.L., Santos, J.M., Pauly, J.M.: Compressed sensing MRI. IEEE Signal Process. Mag. 25, 72-82 (2008) · doi:10.1109/MSP.2007.914728
[3] Duarte, M.F., Eldar, Y.C.: Structured compressed sensing: from theory to applications. IEEE Trans. Signal Process. 59, 4053-4085 (2011) · Zbl 1392.94188 · doi:10.1109/TSP.2011.2161982
[4] Natraajan, B.K.: Sparse approximation to linear systems. SIAM J. Comput. 24(2), 227-234 (1995) · Zbl 0827.68054 · doi:10.1137/S0097539792240406
[5] Chen, S.S., Donoho, D.L., Saunders, M.A.: Atomic decomposition by basis pursuit. SIAM J. Sci. Comput. 20(1), 33-61 (1998) · Zbl 0919.94002 · doi:10.1137/S1064827596304010
[6] Daubechies, I., Defries, M., De Mol, C.: An iterative thresholding algorithm for linear inverse problems with a sparsity constraint. Commun. Pure Appl. Math. 57, 1413-1457 (2004) · Zbl 1077.65055 · doi:10.1002/cpa.20042
[7] Tibshirani, R.: Regression shrinkage and selection via the lasso. J. R. Stat. Soc. Ser. B 58(1), 267-288 (1996) · Zbl 0850.62538
[8] Zou, H.: The adaptive lasso and its oracle properties. J. Am. Stat. Assoc. 101(467), 1418-1429 (2006) · Zbl 1171.62326 · doi:10.1198/016214506000000735
[9] Meinshausen, N., Yu, B.: Lasso-type recovery of sparse representations for high-dimensional data. Ann. Stat. 37(1), 246-270 (2009) · Zbl 1155.62050 · doi:10.1214/07-AOS582
[10] Zou, H., Hastie, T.: Regularization and variable selection via the elastic net. J. R. Stat. Soc. B 67(2), 301-320 (2005) · Zbl 1069.62054 · doi:10.1111/j.1467-9868.2005.00503.x
[11] Chen, X., Xu, F., Ye, Y.: Lower bound theory of nonzero entries in solutions of \[\ell_2\] ℓ \[2-\ell_p\] ℓp minimization. SIAM J. Sci. Comput. 32, 2832-2852 (2010) · Zbl 1242.90174 · doi:10.1137/090761471
[12] Chartrand, R.: Exact reconstructions of sparse signals via nonconvex minimization. IEEE Signal Process. Lett. 14(10), 707-710 (2007) · doi:10.1109/LSP.2007.898300
[13] Chartrand, R., Staneva, V.: Restricted isometry properties and nonconvex compressive sensing. Inverse Probl. 24, 1-14 (2008) · Zbl 1143.94004 · doi:10.1088/0266-5611/24/3/035020
[14] Lai, M.J., Wang, J.Y.: An unconstrained \[\ell_q\] ℓq minimization with \[0<q\le 10\]<q≤1 for sparse solution of underdetermined linear systems. SIAM J. Optim. 21(1), 82-101 (2011) · Zbl 1220.65051 · doi:10.1137/090775397
[15] Lai, M.J., Xu, Y.Y., Yin, W.T.: Improved iteratively reweighted least squares for unconstrained smoothed \[\ell_q\] ℓq minimization. SIAM J. Numer. Anal. 51(2), 927-957 (2013) · Zbl 1268.49038 · doi:10.1137/110840364
[16] Efron, B., Hastie, T., Johnstone, I., Tibshirani, R.: Least angle regression. Ann. Stat. 32(2), 407-499 (2004) · Zbl 1091.62054 · doi:10.1214/009053604000000067
[17] Bian, W., Chen, X.: Worst-case complexity of smoothing quadratic regularization methods for nonLipschitzian optimization. SIAM J. Optim. 23(3), 1718-1741 (2013) · Zbl 1282.90175 · doi:10.1137/120864908
[18] Bian, W., Chen, X.: Linearly Constrained Non-Lipschitz Optimization for Image Restoration. SIAM J. Imaging Sci. 8(4), 2294-2322 (2015) · Zbl 1327.90299 · doi:10.1137/140985639
[19] Liu, Y.F., Ma, S.Q., Dai, Y.H., Zhang, S.Z.: A smoothing SQP framework for a class of composite \[L_q\] Lq minimization over polyhedron. Math. Program. Ser. A (2015). doi:10.1007/s10107-015-0939-5 · Zbl 1346.90684 · doi:10.1007/s10107-015-0939-5
[20] Candès, E.J., Wakin, M.B., Boyd, S.P.: Enchaning sparsity by reweighted \[\ell_1\] ℓ1 minimization. J. Fourier Anal. Appl. 14, 877-905 (2008) · Zbl 1176.94014 · doi:10.1007/s00041-008-9045-x
[21] Chartrand, R., Yin, W.: Iteratively reweighted algorithms for compressive sensing. In: Proceeding of International Conference on Acoustics, Speech, Signal Processing (ICASSP’08), PP. 3869-3872 (2008) · Zbl 1393.94353
[22] Daubechies, I., Devore, R., Fornasier, M., Güntük, C.S.: Iteratively reweighted least squares minimization for sparse recovery. Commun. Pure Appl. Math. 63, 1-38 (2010) · Zbl 1202.65046 · doi:10.1002/cpa.20303
[23] Garcia, C.B., Li, T.Y.: On the number of solutions to polynomial systems of equations. SIAM J. Numer. Anal. 17(4), 540-546 (1980) · Zbl 0445.65037 · doi:10.1137/0717046
[24] Sun, Q.: Sparse approximation property and stable recovery of sparse singals from noisy measurements. IEEE Trans. Signal Process. 59, 5086-5090 (2011) · Zbl 1393.94449 · doi:10.1109/TSP.2011.2161470
[25] Marjanovic, G., Solo, V.: On \[\ell_q\] ℓq optimization and matrix completion. IEEE Trans. Signal Process. 60, 5714-5724 (2012) · Zbl 1393.94353 · doi:10.1109/TSP.2012.2212015
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.