Median-Truncated Nonconvex Approach for Phase Retrieval With Outliers
Median-Truncated Nonconvex Approach for Phase Retrieval With Outliers
复制标题
DOI：
10.1109/tit.2018.2847695
复制
发表时间：
2016-03
影响因子：
2.5
通讯作者：
Huishuai Zhang;Yuejie Chi;Yingbin Liang
中科院分区：
文献类型：
--
作者：
Huishuai Zhang;Yuejie Chi;Yingbin Liang
本文研究了相位检索问题，该问题旨在从其线性测量的大小中恢复信号。当测量结果被稀疏的离群值损坏时，我们可以在统计和计算上开发统计和计算有效的算法。我们提出了一种新颖的方法，通过使用样品中位数作为修剪初始化和局部搜索中的虚假样品的指南来鲁棒性梯度下降算法。分别采用泊松损失和重塑二次损失，我们获得了两种算法，称为中位数截断器流量和中间示例示例线的电线流，两者都可以从近乎最佳的测量值中恢复信号。独立和相同分布的高斯条目，即使是对数因素，即使是恒定的分数测量是对手损坏的。我们进一步表明，在存在额外的密集噪声的情况下，这两种算法都是稳定的。我们的分析是通过开发中位数相关数量的非平凡浓度结果来完成的，这可能具有独立的兴趣。我们提供数值实验以证明我们方法的有效性。
This paper investigates the phase retrieval problem, which aims to recover a signal from the magnitudes of its linear measurements. We develop statistically and computationally efficient algorithms for the situation when the measurements are corrupted by sparse outliers that can take arbitrary values. We propose a novel approach to robustify the gradient descent algorithm by using the sample median as a guide for pruning spurious samples in initialization and local search. Adopting a Poisson loss and a reshaped quadratic loss, respectively, we obtain two algorithms termed median-truncated Wirtinger flow and median-reshaped Wirtinger flow, both of which provably recover the signal from a near-optimal number of measurements when the measurement vectors are composed of independent and identically distributed Gaussian entries, up to a logarithmic factor, even when a constant fraction of the measurements is adversarially corrupted. We further show that both algorithms are stable in the presence of additional dense bounded noise. Our analysis is accomplished by developing non-trivial concentration results of median-related quantities, which may be of independent interest. We provide numerical experiments to demonstrate the effectiveness of our approach.