压缩感知问题的目标罚函数交替随机搜索方法

计算机科学 ›› 2019, Vol. 46 ›› Issue (6A): 133-137.

压缩感知问题的目标罚函数交替随机搜索方法

蒋敏¹, 孟志青¹, 沈瑞²

浙江工业大学管理学院杭州310023¹;
浙江工业大学经济学院杭州310023²

出版日期:2019-06-14 发布日期:2019-07-02
通讯作者: 孟志青(1962-),男,教授,博士生导师,主要研究方向为供应链管理、非线性优化理论、机器学习、数据挖掘,E-mail:mengzhiqing@zjut.edu.cn
作者简介:蒋敏(1976-),女,教授,博士生导师,主要研究方向为供应链管理、非线性优化理论、机器学习、数据挖掘;沈瑞(1969-),女,博士,讲师,主要研究方向为供应链管理、非线性优化理论、机器学习、数据挖掘。
基金资助:
本文受浙江省自然科学基金项目(LY18A010031),国家自然科学基金项目(11871434)资助。

Alternate Random Search Algorithm of Objective Penalty Function for Compressed Sensing Problem

JIANG Min¹, MENG Zhi-qing¹, SHEN Rui²

School of Management,Zhejiang University of Technology,Hangzhou 310023,China¹;
School of Economics,Zhejiang University of Technology,Hangzhou 310023,China²

Online:2019-06-14 Published:2019-07-02

摘要/Abstract

摘要： 首先将压缩感知优化问题等价定义为双凸优化问题,证明了这个等价双凸优化问题的最优解也是压缩感知优化问题的最优解,然后定义了它的一个具有2阶以上的光滑性的目标罚函数及对应的交替子问题,给出了一个交替求解子问题迭代算法,理论上证明了所提出的交替算法的收敛性定理,导出了压缩感知的最优解显示表达式,设计了一种对一类特定的压缩感知问题有效的交替随机搜索算法。该方法为研究和解决实际的压缩感知问题提供了一种新的设计思路。

关键词: 等价表示, 交替随机搜索算法, 目标罚函数, 稀疏优化, 压缩感知

Abstract: The compressed sensing optimization problem was defined as a biconvex optimization problem.It is proved that the optimal solution of the equivalent biconvex optimization problem is also the optimal solution of the compressed sensing optimization problem.Then a smooth objective penalty function and its corresponding alternating sub-problem were defined.An iterative algorithm for solving the sub-problem was given.The convergence theorem of alternating algorithm was proved theoretically.The expression of the optimal solution for compression perception was derived.An alternating random search algorithm was designed,which is effective for a specific type of compressed sensing problem.This method provides a new design idea for studying and solving the actual compressed sensing problem.

Key words: Alternating random search algorithm, Compressive sensing, Equivalent representation, Object penalty function, Sparse optimization

中图分类号:

TP391.4

蒋敏, 孟志青, 沈瑞. 压缩感知问题的目标罚函数交替随机搜索方法[J]. 计算机科学, 2019, 46(6A): 133-137. https://doi.org/

JIANG Min, MENG Zhi-qing, SHEN Rui. Alternate Random Search Algorithm of Objective Penalty Function for Compressed Sensing Problem[J]. Computer Science, 2019, 46(6A): 133-137. https://doi.org/

参考文献

[1]CANDÈS E,TAO T.Near optimal signal recovery from random projections:Universal encoding strategies [J].IEEE Trans. Info.Theory,2006,52(12):5406-5425.
[2]CANDÈS E J,WAKIN M B,BOYD S P.Enhancing Sparsity by Reweighted l1 Minimization[J].J. Fourier Anal. Appl.,2008,14:877-905.
[3]CHARTRAND R,YIN W.Iteratively reweighted algorithms for compressive sensing[C]∥Proc.IEEE Int.Conf.Acoust,Speech,Signal Process.2008:3869-3872.
[4]MOHIMANI H,BABIE-ZADEH M,JUTTEN C.A fast ap-proach for overcomplete sparse decomposition based on smoothed l₀-norm[J].IEEE Trans.Signal Process.,2009,57(1):289-301.
[5]FOUCART S,RAUHUT H.A Mathematical Introduction to Compressive Sensing[M].Springer,New York,2013.
[6]PANT J K,LU W S,ANTONIOU A.New Improved Algo-rithms for Compressive Sensing Based on l_p Norm[J].IEEE Transactions on Circuits and Systems－II:Express Briefs,2014,61(3):198-202.
[7]WANG Y,WANG J J,XU Z B.Restricted p-isometry properties of nonconvex block-sparse compressed sensing[J].Signal Processing,2014,104:188-196.
[8]ZHU Y,WU J,YU G H.A fast proximal point algorithm for l₁-minimization problem mincompressed sensing[J].Applied Mathematics and Computation,2015,270:777-784.
[9]文婷婷,马兆楠,裴炳,基于拟牛顿法的压缩感知重构零范数平滑算法[J].计算机应用,2015,35(S2):17-19,23.
[10]杜卓明,李洪安,康宝生,等.二阶收敛的光滑正则化压缩感知信号重构方法[J].中国图象图形学报,2016,21(4):490-498.
[11]MENG Z Q,DANG C Y,JIANG M,et al.Exactness and algorithm of an objective penalty function.Journal Globel Optimization,2013,56:691-711.
[12]GORSKI J,PFEUFFER F,KLAMROTH K.Biconvex sets and optimization with biconvex functions:a survey and extensions[J].Math. Meth. Oper. Res.,2007,66:373-407.
[13]孟志青,徐蕾艳,蒋敏,等.压缩感知优化问题的等价表示及其目标罚函数方法[J].计算机科学,2017,44(S1):97-99.

相关文章 15

[1]	刘玉红,刘树英,付福祥. 基于卷积神经网络的压缩感知重构算法优化 Optimization of Compressed Sensing Reconstruction Algorithms Based on Convolutional Neural Network 计算机科学, 2020, 47(3): 143-148. https://doi.org/10.11896/jsjkx.190100199
[2]	田伟, 刘浩, 陈根龙, 宫晓蕙. 面向分块压缩感知的交叉子集导引自适应观测 Cross Subset-guided Adaptive Measurement for Block Compressive Sensing 计算机科学, 2020, 47(12): 190-196. https://doi.org/10.11896/jsjkx.200800197
[3]	吴学林, 朱荣, 郭迎. 基于块稀疏贝叶斯模型的鬼成像重构算法 Ghost Imaging Reconstruction Algorithm Based on Block Sparse Bayesian Model 计算机科学, 2020, 47(11A): 188-191. https://doi.org/10.11896/jsjkx.200200058
[4]	许锋, 孙洁, 刘世杰. 基于遗传算法的声场重构测量优化方法 Sampling Optimization Method for Acoustic Field Reconstruction Based on Genetic Algorithm 计算机科学, 2020, 47(11): 304-309. https://doi.org/10.11896/jsjkx.200600167
[5]	侯明星,亓慧,黄斌科. 基于分布式压缩感知的无线传感器网络异常数据处理 Data Abnormality Processing in Wireless Sensor Networks Based on Distributed Compressed Sensing 计算机科学, 2020, 47(1): 276-280. https://doi.org/10.11896/jsjkx.180901667
[6]	宋晓祥, 郭艳, 李宁, 王萌. 基于压缩感知的时间序列缺失数据预测算法 Missing Data Prediction Based on Compressive Sensing in Time Series 计算机科学, 2019, 46(6): 35-40. https://doi.org/10.11896/j.issn.1002-137X.2019.06.004
[7]	李秀琴, 王天荆, 白光伟, 沈航. 基于压缩感知的两阶段多目标定位算法 Two-phase Multi-target Localization Algorithm Based on Compressed Sensing 计算机科学, 2019, 46(5): 50-56. https://doi.org/10.11896/j.issn.1002-137X.2019.05.007
[8]	吴健, 孙保明. 无线传感器网络中基于字典优化的压缩感知定位方法 Dictionary Refinement-based Localization Method Using Compressive Sensing inWireless Sensor Networks 计算机科学, 2019, 46(4): 118-122. https://doi.org/10.11896/j.issn.1002-137X.2019.04.019
[9]	王鹏飞, 张杭. 欠定条件下基于主成分的亚采样信号重构 Sub-sampling Signal Reconstruction Based on Principal Component Under Underdetermined Conditions 计算机科学, 2019, 46(10): 103-108. https://doi.org/10.11896/jsjkx.190700195
[10]	杜秀丽, 胡兴, 陈波, 邱少明. 基于加权非局部相似性的视频压缩感知多假设重构算法 Multi-hypothesis Reconstruction Algorithm of DCVS Based on Weighted Non-local Similarity 计算机科学, 2019, 46(1): 291-296. https://doi.org/10.11896／j.issn.1002-137X.2019.01.045
[11]	衡阳, 陈峰, 徐剑峰, 汤敏. 基于压缩感知的心脏磁共振快速成像的应用现状与发展趋势 Application Status and Development Trends of Cardiac Magnetic Resonance Fast Imaging Based on Compressed Sensing Theory 计算机科学, 2019, 46(1): 36-44. https://doi.org/10.11896／j.issn.1002-137X.2019.01.006
[12]	杨思星, 郭艳, 李宁, 孙保明, 钱鹏. 基于数据融合的压缩感知多目标定位算法 Compressive Sensing Multi-target Localization Algorithm Based on Data Fusion 计算机科学, 2018, 45(9): 161-165. https://doi.org/10.11896／j.issn.1002-137X.2018.09.026
[13]	杜秀丽, 张薇, 顾斌斌, 陈波, 邱少明. 基于灰度共生矩阵的图像自适应分块压缩感知方法 GLCM-based Adaptive Block Compressed Sensing Method for Image 计算机科学, 2018, 45(8): 277-282. https://doi.org/10.11896/j.issn.1002-137X.2018.08.050
[14]	郭艳,杨思星,李宁,孙保明,钱鹏. 非基于测距的压缩感知多测量向量目标定位 Range-free Localization Based on Compressive Sensing Using Multiple Measurement Vectors 计算机科学, 2018, 45(7): 99-103. https://doi.org/10.11896／j.issn.1002-137X.2018.07.016
[15]	王福驰,赵志刚,刘馨月,吕慧显,王国栋,解昊. 一种改进的稀疏度自适应匹配追踪算法 Improved Sparsity Adaptive Matching Pursuit Algorithm 计算机科学, 2018, 45(6A): 234-238.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed