Phase Retrieval Using Alternating Minimization

By Praneeth Netrapalli, Prateek Jain, Sujay Sanghavi. IEEE Transactions on Signal Processing, 2013

667 citations recorded by the source corpus.

Phase retrieval problems involve solving linear equations, but with missing sign (or phase, for complex numbers) information. More than four decades after it was first proposed, the seminal error reduction algorithm of Gerchberg and Saxton and Fienup is still the popular choice for solving many variants of this problem. The algorithm is based on alternating minimization; i.e., it alternates between estimating the missing phase information, and the candidate solution. Despite its wide usage in practice, no global convergence guarantees for this algorithm are known. In this paper, we show that a (resampling) variant of this approach converges geometrically to the solution of one such problem-finding a vector x from y, A, where y = |ATx| and |z| denotes a vector of element-wise magnitudes of z-under the assumption that A is Gaussian. Empirically, we demonstrate that alternating minimization performs similar to recently proposed convex techniques for this problem (which are based on “lifting” to a convex matrix problem) in sample complexity and robustness to noise. However, it is much more efficient and can scale to large problems. Analytically, for a resampling version of alternating minimization, we show geometric convergence to the solution, and sample complexity that is off by log factors from obvious lower bounds. We also establish close to optimal scaling for the case when the unknown vector is sparse. Our work represents the first theoretical guarantee for alternating minimization (albeit with resampling) for any variant of phase retrieval problems in the non-convex setting.

Subfields: Computer Vision and Pattern Recognition, Radiation

View Paper: https://www.semanticscholar.org/paper/944ef766160f1f937ab0e9b136b92547c8c9c9d8

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Vision and Pattern Recognition

In Radiation

Citations in the corpus

Non-convex Optimization for Machine Learning (2017, methodology): “[2009], Nguyen and Tran [2013a]. The work of Chen et al. [2013] considers corruptions not only in the responses, but in the covariates as well. However, these methods tend to scale poorly to really large scale problems owing to the non-smooth nature of the optimization problems that they end up solv”
Alternating Minimization Algorithms for Hybrid Precoding in Millimeter Wave MIMO Systems (2016, methodology): “has been successfully applied to many applications such as matrix completion [14], phase retrieval [36], image reconstruction [37], blind deconvolution [38] and non-negative matrix”
Simple, Efficient, and Neural Algorithms for Sparse Coding (2015, background): “This adds to the recent literature on analyzing alternating minimization Jain et al. (2013); Hardt (2013); Netrapalli et al. (2013, 2014) but these work in a setting where there is a convex program that is known to work too, and in our setting, the only known convex program runs in time exponential…”
Learning Sparsely Used Overcomplete Dictionaries via Alternating Minimization (2013, background): “More interestingly, our work extends a growing body of recent literature on analysis of alternating minimization methods for a variety of nonconvex factorization problems [15, 24], where global in addition to local results are being established with D ow nl oa de d 09 /2 0/ 17 to 1 31 .”
Statistical guarantees for the EM algorithm: From population to sample-based analysis (2014, background): “[21, 22, 35, 52]) which show that at least in certain special cases optimization methods can be locally effective despite non-convexity.”
Complete dictionary recovery over the sphere (2015, result): “The particular geometry of this problem does not demand any clever initialization, in contrast with most recent approaches to analyzing nonconvex recovery of structured signals [9–11, 13, 18–30].”
A Geometric Analysis of Phase Retrieval (2016, methodology): “Results in [31,76] and this paper pertain only to adaptive measurements that recover any fixed signal x with high probability.”
An Efficient Framework for Clustered Federated Learning (2020, methodology): “In recent years, some progress has been made towards understanding the convergence of EM and AM in the centralized setting (Netrapalli et al., 2013; Daskalakis et al., 2016; Yi et al., 2016; Balakrishnan et al., 2017; Waldspurger, 2018).”
Guaranteed Matrix Completion via Non-Convex Factorization (2014, neutral): “1.5.3].”
Dropping Convexity for Faster Semi-definite Optimization (2015, methodology): “…includes matrix completion [21, 42, 49, 22], aﬃne rank minimization [65, 41, 8], covariance / inverse covariance selection [38, 50], phase retrieval [64, 18, 77, 68], Euclidean distance matrix completion [56], ﬁnding the square root of a PSD matrix [40], and sparse PCA [26], just to name a few.”
Sketchy Decisions: Convex Low-Rank Matrix Optimization with Optimal Storage (2017, background): “Instead, many researchers apply nonconvex heuristics to solve phase retrieval problems [9, 14, 21, 26].”
Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview (2018, methodology): “[102] used this method to address the problem of phase retrieval, the theoretical guarantee of which was tightened in [19].”
Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems (2015, methodology): “It is worth noting that apart from WF, various other nonconvex procedures have been proposed as well for phase retrieval, including the error reduction schemes dating back to Gerchberg-Saxton and Fienup [20,21], iterated projections [19], alternating minimization [32], generalized approximate messag”
An Overview of Low-Rank Matrix Recovery From Incomplete Observations (2016, methodology): “In [128], a theoretical analysis of alternating projections for phase retrieval was given (along with an intelligent method for initializing the algorithm) that gives a guarantee of effectiveness when L N log(3) N .”
Phase Retrieval via Wirtinger Flow: Theory and Algorithms (2014, background): “If the loss function is non-negative and vanishes only when x = y, then a solution to the generalized phase retrieval problem (1.1) is any solution to minimize f(z) ∶= 1 2m m ∑ r=1 `(yr, ∣a ∗ rz∣ 2 ), z ∈ Cn. (2.1) Although one could study many loss functions, we shall focus in this paper on the…”
How to Escape Saddle Points Efficiently (2017, background): “Netrapalli et al., 2013, Candes et al., 2015, Sun and Luo, 2016, Bhojanapalli et al., 2016].”
Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution (2017, background): “On the other hand, alternating minimization [90] with sample splitting has been shown to enjoy much better computational guarantee.”