非负约束稀疏优化问题的一个等价性条件

doi:10.15960/j.cnki.issn.1007-6093.2022.01.003

Abstract

Abstract:

Weighted l₁ minimization is one of the mainstream methods for sparse optimization. Since the l₀ minimization problem is NP-hard, this paper studies the relationship between solutions of the l₀ minimization problem and the weighted l₁ minimization problem with non-negative constraints, and gives the definition of "s-weighted goodness" for the constraint matrix and the coefficient of the objective function. Through this definition, a sufficient condition is provided for a solution of the weighted l₁ minimization problem to be a solution of the l₀ minimization problem with non-negative constraints. Some results and proofs are provided from the perspective of monotonicity and robust stability. Further, this paper gives a sufficient condition for "s-weighted goodness", and shows lower and upper bounds of the sufficient condition, which are easy to check. Moreover, this paper also conducts an error analysis of the solution of the weighted l₁ minimization problem.

Key words: linear programming, nonnegative sparse solution, error analysis, equivalence condition

CLC Number:

O224

Yaxing LYU, Meijia HAN, Zilin HUANG, Wenxing ZHU. An equivalence condition for sparse optimization problem with non-negative constraints[J]. Operations Research Transactions, 2022, 26(1): 43-59.

References 20

1	Bardsley J M , Nagy J G . Covariance-preconditioned iterative methods for nonnegatively constrained astronomical imaging[J]. SIAM Journal on Matrix Analysis and Applications, 2006, 27 (4): 1184- 1197. doi: 10.1137/040615043
2	Bruckstein A M , Elad M , Zibulevsky M . On the uniqueness of nonnegative sparse solutions to underdetermined systems of equations[J]. IEEE Transactions on Information Theory, 2008, 54 (11): 4813- 4820. doi: 10.1109/TIT.2008.929920
3	Donoho D L, Tanner J. Sparse nonnegative solution of underdetermined linear equations by linear programming[C]//Proceedings of the National Academy of Sciences of the United States of America, 2005: 9446-9451.
4	Donoho D L , Tanner J . Counting the faces of randomly-projected hypercubes and orthants, with applications[J]. Discrete and Computational Geometry, 2010, 43 (3)
5	Khajehnejad M A , Dimakis A G , Xu W Y , et al. Sparse recovery of nonnegative signals with minimal expansion[J]. IEEE Transactions on Signal Processing, 2010, 59 (1): 196- 208.
6	O'Grady P D, Rickard S T. Recovery of non-negative Signals from compressively sampled observations via non-negative quadratic programming[C]//SPARS'09-Signal Processing with Adaptive Sparse Structured Representations, 2009.
7	Vo N, Moran B, Challa S. Nonnegative-least-square classifier for face recognition[C]//Proceedings of the 6th International Symposium on Neural Networks: Advances in Neural Networks, 2009: 449-456.
8	Wang M , Xu W Y , Tang A . A unique nonnegative solution to an underdetermined system: from vectors to matrices[J]. IEEE Transactions on Signal Processing, 2011, 59 (3): 1007- 1016. doi: 10.1109/TSP.2010.2089624
9	Bradley P S , Fayyad U M , Mangasarian O L . Mathematical programming for data mining: formulations and challenges[J]. INFORMS Journal on Computing, 1999, 11 (3): 217- 238. doi: 10.1287/ijoc.11.3.217
10	Bradley P S , Mangasarian O L , Rosen J B . Parsimonious least norm approximation[J]. Computational Optimization and Applications, 1998, 11 (1): 5- 21. doi: 10.1023/A:1018361916442
11	He R, Zheng W S, Hu B, et al. Nonnegative sparse coding for discriminative semi-supervised learning[C]//2011 IEEE Conference on Computer Vision and Pattern Recognition, 2011: 2849-2856.
12	Mangasarian O L . Machine learning via polyhedral concave minimization[J]. Applied Mathematics and Parallel Computing, 1996, 175- 188.
13	Szlam A, Guo Z H, Osher S. A split Bregman method for non-negative sparsity penalized least squares with applications to hyperspectral demixing[C]//IEEE International Conference on Imaging Processing, 2010: 1917-1920.
14	Candès E J , Wakin M B , Boyd S P . Enhancing sparsity by reweighted l₁ minimization[J]. Journal of Fourier Analysis and Applications, 2008, 14 (5): 877- 905.
15	Zhao Y B , Li D . Reweighted l₁-minimization for sparse solutions to underdetermined linear systems[J]. SIAM Journal on Optimization, 2012, 22 (3): 1065- 1088. doi: 10.1137/110847445
16	Zhao Y B . Equivalence and strong equivalence between sparsest and least l₁-norm nonnegative solutions of linear systems and their application[J]. Journal of the Operations Research Society of China, 2014, 2 (2): 171- 194. doi: 10.1007/s40305-014-0043-1
17	Gao Y , Peng J G , Yue S G , et al. On the null space property of l_q-minimization for 0< q ≤ 1 in compressed sensing[J]. Journal of Function Spaces, 2015, 1- 10.
18	Foucart S , Rauhut H . A Mathematical Introduction to Compressive Sensing[M]. New York: Springer Science+Business Media, 2013: 1- 39.
19	Qin L X , Xiu N H , Kong L C , et al. Linear program relaxation of sparse nonnegative recovery in compressive sensing microarrays[J]. Computational and Mathematical Methods in Medicine, 2012, 646045.
20	Juditsky A , Nemirovski A S . On verifiable sufficient conditions for sparse signal recovery via l₁ minimization[J]. Mathematical Programming, 2011, 127 (1): 57- 88. doi: 10.1007/s10107-010-0417-z

[1]	CHEN Hua, ZHANG Guochuan. A survey on approximation algorithms for one dimensional bin packing [J]. Operations Research Transactions, 2022, 26(1): 69-84.
[2]	Yindong SHEN, Zhuang QIAN, Yuanyuan LI. A survey on driver scheduling in public transportation [J]. Operations Research Transactions, 2021, 25(1): 1-16.
[3]	HUANG Peihuang, ZHU Wenxing. Algorithms for Max-Value Path Sweep Coverage in Mobile Sensor Networks [J]. Operations Research Transactions, 2019, 23(4): 155-164.
[4]	YANG Muming, HUANG Yakui, DAI Yuhong. Linear relaxation solution based heuristics for a class of multi-product facility location problems [J]. Operations Research Transactions, 2019, 23(3): 15-26.
[5]	HUANG Yakui, LI Bo, KANG Yang, DAI Yuhong, LIU Jianjun. A mixed integer model and an algorithm for steady-state gas network optimization [J]. Operations Research Transactions, 2017, 21(2): 13-23.
[6]	LIAN Shujun, DU Aihua, TANG Jiahui. A new class of simple smooth exact penalty functions for equality constrained optimization problems [J]. Operations Research Transactions, 2017, 21(1): 33-43.
[7]	SHI Litang, CHEN Wei. A filled-filter function algorithm for solving unconstrained nonlinear optimization [J]. Operations Research Transactions, 2017, 21(1): 55-64.
[8]	PAN Pingqi. On “An efficient implementation of the face algorithm for linear programming” [J]. Operations Research Transactions, 2015, 19(3): 78-84.
[9]	HE Shengxue. Determining optimal routes for transit vehicles in no-notice emergency evacuation [J]. Operations Research Transactions, 2014, 18(3): 47-59.
[10]	DAI Yuhong, LIU Xinwei. Advances in linear and nonlinear programming [J]. Operations Research Transactions, 2014, 18(1): 69-92.
[11]	Shu-jun Lian. On the Smoothing of the Lower Order Exact Penalty Function for Inequality Constrained Optimization [J]. Operations Research Transactions, 2012, 16(2): 51-64.
[12]	ZHOU Kang, CHEN Jin, QIU Jiang, JIE Zhi. Matrix Algorithm for LP Problem Based on Partial Basic Variables [J]. Operations Research Transactions, 2012, 16(2): 121-126.
[13]	Shang-You-Lin, LIU Mu-Hua, LI Pu. A New Penalty Function Based on Non-coercive Penalty Functions [J]. Operations Research Transactions, 2012, 16(1): 56-66.
[14]	SONG Wei, ZHAO Mao-Xian, WANG Xiang-Rong. Fuzzy programming approach for Multilevel linear programming [J]. Operations Research Transactions, 2011, 15(4): 85-92.
[15]	WANG Sheng-Gang, ZHANG Ying, XU Ying-Tao. The BP Neural Network Hydrological Forecasting Algorithm Based on Tunneling Function Method [J]. Operations Research Transactions, 2011, 15(4): 45-54.

An equivalence condition for sparse optimization problem with non-negative constraints

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

References 20

Related Articles 15

Recommended Articles

Metrics

Comments