A strong restricted isometry property, with an application to phaseless compressed sensing

详细信息    查看全文

• 作者：Vladislav Voroninski^a ; ^{vvlad@math.mit.edu" class="auth_mail" title="E-mail the corresponding author} ; Zhiqiang Xu^b ; ^{xuzq@lsec.cc.ac.cn" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Signal recovery ; Phase retrieval ; Compressed sensing ; Johnson&ndash ; Lindenstrauss Lemma ; Restricted isometry property ; Compressed phaseless sensing
• 刊名：Applied and Computational Harmonic Analysis
• 出版年：2016
• 出版时间：March 2016
• 年：2016
• 卷：40
• 期：2
• 页码：386-395
• 全文大小：331 K

文摘

The many variants of the restricted isometry property (RIP) have proven to be crucial theoretical tools in the fields of compressed sensing and matrix completion. The study of extending compressed sensing to accommodate phaseless measurements naturally motivates a strong notion of restricted isometry property (SRIP), which we develop in this paper. We show that if A∈R^m×n$A\in {\mathbb{R}}^{m\times n}$ satisfies SRIP and phaseless measurements |Ax₀|=b$|A{x}_0|=b$ are observed about a k  -sparse signal x₀∈Rⁿ$x_0\in {\mathbb{R}}^n$, then minimizing the ℓ₁${\ell }_1$ norm subject to |Ax|=b$|Ax|=b$ recovers x₀$x_0$ up to multiplication by a global sign. Moreover, we establish that the SRIP holds for the random Gaussian matrices typically used for standard compressed sensing, implying that phaseless compressed sensing is possible from O(klog⁡(en/k))$O(k\log (en/k))$ measurements with these matrices via ℓ₁${\ell }_1$ minimization over |Ax|=b$|Ax|=b$. Our analysis also yields an erasure robust version of the Johnson–Lindenstrauss Lemma.