Solving Quadratic Equations via PhaseLift When There Are About as Many Equations as Unknowns

被引：170

作者：

Candes, Emmanuel J. ^{[1
,2
]}

Li, Xiaodong ^{[1
]}

机构：

[1] Stanford Univ, Dept Stat, Stanford, CA 94305 USA

[2] Stanford Univ, Dept Stat, Stanford, CA 94305 USA

来源：

FOUNDATIONS OF COMPUTATIONAL MATHEMATICS | 2014年 / 14卷 / 05期

基金：

美国国家科学基金会;

关键词：

Phase retrieval; PhaseLift; Semidefinite relaxations of nonconvex quadratic programs; Deviation inequalities for random matrices;

D O I：

10.1007/s10208-013-9162-z

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

This note shows that we can recover any complex vector exactly from on the order of n quadratic equations of the form |aOE (c) a (i) ,x (0)>|(2)=b (i) , i=1,aEuro broken vertical bar,m, by using a semidefinite program known as PhaseLift. This improves upon earlier bounds in CandSs et al. (Commun. Pure Appl. Math. 66:1241-1274, 2013), which required the number of equations to be at least on the order of nlogn. Further, we show that exact recovery holds for all input vectors simultaneously, and also demonstrate optimal recovery results from noisy quadratic measurements; these results are much sharper than previously known results.

引用

页码：1017 / 1026

页数：10

共 5 条

[1] On signal reconstruction without phase
Balan, Radu
Casazza, Pete
Edidin, Dan
[J]. APPLIED AND COMPUTATIONAL HARMONIC ANALYSIS, 2006, 20 (03) : 345 - 356
[2] Phase Retrieval via Matrix Completion
Candes, Emmanuel J.
Eldar, Yonina C.
Strohmer, Thomas
Voroninski, Vladislav
[J]. SIAM JOURNAL ON IMAGING SCIENCES, 2013, 6 (01): : 199 - 225
[3] PhaseLift: Exact and Stable Signal Recovery from Magnitude Measurements via Convex Programming
Candes, Emmanuel J.
Strohmer, Thomas
Voroninski, Vladislav
[J]. COMMUNICATIONS ON PURE AND APPLIED MATHEMATICS, 2013, 66 (08) : 1241 - 1274
[4] Demanet L, 2012, ARXIV E PRINTS
[5] Vershynin R., 2012, COMPRESSED SENSING, P210, DOI [DOI 10.1017/CBO9780511794308.006, 10.1017/CBO9780511794308.006, 10.1017/cbo9780511794308.006]

← 1 →