Gradient Descent with Random Initialization: Fast Global Convergence for Nonconvex Phase Retrieval.

ABSTRACT: This paper considers the problem of solving systems of quadratic equations, namely, recovering an object of interest x ♮ ∈ ℝ n from m quadratic equations/samples y i = ( a i ⊤ x ♮ ) 2 , 1 ≤ i ≤ m . This problem, also dubbed as phase retrieval, spans multiple domains including physical sciences and machine learning. We investigate the efficacy of gradient descent (or Wirtinger flow) designed for the nonconvex least squares problem. We prove that under Gaussian designs, gradient descent - when randomly initialized - yields an ϵ-accurate solution in O(log n + log(1/ϵ)) iterations given nearly minimal samples, thus achieving near-optimal computational and sample complexities at once. This provides the first global convergence guarantee concerning vani

SUBMITTER: Chen Y 

PROVIDER: S-EPMC8025800 | biostudies-literature | 2019 Jul

REPOSITORIES: biostudies-literature