×

Sparse solutions by a quadratically constrained \(\ell q\) (\(0 < q< 1\)) minimization model. (English) Zbl 07362331

Summary: Finding sparse solutions to a system of equations and/or inequalities is an important topic in many application areas such as signal processing, statistical regression and nonparametric modeling. Various continuous relaxation models have been proposed and widely studied to deal with the discrete nature of the underlying problem. In this paper, we propose a quadratically constrained \(\ell q\) (\(0 < q< 1\)) minimization model for finding sparse solutions to a quadratic system. We prove that solving the proposed model is strongly NP-hard. To tackle the computation difficulty, a first order necessary condition for local minimizers is derived. Various properties of the proposed model are studied for designing an active-set-based descent algorithm to find candidate solutions satisfying the proposed condition. In addition to providing a theoretical convergence proof, we conduct extensive computational experiments using synthetic and real-life data to validate the effectiveness of the proposed algorithm and to show the superior capability in finding sparse solutions of the proposed model compared with other known models in the literature. We also extend our results to a quadratically constrained \(\ell q\) (\(0 < q< 1\)) minimization model with multiple convex quadratic constraints for further potential applications.
Summary of Contribution: In this paper, we propose and study a quadratically constrained \(\ell_q\) minimization (\(0 < q < 1\)) model for finding sparse solutions to a quadratic system which has wide applications in sparse signal recovery, image processing and machine learning. The proposed quadratically constrained \(\ell_q\) minimization model extends the linearly constrained \(\ell_q\) and unconstrained \(\ell_2- \ell_q\) models. We study various properties of the proposed model in aim of designing an efficient algorithm. Especially, we propose an unrelaxed KKT condition for local/global minimizers. Followed by the properties studied, an active-set based descent algorithm is then proposed with its convergence proof being given. Extensive numerical experiments with synthetic and real-life Sparco datasets are conducted to show that the proposed algorithm works very effectively and efficiently. Its sparse recovery capability is superior to that of other known models in the literature.
The online appendices are available at https://doi.org/10.1287/ijoc.2020.1004.

MSC:

90Cxx Mathematical programming

Software:

PDCO; FPC_AS; SPGL1
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Arrow KJ , Hurwicz L , Uzawa H (1961) Constraint qualifications in maximization problems. Naval Res. Logist. Quart. 8(2):175-191.Crossref, Google Scholar · Zbl 0129.34103 · doi:10.1002/nav.3800080206
[2] Baraniuk RG (2007) Compressive sensing. IEEE Signal Processing Magazine 24(4):118-121.Crossref, Google Scholar · doi:10.1109/MSP.2007.4286571
[3] Bertsimas D , King A (2015) OR Forum—An algorithmic approach to linear regression. Oper. Res. 64(1):2-16.Link, Google Scholar · Zbl 1338.90272
[4] Blumensath T , Davies ME (2008) Iterative thresholding for sparse approximations. J. Fourier Anal. Appl. 14(5):629-654.Crossref, Google Scholar · Zbl 1175.94060 · doi:10.1007/s00041-008-9035-z
[5] Bruckstein A , Donoho D , Elad M (2009) From sparse solutions of systems of equations to sparse modeling of signals and images. SIAM Rev. 51(1):34-81.Crossref, Google Scholar · Zbl 1178.68619 · doi:10.1137/060657704
[6] Candès EJ (2008) The restricted isometry property and its implications for compressed sensing. C. R. Math. Acad. Sci. Paris 346(9):589-592.Crossref, Google Scholar · Zbl 1153.94002 · doi:10.1016/j.crma.2008.03.014
[7] Candès EJ , Tao T (2005) Decoding by linear programming. IEEE Trans. Inform. Theory 51(12):4203-4215.Crossref, Google Scholar · Zbl 1264.94121 · doi:10.1109/TIT.2005.858979
[8] Candès EJ , Romberg J , Tao T (2006) Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Trans. Inform. Theory 52(2):489-509.Crossref, Google Scholar · Zbl 1231.94017 · doi:10.1109/TIT.2005.862083
[9] Candès EJ , Wakin MB , Boyd SP (2008) Enhancing sparsity by reweighted ℓ 1 minimization. J. Fourier Anal. Appl. 14(5):877-905.Crossref, Google Scholar · Zbl 1176.94014 · doi:10.1007/s00041-008-9045-x
[10] Canon M , Cullum C , Polak E (1966) Constrained minimization problems in finite-dimensional spaces. SIAM J. Control 4(3):528-547.Crossref, Google Scholar · Zbl 0145.34202 · doi:10.1137/0304041
[11] Carrillo RE , Barner KE (2009) Iteratively re-weighted least squares for sparse signal reconstruction from noisy measurements. 2009 43rd Annual Conf. Inform. Sci. Systems, Baltimore, 448-453.Google Scholar
[12] Chartrand R (2007) Exact reconstruction of sparse signals via nonconvex minimization. IEEE Signal Processing Lett. 14(10):707-710.Crossref, Google Scholar · doi:10.1109/LSP.2007.898300
[13] Chartrand R , Staneva V (2008) Restricted isometry properties and nonconvex compressive sensing. Inverse Problems 24(3):035020.Crossref, Google Scholar · Zbl 1143.94004 · doi:10.1088/0266-5611/24/3/035020
[14] Chen X , Xiang S (2016) Sparse solutions of linear complementarity problems. Math. Programming 159(1):539-556.Crossref, Google Scholar · Zbl 1346.90776 · doi:10.1007/s10107-015-0950-x
[15] Chen YC , Domínguez-García AD , Sauer PW (2015) A sparse representation approach to online estimation of power system distribution factors. IEEE Trans. Power Systems 30(4):1727-1738.Crossref, Google Scholar · doi:10.1109/TPWRS.2014.2356399
[16] Chen S , Donoho D , Saunders M (2001) Atomic decomposition by basis pursuit. SIAM Rev. 43(1):129-159.Crossref, Google Scholar · Zbl 0979.94010 · doi:10.1137/S003614450037906X
[17] Chen X , Xu F , Ye Y (2010) Lower bound theory of nonzero entries in solutions of ℓ 2 - ℓ p minimization. SIAM J. Sci. Comput. 32(5):2832-2852.Crossref, Google Scholar · Zbl 1242.90174 · doi:10.1137/090761471
[18] Chen X , Ge D , Wang Z , Ye Y (2014) Complexity of unconstrained L 2 - L p minimization. Math. Programming 143(1):371-383.Crossref, Google Scholar · Zbl 1285.90039 · doi:10.1007/s10107-012-0613-0
[19] Daubechies I , Defrise M , De Mol C (2004) An iterative thresholding algorithm for linear inverse problems with a sparsity constraint. Comm. Pure Appl. Math. 57(11):1413-1457.Crossref, Google Scholar · Zbl 1077.65055 · doi:10.1002/cpa.20042
[20] Donoho DL (2006) Compressed sensing. IEEE Trans. Inform. Theory 52(4):1289-1306.Crossref, Google Scholar · Zbl 1288.94016 · doi:10.1109/TIT.2006.871582
[21] Donoho DL , Elad M (2003) Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ 1 minimization. Proc. Natl. Acad. Sci. USA 100(5):2197-2202.Crossref, Google Scholar · Zbl 1064.94011 · doi:10.1073/pnas.0437847100
[22] Efron B , Hastie T , Johnstone I , Tibshirani R (2004) Least angle regression. Ann. Statist. 32(2):407-499.Crossref, Google Scholar · Zbl 1091.62054 · doi:10.1214/009053604000000067
[23] Fang S-C , Xing W (2013) Linear Conic Programming: Theory and Applications (Science Press, Beijing).Google Scholar
[24] Farias VF , Jagabathula S , Shah D (2013) A nonparametric approach to modeling choice with limited data. Management Sci. 59(2):305-322.Link, Google Scholar
[25] Foucart S (2010) A note on guaranteed sparse recovery via ℓ 1 -minimization. Appl. Comput. Harmonic Anal. 29(1):97-103.Crossref, Google Scholar · Zbl 1198.41011 · doi:10.1016/j.acha.2009.10.004
[26] Foucart S , Lai MJ (2009) Sparsest solutions of underdetermined linear systems via ℓ q -minimization for 0 < q < 1. Appl. Comput. Harmonic Anal. 26(3):395-407.Crossref, Google Scholar · Zbl 1171.90014 · doi:10.1016/j.acha.2008.09.001
[27] Garey MR , Johnson DS (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, New York).Google Scholar · Zbl 0411.68039
[28] Ge D , He R , He S (2017) An improved algorithm for the L 2 - L p minimization problem. Math. Programming 166(1):131-158.Crossref, Google Scholar · Zbl 1386.90146 · doi:10.1007/s10107-016-1107-2
[29] Ge D , Jiang X , Ye Y (2011) A note on the complexity of L p minimization. Math. Programming 129(2):285-299.Crossref, Google Scholar · Zbl 1226.90076 · doi:10.1007/s10107-011-0470-2
[30] Haeser G , Liu H , Ye Y (2019) Optimality condition and complexity analysis for linearly-constrained optimization without differentiability on the boundary. Math. Programming 178:263-299.Crossref, Google Scholar · Zbl 1423.90248 · doi:10.1007/s10107-018-1290-4
[31] Jiang S (2019) Sub-one ℓ p quasi-norm minimization and applications. Unpublished doctoral dissertation, North Carolina State University.Google Scholar
[32] Lai MJ , Wang J (2011) An unconstrained ℓ q minimization with 0 < q < 1 for sparse solution of underdetermined linear systems. SIAM J. Optim. 21(1):82-101.Crossref, Google Scholar · Zbl 1220.65051 · doi:10.1137/090775397
[33] Lai MJ , Xu Y , Yin W (2013) Improved iteratively reweighted least squares for unconstrained smoothed ℓ q minimization. SIAM J. Numer. Anal. 51(2):927-957.Crossref, Google Scholar · Zbl 1268.49038 · doi:10.1137/110840364
[34] Li HL , Huang YH , Fang S-C (2013) A logarithmic method for reducing binary variables and inequality constraints in solving task assignment problems. INFORMS J. Comput. 25(4):643-653.Link, Google Scholar
[35] Li Y , Reyes KG , Vazquez-Anderson J , Wang Y , Contreras LM , Powell WB (2018) A knowledge gradient policy for sequencing experiments to identify the structure of RNA molecules using a sparse additive belief model. INFORMS J. Comput. 30(4):750-767.Link, Google Scholar · Zbl 1519.92166
[36] Liu YF , Ma S , Dai YH , Zhang S (2016) A smoothing SQP framework for a class of composite L q minimization over polyhedron. Math. Programming 158(1):467-500.Crossref, Google Scholar · Zbl 1346.90684 · doi:10.1007/s10107-015-0939-5
[37] Lu Z , Chen X (2017) Generalized conjugate gradient methods for ℓ 1 regularized convex quadratic programming with finite convergence. Math. Oper. Res. 43(1):275-303.Link, Google Scholar · Zbl 1432.90101
[38] Mangasarian O , Fromovitz S (1967) The Fritz John necessary optimality conditions in the presence of equality and inequality constraints. J. Math. Anal. Appl. 17(1):37-47.Crossref, Google Scholar · Zbl 0149.16701 · doi:10.1016/0022-247X(67)90163-1
[39] Natarajan BK (1995) Sparse approximate solutions to linear systems. SIAM J. Comput. 24(2):227-234.Crossref, Google Scholar · Zbl 0827.68054 · doi:10.1137/S0097539792240406
[40] Thi HL , Dinh TP , Le HM , Vo XT (2015) DC approximation approaches for sparse optimization. Eur. J. Oper. Res. 244(1):26-46.Crossref, Google Scholar · Zbl 1346.90819 · doi:10.1016/j.ejor.2014.11.031
[41] van den Berg E , Friedlander MP (2009) Probing the Pareto frontier for basis pursuit solutions. SIAM J. Sci. Comput. 31(2):890-912.Crossref, Google Scholar · Zbl 1193.49033 · doi:10.1137/080714488
[42] van den Berg E , Friedlander MP , Hennenfent G , Herrmann F , Saab R , Yılmaz Ö (2007) Sparco: A testing framework for sparse reconstruction. Technical Report TR-2007-20, Department of Computer Science, University of British Columbia, Vancouver.Google Scholar
[43] Wang Z , Fang S-C , Xing W (2013) On constraint qualifications: Motivation, design and inter-relations. J. Indust. Management Optim. 9(4):983-1001.Google Scholar · Zbl 1281.90059
[44] Wen Z , Yin W , Goldfarb D , Zhang Y (2010) A fast algorithm for sparse reconstruction based on shrinkage, subspace optimization, and continuation. SIAM J. Sci. Comput. 32(4):1832-1857.Crossref, Google Scholar · Zbl 1215.49039 · doi:10.1137/090747695
[45] Xu Z , Chang X , Xu F , Zhang H (2012) L 1/2 regularization: A thresholding representation theory and a fast solver. IEEE Trans. Neural Networks Learn. Systems 23(7):1013-1027.Crossref, Google Scholar · doi:10.1109/TNNLS.2012.2197412
[46] Yin P , Lou Y , He Q , Xin J (2015) Minimization of ℓ 1 − 2 for compressed sensing. SIAM J. Sci. Comput. 37(1):A536-A563.Crossref, Google Scholar · Zbl 1316.90037 · doi:10.1137/140952363
[47] Zhang L , Hu Y , Yu CKW , Wang J (2018) Iterative positive thresholding algorithm for non-negative sparse optimization. Optimization 67(9):1345-1363.Crossref, Google Scholar · Zbl 1412.90163 · doi:10.1080/02331934.2018.1470629
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.