干扰恢复问题中惩罚优化方法相变现象分析

doi:10.3969/j.issn.1006-2475.2019.06.013

计算机与现代化

干扰恢复问题中惩罚优化方法相变现象分析

(1.中国科学院电子学研究所,北京100190;2.中国科学院大学,北京100049)

收稿日期:2019-01-04 出版日期:2019-06-14 发布日期:2019-06-14
作者简介:张欢(1991-),男，河北石家庄人,博士研究生,研究方向:信号恢复,优化算法及其理论分析,E-mail: zhanghuan13@mails.ucas.ac.cn; 雷宏(1963-),男,研究员,博士生导师,研究方向:电磁场与微波技术,信号处理。

Analysis of Phase Transition of Penalized Optimization Method in Corrupted Sensing Problem

(1. Institute of Electronics, Chinese Academy of Sciences, Beijing 100190, China;
2. University of Chinese Academy of Sciences, Beijing 100049, China)

Received:2019-01-04 Online:2019-06-14 Published:2019-06-14

摘要/Abstract

摘要： 惩罚优化方法广泛应用于存在干扰时的信号恢复问题，并且具有明显的相变现象。为了分析这一现象，需要研究2个问题：该算法何时成功以及何时失败。文献［1］针对前者进行了研究，因此，本文对后者进行研究，即何时惩罚优化方法失败。在分析中，提出一个简单的几何条件，如果观测矩阵的各个元素具有独立的标准高斯分布，则可以使用高斯过程理论来研究这一几何条件，最终获得测量个数的一个阈值。当观测个数小于该阈值时，惩罚优化问题以高概率失败。此外，为了验证这一理论结果，给出该阈值的一个可计算上界,仿真结果表明上述理论结果的阈值是十分紧的。

关键词: 干扰恢复, 惩罚优化问题, 相变, 高斯宽度, 压缩感知, 稀疏信号恢复

Abstract: Penalized optimization method is widely used in the corrupted sensing problems with interference and has sharp phase transition. To analyze this phenomenon, we need to study two problems: when they succeed and when they fail. The former has been studied in the literature［1］, therefore, this paper study the latter, i.e., the failure case. In our analysis, we present a simple geometry condition, if each element of the sensing matrix has independent normal entries, the geometry condition can be studied using Gaussian process theory, and finally we obtain the threshold for the measurement number below which penalized problems fail with high probability. Moreover, in order to verify this theoretical result, a computable upper bound of the threshold value is given, and the simulation results show that the threshold of the above theoretical results is very sharp.

Key words: corrupted sensing, penalized optimization problems, phase transition, Gaussian width, compressed sensing, sparse signal recovery

中图分类号:

TN911.72

张欢1,2,雷宏1. 干扰恢复问题中惩罚优化方法相变现象分析[J]. 计算机与现代化, doi: 10.3969/j.issn.1006-2475.2019.06.013.

ZHANG Huan1,2, LEI Hong1. Analysis of Phase Transition of Penalized Optimization Method in Corrupted Sensing Problem[J]. Computer and Modernization, doi: 10.3969/j.issn.1006-2475.2019.06.013.

参考文献

［1］ FOYGEL R, MACKEY L. Corrupted sensing: Novel guarantees for separating structured signals［J］. IEEE Transactions on Information Theory, 2014,60(2):1223-1247.
［2］ WRIGHT J, YANG A Y, GANESH A, et al. Robust face recognition via sparse representation［J］. IEEE Transactions on Pattern Recognition and Machine Intelligence, 2009,31(2):210-227.
［3］ ELHAMIFAR E, VIDAL R. Sparse subspace clustering［C］// Proceedings of 2009 IEEE Conference on Computer Vision and Pattern Recognition. 2009:2790-2797.
［4］ HAUPT J, BAJWA W U, RABBAT M, et al. Compressed sensing for networked data［J］. IEEE Signal Processing Magazine, 2008,25(2):92-101.
［5］薛以梅. 基于稀疏表示和梯度先验的图像盲去模糊［J］. 计算机与现代化, 2017(12):39-42.
［6］ MCCOY M B, TROPP J A. The Achievable Performance of Convex Demixing［DB/OL］. (2013-09-28)［2019-01-14］. https://arxiv.org/pdf/1309.7478.pdf.
［7］ MCCOY M B, TROPP J A. Sharp recovery bounds for convex demixing, with applications［J］. Foundations of Computation Mathematics, 2014,14(3):503-567.
［8］ AMELUNXEN D, LOTZ M, MCCOY M B, et al. Living on the edge: Phase transitions in convex programs with random data［J］. Information and Inference: A Journal of the IMA, 2014,3(3):224-294.
［9］ OYMAK S, TROPP J A. Universality laws for randomized dimension reduction, with applications［J］. Information and Inference: A Journal of the IMA, 2018,7(3):337-446.
［10］LI X D. Compressed sensing and matrix completion with constant proportion of corruptions［J］. Constructive Approximation, 2013,37(1):73-99.
［11］WRIGHT J, MA Y. Dense error correction via 1-minimization［J］. IEEE Transactions on Information Theory, 2010,56(7):3540-3560.
［12］NGUYEN N H, TRAN T D. Exact recoverability from dense corrupted observations via 1-minimization［J］. IEEE Transactions on Information Theory, 2013,59(4):2017-2035.
［13］NGUYEN N H, TRAN T D. Robust lasso with missing and grossly corrupted observations［J］. IEEE Transactions on Information Theory, 2013,4(59):2036-2058.
［14］POPE G, BRACHER A, STUDER C. Probabilistic recovery guarantees for sparsely corrupted signals［J］. IEEE Transactions on Information Theory, 2013,59(5):3104-3116.
［15］STUDER C, KUPPINGER P, POPE G, et al. Recovery of sparsely corrupted signals［J］. IEEE Transactions on Information Theory, 2012,58(5):3115-3130.
［16］STUDER C, BARANIUK R G. Stable restoration and separation of approximately sparse signals［J］. Applied and Computational Harmonic Analysis, 2014,37(1):12-35.
［17］ZHANG H, LIU Y L, LEI H. On the phase transition of corrupted sensing［C］// Proceedings of 2017 IEEE International Symposium on Information Theory. 2017:521-525.
［18］CHEN J C, LIU Y L. Corrupted sensing with sub-Gaussian measurements［C］// Proceedings of 2017 IEEE International Symposium on Information Theory. 2017:516-520.
［19］ROCKAFELLAR R T. Convex Analysis［M］. Princeton University Press, 1970.
［20］GORDON Y. Some inequalities for Gaussian processes and applications［J］. Israel Journal of Mathematics, 1985,50(4):265-289.
［21］BOUCHERON S, LUGOSI G, MASSART P. Concentration Inequalities: A Nonasymptotic Theory of Independence［M］. Oxford University Press, 2013

[1]	杜鑫昌, 高瑜翔, 曹远杰, 张皓, 刘海波. 改进混沌方程及压缩感知理论图像加密算法[J]. 计算机与现代化, 2022, 0(04): 115-120.
[2]	张连娜, 张慧萍, 李荣鹏, 宋学力. 基于二次筛选的回溯广义正交匹配追踪算法的稀疏信号重构[J]. 计算机与现代化, 2022, 0(03): 111-115.
[3]	陈勋豪, 杨莹, 黄俊茹, 孙玉宝. 基于多尺度融合网络的视频快照压缩感知重建[J]. 计算机与现代化, 2021, 0(12): 58-64.
[4]	金安安, 丁双双, 熊卿智, 许婷婷, 习淑萍, 马继忠. 基于SWOMP算法的EPMA影像优化重构[J]. 计算机与现代化, 2020, 0(12): 104-111.
[5]	张蕾, 崔娟娟, 李晶晶. WSN中基于压缩感知的分簇数据收集算法[J]. 计算机与现代化, 2020, 0(09): 1-5.
[6]	余红星1,2,申国伟1,2，郭春1，2. 一种基于自动特征工程与压缩感知的网络隧道检测方法[J]. 计算机与现代化, 2019, 0(06): 1-.
[7]	吴佳1，赵云2，张丽娟3，宋文2. 基于空时压缩感知算法的蜂窝流量预测[J]. 计算机与现代化, 2018, 0(12): 11-.
[8]	董袁泉1，王浩2. 基于离散鸡群压缩感知的WSNs多目标定位[J]. 计算机与现代化, 2017, 0(12): 23-27.
[9]	申慧君. 基于复合正则化的高效压缩感知磁共振成像研究[J]. 计算机与现代化, 2016, 0(5): 39-45.
[10]	刘继承1，王敏莹1，李浩然2. 基于改进CoSaMP算法的图像重建[J]. 计算机与现代化, 2015, 0(5): 48-52.
[11]	陈宝深. 基于压缩感知技术的自适应阵列天线滤波系统的研究[J]. 计算机与现代化, 2013, 1(7): 98-100,.

干扰恢复问题中惩罚优化方法相变现象分析

Analysis of Phase Transition of Penalized Optimization Method in Corrupted Sensing Problem

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 11

编辑推荐

Metrics

本文评价