Learning without the Phase: Regularized PhaseMax Achieves Optimal Sample Complexity
Abstract
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.
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.Attached Files
Published - 8082-learning-without-the-phase-regularized-phasemax-achieves-optimal-sample-complexity.pdf
Supplemental Material - 8082-learning-without-the-phase-regularized-phasemax-achieves-optimal-sample-complexity-supplemental.zip
Files
Name | Size | Download all |
---|---|---|
md5:bcaba8b1ef234acac3eb0eb3188e4a82
|
707.9 kB | Preview Download |
md5:58c28297deee534574d40a4e4b00835a
|
588.8 kB | Preview Download |
Additional details
- Eprint ID
- 94731
- Resolver ID
- CaltechAUTHORS:20190416-102710748
- NSF
- CCF-1018927
- NSF
- CCF-1423663
- NSF
- CCF-1409204
- Qualcomm Inc.
- JPL President and Director's Fund
- King Abdullah University of Science and Technology (KAUST)
- Created
-
2019-04-16Created from EPrint's datestamp field
- Updated
-
2019-10-03Created from EPrint's last_modified field
- Series Name
- Advances in Neural Information Processing Systems
- Series Volume or Issue Number
- 31