Nonuniqueness of Solutions of a Class of ℓ0-minimization Problems

doi:10.1007/s40305-020-00336-3

Journal of the Operations Research Society of China ›› 2021, Vol. 9 ›› Issue (4): 893-908.doi: 10.1007/s40305-020-00336-3

Previous Articles Next Articles

Nonuniqueness of Solutions of a Class of ℓ₀-minimization Problems

Jia-Liang Xu

Hua Loo-Keng Center for Mathematical Sciences, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China

Received:2020-03-23 Revised:2020-06-05 Online:2021-12-30 Published:2021-11-25
Contact: Jia-Liang Xu E-mail:xujialiang@lsec.cc.ac.cn

Abstract

Abstract: 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.

Key words: $\ell_{0}$-minimization, Sparsity, Nonuniqueness, Boundedness

CLC Number:

Jia-Liang Xu. Nonuniqueness of Solutions of a Class of ℓ₀-minimization Problems[J]. Journal of the Operations Research Society of China, 2021, 9(4): 893-908.

TrendMD

References

[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)

Nonuniqueness of Solutions of a Class of ℓ₀-minimization Problems

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 6

Recommended Articles

Metrics

Comments

[1]	Yan-Qin Bai\| Kai-Ji Shen. Alternating Direction Method of Multipliers for 1₁-1₂-Regularized Logistic Regression Model [J]. Journal of the Operations Research Society of China, 2016, 4(2): 243-.
[2]	Li-Li Pan · Nai-Hua Xiu1· Sheng-Long Zhou. On Solutions of Sparsity Constrained Optimization [J]. Journal of the Operations Research Society of China, 2015, 3(4): 421-.
[3]	Xue Li· Wen Song. The First-Order Necessary Conditions for Sparsity Constrained Optimization [J]. Journal of the Operations Research Society of China, 2015, 3(4): 521-.
[4]	JinWang · Jian-Feng Cai. Data-Driven Tight Frame for Multi-channel Images and Its Application to Joint Color-Depth Image Reconstruction [J]. Journal of the Operations Research Society of China, 2015, 3(2): 99-.
[5]	Xiao-Ling Sun · Xiao-Jin Zheng · Duan Li. Recent Advances in Mathematical Programming with Semi-continuous Variables and Cardinality Constraint [J]. Journal of the Operations Research Society of China, 2013, 1(1): 55-.
[6]	Qing-Na Li · He Yan · Le-Qin Wu · Robert Wang. Robust PCA for Ground Moving Target Indication in Wide-Area Surveillance Radar System [J]. Journal of the Operations Research Society of China, 2013, 1(1): 135-.