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 b=MathURL&_method=retrieve&_eid=1-s2.0-S1063520315000901&_mathId=si1.gif&_user=111111111&_pii=S1063520315000901&_rdoc=1&_issn=10635203&md5=9e845d43a7f1a13dc052e4ab51b3703b" title="Click to view the MathML source">A∈R^m×n satisfies SRIP and phaseless measurements b=MathURL&_method=retrieve&_eid=1-s2.0-S1063520315000901&_mathId=si2.gif&_user=111111111&_pii=S1063520315000901&_rdoc=1&_issn=10635203&md5=8d96355d3d4e21cc96aef2869015f81c" title="Click to view the MathML source">|Axb>0b>|=b are observed about a k  -sparse signal b=MathURL&_method=retrieve&_eid=1-s2.0-S1063520315000901&_mathId=si3.gif&_user=111111111&_pii=S1063520315000901&_rdoc=1&_issn=10635203&md5=f07fd28a6b43db1912ba9ab3b9f0318f" title="Click to view the MathML source">xb>0b>∈Rⁿ, then minimizing the b=MathURL&_method=retrieve&_eid=1-s2.0-S1063520315000901&_mathId=si4.gif&_user=111111111&_pii=S1063520315000901&_rdoc=1&_issn=10635203&md5=b99adb36838f4f52c7263494dd2cf488" title="Click to view the MathML source">ℓb>1b> norm subject to b=MathURL&_method=retrieve&_eid=1-s2.0-S1063520315000901&_mathId=si5.gif&_user=111111111&_pii=S1063520315000901&_rdoc=1&_issn=10635203&md5=476b51babe6416af12074752583f6a36" title="Click to view the MathML source">|Ax|=b$|Ax|=\mathrm{<font\; color="red">b</font>}$ recovers b=MathURL&_method=retrieve&_eid=1-s2.0-S1063520315000901&_mathId=si6.gif&_user=111111111&_pii=S1063520315000901&_rdoc=1&_issn=10635203&md5=51dac00f8e2d0ec01d8d235c8e8686b4" title="Click to view the MathML source">xb>0b> 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 b=MathURL&_method=retrieve&_eid=1-s2.0-S1063520315000901&_mathId=si19.gif&_user=111111111&_pii=S1063520315000901&_rdoc=1&_issn=10635203&md5=40b29d277c217365e9bd411b91a3667d" title="Click to view the MathML source">O(klog⁡(en/k))$O(k\log (en/k))$ measurements with these matrices via b=MathURL&_method=retrieve&_eid=1-s2.0-S1063520315000901&_mathId=si4.gif&_user=111111111&_pii=S1063520315000901&_rdoc=1&_issn=10635203&md5=b99adb36838f4f52c7263494dd2cf488" title="Click to view the MathML source">ℓb>1b> minimization over b=MathURL&_method=retrieve&_eid=1-s2.0-S1063520315000901&_mathId=si5.gif&_user=111111111&_pii=S1063520315000901&_rdoc=1&_issn=10635203&md5=476b51babe6416af12074752583f6a36" title="Click to view the MathML source">|Ax|=b$|Ax|=\mathrm{<font\; color="red">b</font>}$. Our analysis also yields an erasure robust version of the Johnson–Lindenstrauss Lemma.