{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T16:55:06Z","timestamp":1787417706665,"version":"build-2736575974"},"reference-count":29,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Sci. Comput."],"published-print":{"date-parts":[[2010,1]]},"abstract":"<jats:p>Recently, variable selection and sparse reconstruction are solved by finding an optimal solution of a minimization model, where the objective function is the sum of a data-fitting term in $\\ell_2$ norm and a regularization term in $\\ell_p$ norm $(0&lt;p&lt;1)$. Since it is a nonconvex model, most algorithms for solving the problem can provide only an approximate local optimal solution, where nonzero entries in the solution cannot be identified theoretically. In this paper, we establish lower bounds for the absolute value of nonzero entries in every local optimal solution of the model, which can be used to indentify zero entries precisely in any numerical solution. Therefore, we have developed a lower bound theorem to classify zero and nonzero entries in every local solution. These lower bounds clearly show the relationship between the sparsity of the solution and the choice of the regularization parameter and norm so that our theorem can be used for selecting desired model parameters and norms. Furthermore, we also develop error bounds for verifying the accuracy of numerical solutions of the $\\ell_2$-$\\ell_p$ minimization model. To demonstrate applications of our theory, we propose a hybrid orthogonal matching pursuit-smoothing gradient (OMP-SG) method for solving the nonconvex, non-Lipschitz continuous $\\ell_2$-$\\ell_p$ minimization problem. Computational results show the effectiveness of the lower bounds for identifying nonzero entries in numerical solutions and the OMP-SG method for finding a high quality numerical solution.<\/jats:p>","DOI":"10.1137\/090761471","type":"journal-article","created":{"date-parts":[[2012,6,15]],"date-time":"2012-06-15T19:18:14Z","timestamp":1339787894000},"page":"2832-2852","source":"Crossref","is-referenced-by-count":232,"title":["Lower Bound Theory of Nonzero Entries in Solutions of $\\ell_2$-$\\ell_p$ Minimization"],"prefix":"10.1137","volume":"32","author":[{"given":"Xiaojun","family":"Chen","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fengmin","family":"Xu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yinyu","family":"Ye","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2010,11,4]]},"reference":[{"key":"R1","unstructured":"C. Blake and C. Merz,\n                      Repository of Machine Learning Databases [DB\/OL]\n                      , Department of Information and Computer Science, University of California, Irvine, CA, 1998, http:\/\/www.ics.uci.edu\/~mlearn\/MLRepository.html."},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1080\/00401706.1995.10484371"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1137\/060657704"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1137\/030601296"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1007\/s00041-008-9045-x"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.862083"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1109\/LSP.2007.898300"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"R. Chartrand,\n                      Nonconvex regularization for shape preservation\n                      , in 2007 IEEE International Conference on Image Processing, San Antonio, TX, 2007, pp. I293\u2013I296.","DOI":"10.1109\/ICIP.2007.4378949"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"R. Chartrand and W. Yin,\n                      Iteratively reweighted algorithms for compressive sensing\n                      , in 2008 IEEE International Conference on Acoustics, Speech, and Signal Processing, Las Vegas, NV, 2008, pp. 3869\u20133872.","DOI":"10.1109\/ICASSP.2008.4518498"},{"key":"R10","first-page":"129","volume":"43","author":"Chen S. S.","year":"2001","journal-title":"SIAM J. Sci. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/1064-8275","issn-type":"print"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1137\/S0363012997315907"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1137\/080740167"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"F. H. Clarke,\n                      Optimization and Nonsmooth Analysis\n                      , Classics Appl. Math. 5, SIAM, Philadelphia, 1990.","DOI":"10.1137\/1.9781611971309"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1007\/BF02678430"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.871582"},{"key":"R16","first-page":"407","volume":"23","author":"Efron B.","year":"2004","journal-title":"Ann. Statist.","ISSN":"https:\/\/id.crossref.org\/issn\/0090-5364","issn-type":"print"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1198\/016214501753382273"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"T. Hastie, R. Tibshirani, and J. Friedman,\n                      The elements of statistical learning: Data mining\n                      , in Inference and Prediction, Springer-Verlag, New York, 2001.","DOI":"10.1007\/978-0-387-21606-5"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1080\/00401706.1970.10488634"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1137\/050639673"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1109\/78.258082"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1137\/040619582"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1137\/070692285"},{"key":"R24","doi-asserted-by":"crossref","unstructured":"Y. C. Pati, R. Rezaiifar, and P. S. Krishnaprasad,\n                      Orthogonal matching pursuit: Recursive function approximation with applications to wavelet decomposition\n                      , in Proceedings of the 27th Asilomar Conference on Signals, Systems and Computers, Pacific Grove, CA, IEEE, 1993, pp. 40\u201344.","DOI":"10.1109\/ACSSC.1993.342465"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1111\/j.2517-6161.1996.tb02080.x"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2007.909108"},{"key":"R27","doi-asserted-by":"crossref","unstructured":"J. A. Tropp, A. C. Gilbert, S. Muthukrishnan, and M. J. Strauss,\n                      Improved sparse approximation over quasi-incoherent dictionaries\n                      , in 2003 International Conference on Image Processing, Barcelona, Spain, 2003, pp. 37\u201340.","DOI":"10.1109\/ICIP.2003.1246892"},{"key":"R28","first-page":"1","volume":"52","author":"Xu Z.","year":"2009","journal-title":"Sci. China Ser. F"},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1137\/070702187"}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/090761471","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T16:44:23Z","timestamp":1787330663000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/090761471"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,1]]},"references-count":29,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2010,1]]}},"alternative-id":["10.1137\/090761471"],"URL":"https:\/\/doi.org\/10.1137\/090761471","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,1]]}}}