On the Phase Transition of Corrupted Sensing

被引：0

作者：

Zhang, Huan ^{[1
,2
]}

Liu, Yulong ^{[3
]}

Lei, Hong ^{[1
]}

机构：

[1] Chinese Acad Sci, Inst Elect, Beijing 100190, Peoples R China

[2] Univ Chinese Acad Sci, Beijing 100049, Peoples R China

[3] Beijing Inst Technol, Sch Phys, Beijing 100081, Peoples R China

来源：

2017 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY (ISIT) | 2017年

基金：

中国国家自然科学基金;

关键词：

Corrupted sensing; phase transition; Gaussian width; compressed sensing; signal separation; L(1)-MINIMIZATION; SIGNALS;

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

In [1], a sharp phase transition has been numerically observed when a constrained convex procedure is used to solve the corrupted sensing problem. In this paper, we present a theoretical analysis for this phenomenon. Specifically, we establish the threshold below which this convex procedure fails to recover signal and corruption with high probability. Together with the work in [1], we prove that a sharp phase transition occurs around the sum of the squares of spherical Gaussian widths of two tangent cones. Numerical experiments are provided to demonstrate the correctness and sharpness of our results.

引用

页码：521 / 525

页数：5

共 20 条

[1] Living on the edge: phase transitions in convex programs with random data
Amelunxen, Dennis
Lotz, Martin
McCoy, Michael B.
Tropp, Joel A.
[J]. INFORMATION AND INFERENCE-A JOURNAL OF THE IMA, 2014, 3 (03) : 224 - 294
[2] [Anonymous], 1991, Probability in Banach Spaces
[3] [Anonymous], UNIVERSALITY LAWS RA
[4] [Anonymous], CVX: Matlab Software for Disciplined Con[1]vex Programming
[5] [Anonymous], 2013, Concentration Inequali-ties: A Nonasymptotic Theory of Independence, DOI DOI 10.1093/ACPROF:OSO/9780199535255.001.0001
[6] The Convex Geometry of Linear Inverse Problems
Chandrasekaran, Venkat
Recht, Benjamin
Parrilo, Pablo A.
Willsky, Alan S.
[J]. FOUNDATIONS OF COMPUTATIONAL MATHEMATICS, 2012, 12 (06) : 805 - 849
[7] Chen J., 2017, P IEEE INT IN PRESS
[8] Elhamifar Ehsan, 2009, 2009 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), P2790, DOI 10.1109/CVPRW.2009.5206547
[9] Corrupted Sensing: Novel Guarantees for Separating Structured Signals
Foygel, Rina
Mackey, Lester
[J]. IEEE TRANSACTIONS ON INFORMATION THEORY, 2014, 60 (02) : 1223 - 1259
[10] Graph implementations for nonsmooth convex programs
Stanford University, United States
[J]. Lect. Notes Control Inf. Sci., 2008, (95-110): : 95 - 110

← 1 2 →