Compressive Phase Retrieval via Generalized Approximate Message Passing

Abstract

In phase retrieval, the goal is to recover a signal $\mathbf{x}\in {\mathbb{C}}^N$ from the magnitudes of linear measurements $\mathbf{Ax}\in {\mathbb{C}}^M$. While recent theory has established that $M\approx 4N$ intensity measurements are necessary and sufficient to recover generic $\mathbf{x}$, there is great interest in reducing the number of measurements through the exploitation of sparse $\mathbf{x}$, which is known as compressive phase retrieval. In this work, we detail a novel, probabilistic approach to compressive phase retrieval based on the generalized approximate message passing (GAMP) algorithm. We then present a numerical study of the proposed PR-GAMP algorithm, demonstrating its excellent phase-transition behavior, robustness to noise, and runtime. Our experiments suggest that approximately $M\ge 2K{\log }_2(N/K)$ intensity measurements suffice to recover $K$-sparse Bernoulli-Gaussian signals for $\mathbf{A}$ with i.i.d Gaussian entries and $K\ll N$. Meanwhile, when recovering a 6k-sparse 65k-pixel grayscale image from 32k randomly masked and blurred Fourier intensity measurements at 30~dB measurement SNR, PR-GAMP achieved an output SNR of no less than 28~dB in all of 100 random trials, with a median runtime of only 7.3 seconds. Compared to the recently proposed CPRL, sparse-Fienup, and GESPAR algorithms, our experiments suggest that PR-GAMP has a superior phase transition and orders-of-magnitude faster runtimes as the sparsity and problem dimensions increase.

References in corpus (18)

• Message Passing Algorithms for Compressed Sensing
• Wide-field, high-resolution Fourier ptychographic microscopy
• The dynamics of message passing on dense graphs, with applications to compressed sensing
• Expectation-Maximization Gaussian-Mixture Approximate Message Passing
• GESPAR: Efficient Phase Retrieval of Sparse Signals
• Compressive Phase Retrieval via Generalized Approximate Message Passing
• Sparsity-based single-shot sub-wavelength coherent diffractive imaging
• Probabilistic Reconstruction in Compressed Sensing: Algorithms, Phase Diagrams, and Threshold Achieving Matrices
• Super-Resolution and Reconstruction of Sparse Sub-Wavelength Images
• Adaptive Damping and Mean Removal for the Generalized Approximate Message Passing Algorithm
• Quantum Tomography under Prior Information
• Compressive Phase Retrieval From Squared Output Measurements Via Semidefinite Programming
• Convex recovery from interferometric measurements
• An Empirical-Bayes Approach to Recovering Linearly Constrained Non-Negative Sparse Signals
• Variational Free Energies for Compressed Sensing
• Exact and Stable Covariance Estimation from Quadratic Sampling via Convex Programming
• Ab initio compressive phase retrieval
• Generalized Approximate Message Passing for Cosparse Analysis Compressive Sensing

Cited by in corpus (68)

• AMP-Inspired Deep Networks for Sparse Linear Inverse Problems
• Statistical physics of inference: Thresholds and algorithms
• Bilinear Generalized Approximate Message Passing
• Compressive Phase Retrieval via Generalized Approximate Message Passing
• Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
• Universality in polytope phase transitions and message passing algorithms
• Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Models
• Adaptive Damping and Mean Removal for the Generalized Approximate Message Passing Algorithm
• Scaling Limits of Wide Neural Networks with Weight Sharing: Gaussian Process Behavior, Gradient Independence, and Neural Tangent Kernel Derivation
• The Numerics of Phase Retrieval
• Learning-based real-time method to looking through scattering medium beyond the memory effect
• PRIME: Phase Retrieval via Majorization-Minimization
• Parametric Bilinear Generalized Approximate Message Passing
• Fast Beam Alignment for Millimeter Wave Communications: A Sparse Encoding and Phaseless Decoding Approach
• The distribution of the Lasso: Uniform control over sparse balls and adaptive parameter tuning
• Low-Rank Positive Semidefinite Matrix Recovery from Corrupted Rank-One Measurements
• Undersampled Phase Retrieval via Majorization-Minimization
• Capacity-achieving Spatially Coupled Sparse Superposition Codes with AMP Decoding
• Quantitative phase and polarisation endoscopy applied to detection of early oesophageal tumourigenesis
• Joint Visibility Region and Channel Estimation for Extremely Large-scale MIMO Systems
• Efficient Compressive Phase Retrieval with Constrained Sensing Vectors
• Intensity-only optical compressive imaging using a multiply scattering material and a double phase retrieval approach
• Binary Linear Classification and Feature Selection via Generalized Approximate Message Passing
• Phase retrieval in high dimensions: Statistical and computational phase transitions
• Single-step transmission matrix retrieval for fast imaging through multi-mode fibers
• Robust Compressive Phase Retrieval via Deep Generative Priors
• Intensity-only measurement of partially uncontrollable transmission matrix: demonstration with wave-field shaping in a microwave cavity
• Reducibility and Statistical-Computational Gaps from Secret Leakage
• Referenceless characterisation of complex media using physics-informed neural networks
• mmRAPID: Machine Learning assisted Noncoherent Compressive Millimeter-Wave Beam Alignment
• prDeep: Robust Phase Retrieval with a Flexible Deep Network
• Sparse Phase Retrieval via Truncated Amplitude Flow
• The estimation error of general first order methods
• Robust phase retrieval with the swept approximate message passing (prSAMP) algorithm
• Denoising Poisson Phaseless Measurements via Orthogonal Dictionary Learning
• PCA Initialization for Approximate Message Passing in Rotationally Invariant Models
• Achievable Rates for Short-Reach Fiber-Optic Channels with Direct Detection
• Phase Retrieval From Binary Measurements
• Approximate Message Passing with Parameter Estimation for Heavily Quantized Measurements
• Fourier Phase Retrieval with Extended Support Estimation via Deep Neural Network
• Towards Sample-Optimal Compressive Phase Retrieval with Sparse and Generative Priors
• Bayes-Optimal Estimation in Generalized Linear Models via Spatial Coupling
• On Compressed Sensing of Binary Signals for the Unsourced Random Access Channel
• A general framework for denoising phaseless diffraction measurements
• Low-complexity implementation of convex optimization-based phase retrieval
• Hadamard Wirtinger Flow for Sparse Phase Retrieval
• Generalized Approximate Message Passing for Cosparse Analysis Compressive Sensing
• 1-Bit Compressive Sensing via Approximate Message Passing with Built-in Parameter Estimation
• Fast phase retrieval for high dimensions: A block-based approach
• Compressive Computed Tomography Reconstruction through Denoising Approximate Message Passing
• Approximate Message Passing with Rigorous Guarantees for Pooled Data and Quantitative Group Testing
• Optimal convex lifted sparse phase retrieval and PCA with an atomic matrix norm regularizer
• Fast Phase Retrieval from Local Correlation Measurements
• Fast Compressive Phase Retrieval from Fourier Measurements
• Nearly Minimax-Optimal Rates for Noisy Sparse Phase Retrieval via Early-Stopped Mirror Descent
• Phase Retrieval using Expectation Consistent Signal Recovery Algorithm based on Hypernetwork
• Generalized Approximate Survey Propagation for High-Dimensional Estimation
• Grid-less Variational Bayesian Inference of Line Spectral from Quantized Samples
• $L^0$-regularized Variational Methods for Sparse Phase Retrieval
• Signal Recovery in Perturbed Fourier Compressed Sensing
• A Continuous-Time Mirror Descent Approach to Sparse Phase Retrieval
• Construction of optimal spectral methods in phase retrieval
• 3D Tomographic Phase Retrieval and Unwrapping
• Support Recovery in the Phase Retrieval Model: Information-Theoretic Fundamental Limits
• Phase Retrieval of Vortices in Bose-Einstein Condensates
• Symbol Detection for Coarsely Quantized OTFS
• Replica Analysis for Generalized Linear Regression with IID Row Prior
• Compressive phase retrieval of sparse bandlimited signals