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

doi:10.3969/j.issn.1006-2475.2019.06.013

Abstract

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

CLC Number:

TN911.72

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.

References

［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]	ZHANG Lian-na, ZHANG Hui-ping, LI Rong-peng, SONG Xue-li. Sparse Signal Reconstruction of Backtracking Generalized Orthogonal Matching Pursuit Algorithm Based on Secondary Screening [J]. Computer and Modernization, 2022, 0(03): 111-115.
[2]	CHEN Xun-hao, YANG Ying, HUANG Jun-ru, SUN Yu-bao. Video Snapshot Compressed Sensing Reconstruction Based on Multi-scale Fusion Network [J]. Computer and Modernization, 2021, 0(12): 58-64.
[3]	JIN An-an, DING Shuang-shuang, XIONG Qing-zhi, XU Ting-ting, XI Shu-ping, MA Ji-zhong. Optimization Reconstruction of EPMA Image Based on SWOMP Algorithm [J]. Computer and Modernization, 2020, 0(12): 104-111.
[4]	ZHANG Lei, CUI Juan-juan, LI Jing-jing. A Clustering Data Collection Algorithm in WSN Based on Compressed Sensing [J]. Computer and Modernization, 2020, 0(09): 1-5.
[5]	YU Hong-xing1,2, SHEN Guo-wei1,2, GUO Chun1,2. Network Tunnel Detection Method Based on [J]. Computer and Modernization, 2019, 0(06): 1-.
[6]	WU Jia1, ZHAO Yun2, ZHANG Li-juan3, SONG Wen2. Prediction of Cellular Traffic Based on Space-time Compression Sensing [J]. Computer and Modernization, 2018, 0(12): 11-.
[7]	DONG Yuan-quan1, WANG Hao2. Multiple Target Localizationin WSNs via CS Reconstruction Method Based on Discrete CSO Algorithm [J]. Computer and Modernization, 2017, 0(12): 23-27.
[8]	SHEN Huijun. Efficient Compressed Sensing Magnetic Resonance Imaging #br# Based on Compound Regularization [J]. Computer and Modernization, 2016, 0(5): 39-45.
[9]	ZHONG Zhi-wei. Low-dose CT Image Reconstruction Based on Adaptive Kernel Regression Method and Algebraic Reconstruction Technique [J]. Computer and Modernization, 2016, 0(11): 38-42.
[10]	LIU Ji-cheng1, WANG Min-ying1, LI Hao-ran2. Image Reconstruction Based on Improved CoSaMP Algorithm [J]. Computer and Modernization, 2015, 0(5): 48-52.
[11]	LIU Hong-jiang;LI Wen-ying. Research on Technology of Quantum Tomography Based on Compressed Sensing [J]. Computer and Modernization, 2011, 12(12): 121-125.