A Caltech Library Service

Learning without the Phase: Regularized PhaseMax Achieves Optimal Sample Complexity

Salehi, Fariborz and Abbasi, Ehsan and Hassibi, Babak (2018) Learning without the Phase: Regularized PhaseMax Achieves Optimal Sample Complexity. In: Advances in Neural Information Processing Systems 31. Advances in Neural Information Processing Systems. No.31. Neural Information Processing Systems , Red Hook, NY, pp. 1-12.

[img] PDF - Published Version
See Usage Policy.

[img] Archive (ZIP) - Supplemental Material
See Usage Policy.


Use this Persistent URL to link to this item:


The problem of estimating an unknown signal, x_0 ϵ R^n, from a vector y ϵ R^m consisting of m magnitude-only measurements of the form y_i = |a_ix_o|, where a_i’s are the rows of a known measurement matrix A is a classical problem known as phase retrieval. This problem arises when measuring the phase is costly or altogether infeasible. In many applications in machine learning, signal processing, statistics, etc., the underlying signal has certain structure (sparse, low-rank, finite alphabet, etc.), opening of up the possibility of recovering x_0 from a number of measurements smaller than the ambient dimension, i.e., m < n. Ideally, one would like to recover the signal from a number of phaseless measurements that is on the order of the "degrees of freedom" of the structured x_0. To this end, inspired by the PhaseMax algorithm, we formulate a convex optimization problem, where the objective function relies on an initial estimate of the true signal and also includes an additive regularization term to encourage structure. The new formulation is referred to as regularized PhaseMax. We analyze the performance of regularized PhaseMax to find the minimum number of phaseless measurements required for perfect signal recovery. The results are asymptotic and are in terms of the geometrical properties (such as the Gaussian width) of certain convex cones. When the measurement matrix has i.i.d. Gaussian entries, we show that our proposed method is indeed order-wise optimal, allowing perfect recovery from a number of phaseless measurements that is only a constant factor away from the degrees of freedom. We explicitly compute this constant factor, in terms of the quality of the initial estimate, by deriving the exact phase transition. The theory well matches empirical results from numerical simulations.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Additional Information:© 2019 Neural Information Processing Systems Foundation, Inc. This work was supported in part by the National Science Foundation under grants CNS-0932428, CCF-1018927, CCF-1423663 and CCF-1409204, by a grant from Qualcomm Inc., by NASA’s Jet Propulsion Laboratory through the President and Director’s Fund, and by King Abdullah University of Science and Technology.
Funding AgencyGrant Number
JPL President and Director's FundUNSPECIFIED
King Abdullah University of Science and Technology (KAUST)UNSPECIFIED
Series Name:Advances in Neural Information Processing Systems
Issue or Number:31
Record Number:CaltechAUTHORS:20190416-102710748
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:94731
Deposited By: Tony Diaz
Deposited On:16 Apr 2019 20:09
Last Modified:03 Oct 2019 21:06

Repository Staff Only: item control page