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

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

运筹学学报 ›› 2022, Vol. 26 ›› Issue (1): 43-59.doi: 10.15960/j.cnki.issn.1007-6093.2022.01.003

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

吕亚星¹, 韩美佳², 黄子麟², 朱文兴^2*^,*()

1. 福州大学数学与统计学院, 福建福州 350116
2. 福州大学离散数学与理论计算机科学研究中心, 福建福州 350116

收稿日期:2021-04-25 出版日期:2022-03-15 发布日期:2022-03-14
通讯作者: 朱文兴 E-mail:wxzhu@fzu.edu.cn
作者简介:朱文兴 E-mail: wxzhu@fzu.edu.cn
基金资助:
国家自然科学基金(62174033)

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

Yaxing LYU¹, Meijia HAN², Zilin HUANG², Wenxing ZHU^2*^,*()

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:2021-04-25 Online:2022-03-15 Published:2022-03-14
Contact: Wenxing ZHU E-mail:wxzhu@fzu.edu.cn

摘要/Abstract

摘要：

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

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

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

中图分类号:

O224

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

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.

参考文献 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]	陈婳, 张国川. 经典一维装箱问题近似算法的研究进展[J]. 运筹学学报, 2022, 26(1): 69-84.
[2]	黄培煌, 朱文兴. 移动传感器网络中的最大价值路径扫描覆盖算法[J]. 运筹学学报, 2019, 23(4): 155-164.
[3]	杨沐明, 黄亚魁, 戴彧虹. 一类多商品设施选址问题的基于线性松弛解的启发式方法[J]. 运筹学学报, 2019, 23(3): 15-26.
[4]	蔡爽, 杨珂, 刘克. 具有机器适用限制的分布式置换流水车间问题的模型与算法[J]. 运筹学学报, 2018, 22(4): 17-30.
[5]	黄亚魁, 李博, 康阳, 戴彧虹, 柳建军. 天然气稳态运行优化的混合整数模型及其算法[J]. 运筹学学报, 2017, 21(2): 13-23.
[6]	连淑君, 杜爱华, 唐加会. 等式约束优化问题的一类新的简单光滑精确罚函数[J]. 运筹学学报, 2017, 21(1): 33-43.
[7]	潘平奇. 关于“线性规划界面算法的高效实现”[J]. 运筹学学报, 2015, 19(3): 78-84.
[8]	戴彧虹，刘新为. 线性与非线性规划算法与理论[J]. 运筹学学报, 2014, 18(1): 69-92.
[9]	连淑君. 不等式约束优化问题的低阶精确罚函数的光滑化算法[J]. 运筹学学报, 2012, 16(2): 51-64.
[10]	尚有林, 刘牧华, 李璞. 一种新的逼近精确罚函数的罚函数及性质[J]. 运筹学学报, 2012, 16(1): 56-66.
[11]	邵嘉婷, 徐大川. 随机容错设施布局问题的近似算法[J]. 运筹学学报, 2012, 16(1): 13-20.
[12]	宋伟, 赵茂先, 王向荣. 求解多层线性规划的模糊规划法[J]. 运筹学学报, 2011, 15(4): 85-92.
[13]	王胜刚, 张莹, 徐应涛. 基于打洞函数法的BP神经网络水文预报方法[J]. 运筹学学报, 2011, 15(4): 45-54.
[14]	汪传旭, 蒋良奎. 基于应急救援物资单向转运的受灾点库存策略研究[J]. 运筹学学报, 2011, 15(4): 93-101.

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

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

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献 20

相关文章 14

编辑推荐

Metrics

本文评价