A geometrical stability condition for compressed sensing

详细信息    查看全文

• 作者：Axel Flinth ^{flinth@math.tu-berlin.de" class="auth_mail" title="E-mail the corresponding author}
• 关键词：primary ; 52A20 ; 90C25 ; secondary ; 94A12
• 刊名：Linear Algebra and its Applications
• 出版年：2016
• 出版时间：1 September 2016
• 年：2016
• 卷：504
• 期：Complete
• 页码：406-432
• 全文大小：603 K

文摘

During the last decade, the paradigm of compressed sensing has gained significant importance in the signal processing community. While the original idea was to utilize sparsity assumptions to design powerful recovery algorithms of vectors class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0024379516301161&_mathId=si1.gif&_user=111111111&_pii=S0024379516301161&_rdoc=1&_issn=00243795&md5=106b9ca07fa4fddf610b99037a21a10d" title="Click to view the MathML source">x∈R^dclass="mathContainer hidden">class="mathCode">$x\in {\mathbb{R}}^d$, the concept has been extended to cover many other types of problems. A noteable example is low-rank matrix recovery. Many methods used for recovery rely on solving convex programs.

A particularly nice trait of compressed sensing is its geometrical intuition. In recent papers, a classical optimality condition has been used together with tools from convex geometry and probability theory to prove beautiful results concerning the recovery of signals from Gaussian measurements. In this paper, we aim to formulate a geometrical condition for stability and robustness, i.e. for the recovery of approximately structured signals from noisy measurements.

We will investigate the connection between the new condition with the notion of restricted singular values  , classical stability and robustness conditions in compressed sensing, and also to important geometrical concepts from complexity theory. We will also prove the maybe somewhat surprising fact that for many convex programs, exact recovery of a signal class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0024379516301161&_mathId=si2.gif&_user=111111111&_pii=S0024379516301161&_rdoc=1&_issn=00243795&md5=82e43e733bdc8de4e2bd17054a886b09" title="Click to view the MathML source">x₀class="mathContainer hidden">class="mathCode">$x_0$ immediately implies some stability and robustness when recovering signals close to class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0024379516301161&_mathId=si2.gif&_user=111111111&_pii=S0024379516301161&_rdoc=1&_issn=00243795&md5=82e43e733bdc8de4e2bd17054a886b09" title="Click to view the MathML source">x₀class="mathContainer hidden">class="mathCode">$x_0$.