OPTIMAL RATES OF CONVERGENCE FOR NOISY SPARSE PHASE RETRIEVAL VIA THRESHOLDED WIRTINGER FLOW

• 成果类型: Article
• 署名作者: Cai, T. Tony; Li, Xiaodong; Ma, Zongming
• 署名单位: University of Pennsylvania; University of California System; University of California Davis
• 刊物名称: ANNALS OF STATISTICS
• ISSN/ISSBN: 0090-5364
• DOI: 10.1214/16-AOS1443
• 发表日期: 2016
• 页码: 2221-2251
• 关键词: signal recovery; algorithm; image

摘要

This paper considers the noisy sparse phase retrieval problem: recovering a sparse signal x is an element of R-P from noisy quadratic measurements y(j) = (a(j)'x)(2) + epsilon(j), j = 1,... m, with independent sub-exponential noise epsilon(j). The goals are to understand the effect of the sparsity of x on the estimation precision and to construct a computationally feasible estimator to achieve the optimal rates adaptively. Inspired by the Wirtinger Flow [IEEE Trans. Inform. Theory 61 (2015) 1985-2007] proposed for non-sparse and noiseless phase retrieval, a novel thresholded gradient descent algorithm is proposed and it is shown to adaptively achieve the minimax optimal rates of convergence over a wide range of sparsity levels when the a(j)'s are independent standard Gaussian random vectors, provided that the sample size is sufficiently large compared to the sparsity of x.