The DOI matches its Crossref record; 34 of the 34 references it cites were found in a registry or an index.
Phase Retrieval Using Alternating Minimization
Open accessAbstract
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Phase retrieval algorithms: a comparison
Fienup, J. R. (1982) · Applied Optics · doi:10.1364/ao.21.002758 · Cited by 5,596
GABOR, D. (1948) · Nature · doi:10.1038/161777a0 · Cited by 4,548
A practical algorithm for the determination of phase from image and diffraction plane pictures
Gerchberg, R. W. (1972) · Optik · Cited by 4,519
Sparse Principal Component Analysis
Zou, H., Hastie, T., & Tibshirani, R. (2006) · Journal of Computational and Graphical Statistics · doi:10.1198/106186006x113430 · Cited by 3,152
Introduction to the non-asymptotic analysis of random matrices
Vershynin, R. (2012) · Compressed Sensing · doi:10.1017/cbo9780511794308.006 · Cited by 2,150
Miao, J., Charalambous, P., Kirz, J., & Sayre, D. (1999) · Nature · doi:10.1038/22498 · Cited by 1,976
Reconstructed Wavefronts and Communication Theory*
Leith, E. N., & Upatnieks, J. (1962) · Journal of the Optical Society of America · doi:10.1364/josa.52.001123 · Cited by 1,658
PhaseLift: Exact and Stable Signal Recovery from Magnitude Measurements via Convex Programming
Candès, E. J., Strohmer, T., & Voroninski, V. (2013) · Communications on Pure and Applied Mathematics · doi:10.1002/cpa.21432 · Cited by 1,197
Methods used in the structure determination of bovine mitochondrial F1 ATPase
Abrahams, J. P., & Leslie, A. G. W. (1996) · Acta Crystallographica Section D Biological Crystallography · doi:10.1107/s0907444995008754 · Cited by 1,089
Image Restoration by the Method of Convex Projections: Part 1ߞTheory
Youla, D. C., & Webb, H. (1982) · IEEE Transactions on Medical Imaging · doi:10.1109/tmi.1982.4307555 · Cited by 1,021
Cited by
Majorization-Minimization Algorithms in Signal Processing, Communications, and Machine Learning
Sun, Y., Babu, P., & Palomar, D. P. (2017) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2016.2601299 · Cited by 1,820
Alternating Minimization Algorithms for Hybrid Precoding in Millimeter Wave MIMO Systems
Yu, X., Shen, J.-C., Zhang, J., & Letaief, K. B. (2016) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2016.2523903 · Cited by 1,444
Phase Retrieval with Application to Optical Imaging: A contemporary overview
Shechtman, Y., Eldar, Y. C., Cohen, O., Chapman, H. N., Miao, J., & Segev, M. (2015) · IEEE Signal Processing Magazine · doi:10.1109/msp.2014.2352673 · Cited by 1,131
An Efficient Framework for Clustered Federated Learning
Ghosh, A., Chung, J., Yin, D., & Ramchandran, K. (2022) · IEEE Transactions on Information Theory · doi:10.1109/tit.2022.3192506 · Cited by 623
Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems
Chen, Y., & Candès, E. J. (2017) · Communications on Pure and Applied Mathematics · doi:10.1002/cpa.21638 · Cited by 477
An Overview of Low-Rank Matrix Recovery From Incomplete Observations
Davenport, M. A., & Romberg, J. (2016) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2016.2539100 · Cited by 439
Statistical guarantees for the EM algorithm: From population to sample-based analysis
Balakrishnan, S., Wainwright, M. J., & Yu, B. (2017) · The Annals of Statistics · doi:10.1214/16-aos1435 · Cited by 384
Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
Chi, Y., Lu, Y. M., & Chen, Y. (2019) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2019.2937282 · Cited by 360
Enabling Secure Wireless Communications via Intelligent Reflecting Surfaces
Yu, X., Xu, D., & Schober, R. (2019) · 2019 IEEE Global Communications Conference (GLOBECOM) · doi:10.1109/globecom38437.2019.9014322 · Cited by 355
Solving Systems of Random Quadratic Equations via Truncated Amplitude Flow
Wang, G., Giannakis, G. B., & Eldar, Y. C. (2018) · IEEE Transactions on Information Theory · doi:10.1109/tit.2017.2756858 · Cited by 330
Guaranteed Matrix Completion via Non-Convex Factorization
Sun, R., & Luo, Z.-Q. (2016) · IEEE Transactions on Information Theory · doi:10.1109/tit.2016.2598574 · Cited by 309
Compressive Phase Retrieval via Generalized Approximate Message Passing
Schniter, P., & Rangan, S. (2015) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2014.2386294 · Cited by 279
Complete Dictionary Recovery Over the Sphere I: Overview and the Geometric Picture
Sun, J., Qu, Q., & Wright, J. (2017) · IEEE Transactions on Information Theory · doi:10.1109/tit.2016.2632162 · Cited by 213
“Putting together the above estimates for the case w (cid:54) = 0 , we obtain Hence for all w , we can take the 1 5 √ 2 π as the lower bound, completing the proof.”
MethodMassive CSI Acquisition for Dense Cloud-RANs With Spatial-Temporal Dynamics
Liu, X., Shi, Y., Zhang, J., & Letaief, K. B. (2018) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2018.2797969 · Cited by 11
Metadata
- Authors
- Netrapalli, P., Jain, P., & Sanghavi, S.
- Venue
- IEEE Transactions on Signal Processing
- Published
- 2015-09
- Volume
- 63
- Issue
- 18
- Pages
- 4814-4826
- ISSN
- 1053-587X (ISSN-L)
- 1941-0476
- OpenAlex
- W2158746276
- Cited by
- 535
- References
- 34
- FWCI
- 65.81
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.