Advances in Applied Mathematics
Vol.
13
No.
03
(
2024
), Article ID:
83394
,
10
pages
10.12677/aam.2024.133098
压缩感知中的分布鲁棒优化模型及其求解方法
李达臣
辽宁师范大学数学学院,辽宁 大连
收稿日期:2024年2月27日;录用日期:2024年3月21日;发布日期:2024年3月27日
摘要
压缩感知(CS)理论作为当前先采样后压缩方法的替代方法引起了很多的关注,相关学者已经提出很多CS恢复算法如CoSaMP等,而带噪声的压缩感知模型可以表示为l1-范数问题,由于不易判断矩阵的有限等距性(RIP)以及观测矩阵的不确定性,考虑将该l1-范数问题建模为分布鲁棒优化问题,再借助KL-散度、函数变换以及内部最大化期望函数等方法得到分布鲁棒优化问题的等价形式。
关键词
KL-距离散度,分布鲁棒优化,机会约束优化,压缩感知
Distributed Robust Optimization Model and Its Solution Method in Compressed Sensing
Dachen Li
School of Mathematics, Liaoning Normal University, Dalian Liaoning
Received: Feb. 27th, 2024; accepted: Mar. 21st, 2024; published: Mar. 27th, 2024
ABSTRACT
Compressed sensing (CS) theory has attracted a lot of attention as an alternative to the current sampling-then-compression method. Relevant scholars have proposed many CS recovery algorithms such as CoSaMP, etc., and the noisy compressed sensing model can be expressed as an l1-norm problem. Since it is difficult to judge the finite isometric property (RIP) of the matrix and the uncertainty of the observation matrix, consider modeling the l1-norm problem as a distributed robust optimization problem, and then use KL-divergence, function transformation and internal maximization methods such as the expectation function obtain equivalent forms of distributed robust optimization problems.
Keywords:KL-Distance Divergence, Distributed Robust Optimization, Chance-Constrained Optimization, Compressed Sensing
Copyright © 2024 by author(s) and Hans Publishers Inc.
This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).
http://creativecommons.org/licenses/by/4.0/
1. 引言
压缩感知,也被称为压缩采样或者稀疏采样,其主要思想是利用信号中存在的冗余性,同时进行采样和压缩。压缩感知理论从比Nyquist采样理论所建议的要少得多的采集测量中证明,当信号在某些域中表现出稀疏性时,它可以以很高的概率重建。在此领域研究的相关学者、已经提出了许多压缩感知恢复算法,例如:Tropp [1] 等提出的正交匹配追踪算法,主要应用于语音处理、图像压缩、信号处理等领域,具有简单易实现、在稀疏信号重构中表现良好的特点,但对于非稀疏信号可能性能有所下降 [2] ;Wright [3] 等提出的基追踪算法,主要应用于信号处理、图像压缩、医学成像等领域,可以处理非稀疏信号,通过求解凸优化问题,能够得到全局最优解,但计算复杂 [4] ;Candès [5] 等提出的压缩采样匹配追踪算法,主要应用于通信系统、成像、生物医学工程等领域,在高度稀疏信号的情况下表现良好,相对于正交匹配追踪算法有更好的收敛性,但对于非稀疏信号仍存在一些问题 [6] ;Goldstein [7] 等提出的迭代硬阈值算法,主要应用于图像重构、信号处理、通信系统等领域,但收敛速度相对较快,算法简单,但受噪声干扰较大 [8] 。
在压缩感知理论中,通常通过与信号相互独立的随机投影对信号进行采样,并通过最小化l0-范数或者l1-范数优化问题重建,建立该优化问题的前提是信号在某些变换域中是稀疏的 [8] [9] 。一般地,使用 观测矩阵 的m个行向量来投影稀疏系数为s的向量 ,得到观测向量 。压缩感知的一般模型可以写成:
(1.1)
其中,当稀疏系数为s时可令
也就是说,当信号稀疏时,压缩感知模型可转化为如下形式:
(1.2)
考虑带噪声的稀疏系数为s的压缩感知问题,可建模为最小化l0-范数问题:
(1.3)
问题(1.3)是不连续的,是一个NP-hard问题。
Donoho [10] 等证明了在一定条件下l0-范数问题与下述l1-范数问题是等价的,
(1.4)
在实际测量过程中,噪声容易干扰观测信号,造成重建信号的过程中出现偏差,假设观测到的带噪声的测量向量为y,噪声为e。那么观测向量可以表示为 ,由于希望噪声e非常小,而且噪声是客观存在无法忽视的,所以假设e小于或等于一个正数 ,则问题(1.4)可转化为如下带噪声的压缩感知信号重建模型 [10] :
一般地,带噪声的压缩感知模型为如下形式:
(1.5)
其中, 代表噪声, 代表 的观测矩阵, 表示原始信号, 代表观测值。
关于l1-范数问题的求解,近年来有很多学者对其进行研究做出了很多贡献:
1) 聂操男 [11] 首先将l1-范数问题转化为概率约束优化模型,再通过构造特征函数 的一个光滑近似函数
然后建立压缩感知中的概率约束优化问题的的光滑D.C.近似问题( P δ )
(1.6)
并对(1.6)进行了收敛性分析,最后分析并求解压缩感知中的概率约束优化问题的光滑D.C.近似问题。
2) 陈苗给 [12] 出求解含有l1-范数问题的光滑FR共轭梯度法。先将l1-范数问题等价转化为无约束优化问题,
(1.7)
其中 ,
然后对此无约束优化问题进行光滑化处理,利用绝对值函数的光滑逼近函数:
(1.8)
其中, , 。
且(1.8)满足
其中, 。
基于(1.8),得到(1.7)的目标函数的光滑函数
其中
, .
这样就将含有l1-范数问题转化为光滑无约束优化问题,并且在一般条件下给出了FR共轭梯度法的全局收敛结果。
3) 屈彪等 [13] 将l1-范数问题转化为一个分裂可行问题
求 ,使得 , (1.9)
其中 , 。
同时也可以将l1-范数问题转化为一个凸可行问题
求 (1.10)
其中, , 是观测矩阵第j列, 是观测向量b的第j个分量。
在式(1.9)和(1.10)基础上,设计了几种松弛投影算法与经典投影算法简化了投影计算量和步长计算步骤。
2. 压缩感知中的分布鲁棒约束优化模型
对于带噪声的压缩感知模型,由于不易判断矩阵的有限等距性(RIP)以及观测矩阵的不确定性,因此可将l1-范数问题建模为分布鲁棒优化问题:
(2.1)
其中, 是n维的决策向量, 是支撑集 上的具有概率分布P的随机向量,Pr为概率, , 是预先给定的置信水平。 表示任意分布, , 。
考虑特征函数
由概率约束条件 得
从而问题(2.1)可表示成:
(2.2)
3. 内部最大化问题的求解
假设这里已经获得一个额定分布P0,通过考虑P0与未知分布P之间的距离来构造模糊集
(3.1)
其中,D表示所有概率分布的集合,常数 是模糊度指数,它控制模糊度集P的大小, 表示分布P到额定分布P0的距离散度。
假设P相对于P0是绝对连续的(记为 ),也就是说对于每个可测集合A,若 也就意味着 。设分布P和P0在支撑集 上有概率密度函数 和 ,定义
则 称为似然比, ,且 ,显然,对于测量分布P与额定分布P0扰动或偏差问题,似然比是一个很好的工具 [14] 。
考虑KL-距离散度函数:
则从P到P0的KL-距离散度为
显然, ,当且仅当在P0上有 几乎一定成立时,等式成立。
定义一个不确定集为:
使用测度变换方法,得
因此,可以将约束函数转换为期望形式,其中期望是关于额定分布P0的。
考虑问题(2.2)的约束函数
令 ,有
问题(2.2)中的内部最大化问题可以重新表述为
(3.2)
易证,问题(3.2)是一个凸优化问题。
事实上,和 , ,可以得到
此外,令 ,由于 是在 上关于y的凸函数,对于每个 ,有
由此可得
也就是说, 是凸的。
类似地,令 ,由于 是在 上关于y的凸函数,
那么
由此可见
故 关于 也是凸的,因此问题(2.4)也是个凸优化问题。
对于每个 ,记 表示 关于分布P0的矩母生成函数,令
假设1 [15] 对于每个 ,S是一个非空集。
令
问题(3.2)等价于
(3.3)
交换极大极小算子的顺序,得到(3.3)的Lagrangian对偶为
(3.4)
假设问题(3.2)满足slater条件 [16] ,即存在 ,使得
又由于(3.2)是凸问题,所以问题(3.3)和问题(3.4)的强对偶性成立,因此要求解问题(3.2),只需求解问题(3.4)即可。忽略 ,问题(3.4)可以表示为
(3.5)
问题(3.5)是一个凸优化问题,设 是问题(3.5)的最优值函数。
考虑两种情况:1) ;2) 并且 ;
1) 设 是测度P0上 的本质上确界,即
然后构造一个分布序列 集中趋于 ,进而构造 ,使得当 时, 趋于 。因此, 。
2) 定义函数
其中, 关于 是凸的, 关于 是线性的。因此可以计算函数的导数。对于在 任意可行方向 ,
对于任意可行的y和 ,函数 是关于t单调的,因此,通过单调收敛定理 [16] ,可以得到
类似地,可以得到
问题(3.5)的拉格朗日函数如下:
命题3.1 [16] 如果存在 ,使得 , 并且
(3.6)
因此这个问题简化为解决问题(3.6),则 是问题(3.5)的最优解。问题(3.6)是一个本质上没有约束的凸优化问题。因此,它的最优解应该是某种意义上的驻点,即它应该强制 的导数在某种意义上为零。由导数的表达式和导数算子的线性,得到
命题3.2 [15] 假设 满足 ,也就是 (即 是零线性算子)那么 ,并且
证明:由 可得, ,将其带入
得到
该期望函数可变形为
即
得到
,
再将 变形
又由 ,也就是最优解的形式为
命题3.2表明优化问题(3.5)的最优目标值是有限的,还得出最优解的形式为
设 ,可以得到 。
由上述给出的 与 ,满足Bonnans等人提出的命题3.3的条件 [16] ,这表明 可以求解问题(3.5)。将 代入问题(3.5),得到问题(3.5)的最优值函数:
(3.7)
当假设1成立时,对于 ,总存在 ,使得问题(3.7)有限,这说明问题(3.5)的最优值函数是有限的。进一步结合两种情况,得到以下定理
定理1 若假设1成立且不确定集为 ,则问题(3.2)等价于
(3.8)
综上问题(2.1)可以等价转化为
(3.9)
其中, 由式(3.8)定义。
4. 总结及展望
这篇文章的主要内容是将一个l1-范数问题建模为分布鲁棒优化问题,并通过使用KL-散度、函数变换以及内部最大化期望函数等方法,得到了分布鲁棒优化问题的等价形式。
文章可能首先介绍了压缩感知模型的背景,包括l1-范数问题模型,但其由于不易判断矩阵的有限等距性(RIP)以及观测矩阵的不确定性,需要将其建模为分布鲁棒优化问题等。接着,文章阐述建模的过程,包括如何利用KL-散度和函数变换来对l1-范数问题进行转换,并通过内部最大化期望函数等方法得到等价形式。
应用分布鲁棒优化问题模型方法对于解决l1-范数问题,可以进一步转化为凸优化问题,进而应用凸优化问题解决方法,未来可以探索例如转化为CVaR模型,并考虑使用内点法或梯度下降法等算法解决。相信以后在这个领域会有更深入的理解和探索。
在问题适用性方面,该方法建模为分布鲁棒优化问题的适用性可能受到特定问题结构和数据分布的限制;在计算复杂性角度方面,因为在实际应用中,由于使用了KL-散度、函数变换等方法,可能导致算法的计算复杂性较高;在参数敏感性方面且方法中可能存在一些参数,对于这些参数的选择可能对最终结果产生较大影响。
今后研究方向和改进方向的改进,可以研究如何优化算法,降低计算复杂性,使方法更适用于大规模数据和实时应用;可以探索方法中参数的自适应性,减少对目标的参数调整需求,提高方法的易用性;可以加强对方法理论基础的研究,确保方法在不同场景下的有效性,并探索更一般化的问题建模方法。
文章引用
李达臣. 压缩感知中的分布鲁棒优化模型及其求解方法
Distributed Robust Optimization Model and Its Solution Method in Compressed Sensing[J]. 应用数学进展, 2024, 13(03): 1036-1045. https://doi.org/10.12677/aam.2024.133098
参考文献
- 1. Tropp, J.A. and Gilbert, A.C. (2007) Signal Recovery from Random Measurements via Orthogonal Matching Pursuit. IEEE Transactions on Information Theory, 53, 4655-4666. https://doi.org/10.1109/TIT.2007.909108
- 2. Wang, J., Kwon, S. and Shim, B. (2012) Generalized Orthogonal Matching Pursuit. IEEE Transactions on Signal Pro-cessing, 60, 6202-6216. https://doi.org/10.1109/TSP.2012.2218810
- 3. Wright, S.J., Nowak, R.D. and Figueiredo, M.A.T. (2009) Sparse Reconstruction by Separable Approximation. IEEE Transactions on Signal Processing, 57, 2479-2493. https://doi.org/10.1109/TSP.2009.2016892
- 4. Chen, S.S., Donoho, D.L. and Saunders, M.A. (2001) Atomic Decomposition by Basis Pursuit. SIAM Review, 43, 129-159. https://doi.org/10.1137/S003614450037906X
- 5. Candès, E.J., Romberg, J. and Tao, T. (2006) Robust Uncertainty Principles: Exact Signal Reconstruction from Highly Incomplete Frequency Information. IEEE Transactions on Information Theory, 52, 489-509. https://doi.org/10.1109/TIT.2005.862083
- 6. Gui, G., Wan, Q., Peng, W., et al. (2010) Sparse Multipath Channel Estimation Using Compressive Sampling Matching Pursuit Algorithm. arXiv:1005.2270.
- 7. Goldstein, T. and Osher, S. (2009) The Split Bregman Method for L1-Regularized Problems. SIAM Journal on Imaging Sciences, 2, 323-343. https://doi.org/10.1137/080725891
- 8. Zhang, J., Zhao, D., Zhao, C., et al. (2012) Image Compressive Sensing Recovery via Collaborative Sparsity. IEEE Journal on Emerging and Selected Topics in Circuits and Systems, 2, 380-391. https://doi.org/10.1109/JETCAS.2012.2220391
- 9. Zhang, J., Zhao, D., Zhao, C., et al. (2012) Compressed Sensing Recovery via Collaborative Sparsity. 2012 Data Compression Conference, Snowbird, 10-12 April 2012, 287-296. https://doi.org/10.1109/DCC.2012.71
- 10. Donoho, D.L. (2006) Compressed Sensing. IEEE Transactions on Information Theory, 52, 1289-1306. https://doi.org/10.1109/TIT.2006.871582
- 11. 聂操男. 压缩感知中的概率约束优化模型的光滑近似[D]: [硕士学位论文]. 大连: 辽宁师范大学, 2019.
- 12. 陈苗. 一类含有l1范数优化问题的梯度类算法[D]: [硕士学位论文]. 青岛: 青岛大学, 2020.
- 13. 屈彪, 张文伟, 于丽超. 线性方程组l1范数问题的松弛投影算法及其应用[J]. 运筹学学报, 2017, 21(2): 57-65.
- 14. 王榆. 基于修正的χ2-距离散度的不确定概率优化问题[D]: [硕士学位论文]. 大连: 辽宁师范大学, 2016.
- 15. Hu, Z. and Hong, L.J. (2013) Kullback-Leibler Divergence Constrained Distributionally Robust Optimization. Optimization Online, 1, 9.
- 16. Shapiro, A., Dentcheva D. and Ruszczyński, A. (2009) Lectures on Stochastic Programming. Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9780898718751