Optimal rates of convergence for noisy sparse phase retrieval via thresholded Wirtinger flow

DOI10.1214/16-AOS1443zbMATH Open1349.62019arXiv1506.03382OpenAlexW2962999772MaRDI QIDQ342686FDOQ342686

Authors: Xiaodong Li, Zongming Ma, T. Tony Cai 

Publication date: 18 November 2016

Published in: The Annals of Statistics (Search for Journal in Brave)

Abstract: This paper considers the noisy sparse phase retrieval problem: recovering a sparse signal $xinmathbb{R}^p$ from noisy quadratic measurements $y_j=({a_j}^{\prime }x{)}^2+epsilo{n}_j$, $j=1,ldots,m$, with independent sub-exponential noise $epsilo{n}_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. Inspired by the Wirtinger Flow [12] proposed for noiseless and non-sparse 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$.

Full work available at URL: https://arxiv.org/abs/1506.03382

Recommendations

• Phase retrieval via Wirtinger flow: theory and algorithms
• Phase retrieval via sparse Wirtinger flow
• Sparse signal recovery from phaseless measurements via hard thresholding pursuit
• Phase retrieval for sparse signals
• \(L_{1/2}\)-regularized least absolute deviation method for sparse phase retrieval

zbMATH Keywords

sparse recoveryminimax ratephase retrievaliterative adaptive thresholdingnon-convex empirical riskthresholded gradient method

Mathematics Subject Classification ID

Minimax procedures in statistical decision theory (62C20) Applications of statistics to physics (62P35)

Cited In (34)

• The numerics of phase retrieval
• Gradient descent with random initialization: fast global convergence for nonconvex phase retrieval
• Compressive phase retrieval: Optimal sample complexity with deep generative priors
• ISLET: fast and optimal low-rank tensor regression via importance sketching
• First-order methods almost always avoid strict saddle points
• Robust amplitude method with \(L_{1/2}\)-regularization for compressive phase retrieval
• Robust High-Dimensional Regression with Coefficient Thresholding and Its Application to Imaging Data Analysis
• Rate-optimal perturbation bounds for singular subspaces with applications to high-dimensional statistics
• Cardinality minimization, constraints, and regularization: a survey
• Implicit regularization in nonconvex statistical estimation: gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution
• Inertial proximal ADMM for separable multi-block convex optimizations and compressive affine phase retrieval
• Toward a mathematical theory of the crystallographic phase retrieval problem
• An optimal statistical and computational framework for generalized tensor estimation
• Phase retrieval from Fourier measurements with masks
• Fundamental limits of weak recovery with applications to phase retrieval
• Phase retrieval with PhaseLift algorithm
• A geometric analysis of phase retrieval
• Provable sample-efficient sparse phase retrieval initialized by truncated power method
• Constructing confidence intervals for the signals in sparse phase retrieval
• Nearly minimax-optimal rates for noisy sparse phase retrieval via early-stopped mirror descent
• An Efficient and Robust Scalar Auxialiary Variable Based Algorithm for Discrete Gradient Systems Arising from Optimizations
• Performance bounds of the intensity-based estimators for noisy phase retrieval
• Sparse signal recovery from phaseless measurements via hard thresholding pursuit
• On DC based methods for phase retrieval
• Misspecified nonconvex statistical optimization for sparse phase retrieval
• Phase retrieval using alternating minimization in a batch setting
• Model-free nonconvex matrix completion: local minima analysis and applications in memory-efficient kernel PCA
• \(L_{1/2}\)-regularized least absolute deviation method for sparse phase retrieval
• The recovery of complex sparse signals from few phaseless measurements
• Truncated amplitude flow with coded diffraction patterns
• Partially Observed Dynamic Tensor Response Regression
• Variational phase retrieval with globally convergent preconditioned proximal algorithm
• Phase retrieval via sparse Wirtinger flow
• Proof methods for robust low-rank matrix recovery

This page was built for publication: Optimal rates of convergence for noisy sparse phase retrieval via thresholded Wirtinger flow

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q342686)