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 rc">formulatext stixSupport mathImg" data-mathURL="/science?_ob=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×nr hidden">rflow="scroll">A∈row>riant="double-struck">Rrow>row>m×nrow> satisfies SRIP and phaseless measurements rc">formulatext stixSupport mathImg" data-mathURL="/science?_ob=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">|Ax₀|=br hidden">rflow="scroll">retchy="false">|Arow>xrow>row>0row>retchy="false">|=b are observed about a k  -sparse signal rc">formulatext stixSupport mathImg" data-mathURL="/science?_ob=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">x₀∈Rⁿr hidden">rflow="scroll">row>xrow>row>0row>∈row>riant="double-struck">Rrow>row>nrow>, then minimizing the rc">formulatext stixSupport mathImg" data-mathURL="/science?_ob=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">ℓ₁r hidden">rflow="scroll">row>ℓrow>row>1row> norm subject to rc">formulatext stixSupport mathImg" data-mathURL="/science?_ob=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|=br hidden">rflow="scroll">retchy="false">|Axretchy="false">|=b recovers rc">formulatext stixSupport mathImg" data-mathURL="/science?_ob=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">x₀r hidden">rflow="scroll">row>xrow>row>0row> 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 rc">formulatext stixSupport mathImg" data-mathURL="/science?_ob=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))r hidden">rflow="scroll">Oretchy="false">(kriant="normal">log⁡retchy="false">(enretchy="false">/kretchy="false">)retchy="false">) measurements with these matrices via rc">formulatext stixSupport mathImg" data-mathURL="/science?_ob=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">ℓ₁r hidden">rflow="scroll">row>ℓrow>row>1row> minimization over rc">formulatext stixSupport mathImg" data-mathURL="/science?_ob=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|=br hidden">rflow="scroll">retchy="false">|Axretchy="false">|=b. Our analysis also yields an erasure robust version of the Johnson–Lindenstrauss Lemma.