English

运筹学学报 >

2022 , Vol. 26 >Issue 1: 43 - 59

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2022.01.003

 

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

展开
  • 1. 福州大学数学与统计学院, 福建福州 350116
    2. 福州大学离散数学与理论计算机科学研究中心, 福建福州 350116
朱文兴  E-mail: wxzhu@fzu.edu.cn

收稿日期: 2021-04-25

  网络出版日期: 2022-03-14

基金资助

国家自然科学基金(62174033)

收起

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

Expand
  • 1. School of Mathematics and Statistics, Fuzhou University, Fuzhou 350116, Fujian, China
    2. Center for Discrete Mathematics and Theoretical Computer Science, FuzhouUniversity, Fuzhou 350116, Fujian, China

Received date: 2021-04-25

  Online published: 2022-03-14

Fold

摘要

加权l1最小化是稀疏优化的主流方法之一。本文对带非负约束的l0最小化问题与加权l1最小化问题的解之间的关系进行了研究，给出了加权l1最小化问题的约束矩阵和目标函数的系数是"s-权优"的定义，并通过该定义给出了加权l1最小化问题的解是带非负约束的l0最小化问题的解的条件。进一步，本文给出了"s-权优"的充分条件及其具体表示形式，并对其上下界进行了可计算的有效估计。

关键词： 线性规划; 非负稀疏解; 误差分析; 等价性条件

本文引用格式

吕亚星, 韩美佳, 黄子麟, 朱文兴 . 非负约束稀疏优化问题的一个等价性条件[J]. 运筹学学报, 2022 , 26(1) : 43 -59 . DOI: 10.15960/j.cnki.issn.1007-6093.2022.01.003

Abstract

Weighted l1 minimization is one of the mainstream methods for sparse optimization. Since the l0 minimization problem is NP-hard, this paper studies the relationship between solutions of the l0 minimization problem and the weighted l1 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 l1 minimization problem to be a solution of the l0 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 l1 minimization problem.

Key words： linear programming; nonnegative sparse solution; error analysis; equivalence condition

参考文献

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.
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.
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.
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.
10 Bradley P S , Mangasarian O L , Rosen J B . Parsimonious least norm approximation[J]. Computational Optimization and Applications, 1998, 11 (1): 5- 21.
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 l1 minimization[J]. Journal of Fourier Analysis and Applications, 2008, 14 (5): 877- 905.
15 Zhao Y B , Li D . Reweighted l1-minimization for sparse solutions to underdetermined linear systems[J]. SIAM Journal on Optimization, 2012, 22 (3): 1065- 1088.
16 Zhao Y B . Equivalence and strong equivalence between sparsest and least l1-norm nonnegative solutions of linear systems and their application[J]. Journal of the Operations Research Society of China, 2014, 2 (2): 171- 194.
17 Gao Y , Peng J G , Yue S G , et al. On the null space property of lq-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 l1 minimization[J]. Mathematical Programming, 2011, 127 (1): 57- 88.
Options
文章导航

/

〈 〉