Adaptive Algorithms for Robust Phase Retrieval

Abstract

This paper considers robust phase retrieval, which can be cast as a nonsmooth and nonconvex optimization problem. We propose two first-order algorithms with adaptive step sizes: the subgradient algorithm (AdaSubGrad) and the inexact proximal linear algorithm (AdaIPL). Our contribution lies in a novel design of adaptive step sizes based on quantiles of the absolute residuals. We analyze local linear convergence of both algorithms across different hyperparameter regimes under i.i.d. centered sub-Gaussian measurements, a stability condition linking the measurement distribution and the corruption level, and an additional uniform small-ball condition. Numerical experiments on synthetic datasets and image recovery also demonstrate that our methods are competitive with existing methods in the literature that utilize predetermined (possibly impractical) step sizes, such as subgradient methods and the inexact proximal linear method.

This paper has been accepted for publication in the SIAM Journal on Optimization