Fundamental Limits of Weak Recovery with Applications to Phase Retrieval
Fundamental Limits of Weak Recovery with Applications to Phase Retrieval
复制标题
DOI：
10.1007/s10208-018-9395-y
复制
发表时间：
2019-06-01
影响因子：
3
通讯作者：
Montanari, Andrea
中科院分区：
文献类型：
--
作者：
Mondelli, Marco;Montanari, Andrea
在相位恢复中，我们希望从形式为yi=|ai，x|2+wi的n个二次测量中恢复未知信号xcd，其中aicd是已知的感测向量，wi是测量噪声。我们问下面的弱恢复问题：产生与信号x正相关的估计器x(Y)所需的最小测量次数n是多少？我们考虑高斯向量ai的情况。我们证明了在高维极限中发生了尖锐的相变，并将阈值定位在噪声为零的区域。对于ND-O(D)，没有任何估计量可以比随机变量做得更好，并实现严格的正相关。对于Nd+o(D)，一个简单的谱估计器就可以实现正相关。令人惊讶的是，使用相同谱估计器的数值模拟结果显示，在使用真实感知矩阵的情况下具有良好的性能。谱方法被用来初始化相位恢复中的非凸优化算法，并且我们的方法也可以在这种情况下提高性能。我们的不可能结果是基于经典信息论的论证。谱算法计算加权经验协方差矩阵的主导特征向量。我们利用自由概率中的工具和推广了Lu和Li最近的一个结果，得到了这个随机矩阵的谱性质的一个精确的刻画。上界和下界都超越了相位恢复，推广到根据广义线性模型产生的测量值YI。作为分析的副产品，我们将所提出的谱方法的阈值与消息传递算法的阈值进行了比较。
In phase retrieval, we want to recover an unknown signal xCd from n quadratic measurements of the form yi=|ai,x|2+wi, where aiCd are known sensing vectors and wi is measurement noise. We ask the following weak recovery question: What is the minimum number of measurements n needed to produce an estimator x(y) that is positively correlated with the signal x? We consider the case of Gaussian vectors ai. We prove thatin the high-dimensional limita sharp phase transition takes place, and we locate the threshold in the regime of vanishingly small noise. For nd-o(d), no estimator can do significantly better than random and achieve a strictly positive correlation. For nd+o(d), a simple spectral estimator achieves a positive correlation. Surprisingly, numerical simulations with the same spectral estimator demonstrate promising performance with realistic sensing matrices. Spectral methods are used to initialize non-convex optimization algorithms in phase retrieval, and our approach can boost the performance in this setting as well. Our impossibility result is based on classical information-theoretic arguments. The spectral algorithm computes the leading eigenvector of a weighted empirical covariance matrix. We obtain a sharp characterization of the spectral properties of this random matrix using tools from free probability and generalizing a recent result by Lu and Li. Both the upper bound and lower bound generalize beyond phase retrieval to measurements yi produced according to a generalized linear model. As a by-product of our analysis, we compare the threshold of the proposed spectral method with that of a message passing algorithm.