Recently, finding the sparsest solution of an underdetermined linear system has become an important request in many areas such as compressed sensing, image processing, statistical learning, and data sparse approximation. In this paper, we study some theoretical properties of the solutions to a general class of $\ell_{0}$-minimization problems, which can be used to deal with many practical applications. We establish some necessary conditions for a point being the sparsest solution to this class of problems, and we also characterize the conditions for the multiplicity of the sparsest solutions to the problem. Finally, we discuss certain conditions for the boundedness of the solution set of this class of problems.
Jia-Liang Xu
. Nonuniqueness of Solutions of a Class of ℓ0-minimization Problems[J]. Journal of the Operations Research Society of China, 2021
, 9(4)
: 893
-908
.
DOI: 10.1007/s40305-020-00336-3
[1] Candès, E.:Compressive sampling. Proc. Int. Congr. Math. 3, 1433-1452(2006)
[2] Candès, E., Romberg, J., Tao, T.:Stable signal recovery from incomplete and inaccurate measurements. Commun. Pure Appl. Math. 59, 1207-1223(2006)
[3] Candès, E., Tao, T.:Decoding by linear programming. IEEE Trans. Inform. Theory 51, 4203-4215(2005)
[4] Cohen, A., Dahmen, W., DeVore, R.:Compressed sensing and best k-term approximation. J. Am. Math. Soc. 22, 211-231(2009)
[5] Davenport, M.A., Duarte, M.F., Eldar, Y.C., Kutyniok, G.:Compressed Sensing:Theory and Applications. Cambridge University Press, New York (2012)
[6] Donoho, D.:Compressed sensing. IEEE Trans. Inform. Theory 52, 1289-1306(2006)
[7] Donoho, D., Elad, M.:Optimality sparse representation in general (non-orthogonal) dictionaries via 1 minimization. Proc. Natl. Acad. Sci. 100, 2197-2202(2003)
[8] Donoho, D., Huo, X.:Uncertainty principles and ideal atomic decomposition. IEEE Trans. Inform. Theory 47, 2845-2862(2001)
[9] Foucart, S., Rauhut, H.:A Mathematical Introduction to Compressive Sensing. Springer, New York (2013)
[10] Gupta, A., Nowak, R., Recht, B.:Sample complexity for 1-bit compressed sensing and sparse classification. In:IEEE International Symposium on Information Theory, pp. 1553-1557(2010)
[11] Hoefling, H.:A path algorithm for the fused lasso signal approximator. J. Comput. Graph. Stat. 19, 984-1006(2010)
[12] Laska, J., Wen, Z., Yin, W., Baraniuk, R.:Trust, but verify:fast and accurate signal recovery from 1-bit compressive measurements. IEEE Trans. Signal Process. 59, 5289-5301(2011)
[13] Rinaldo, A.:Properties and refinements of the fused lasso. Ann. Stat. 37, 2922-2952(2009)
[14] Tibshirani, R., Wang, P.:Spatial smoothing and hot spot detection for CGH data using the fused lasso. Biostatistics 9, 18-29(2007)
[15] Tibshirani, R., Wainwright, M., Hastie, T.:Statistical Learning with Sparsity:the Lasso and Generalizations. Chapman and Hall/CRC, Boca Raton (2015)
[16] Tropp, J.:Greed is good:algorithmic results for sparse approximation. IEEE Trans. Inf. Theory 50, 2231-2242(2004)
[17] Xu, J.L., Zhao, Y.B.:Stability analysis of a class of sparse optimization problems. Optim. Methods Softw. 35, 836-854(2020)
[18] Zhao, Y.B.:Sparse Optimization Theory and Methods. CRC Press, Boca Raton (2018)
[19] Zhao, Y.B.:New and improved conditions for uniqueness of sparsest solutions of underdetermined linear systems. Appl. Math. Comput. 224, 58-73(2013)
[20] Zhao, Y.B.:RSP-based analysis for sparsest and least 1-norm solutions to underdetermined linear systems. IEEE Trans. Signal Process. 61, 5777-5788(2013)
[21] Zhao, Y.B.:Equivalence and strong equivalence between the sparsest and least 1-norm nonnegative solutions of linear systems and their applications. J. Oper. Res. Soc. China 2, 171-193(2014)
[22] Zhao, Y.B., Xu, C.:1-Bit compressive sensing:reformulation and RRSP-based sign recovery theory. Sci. China Math. 59, 2049-2074(2016)
