Source-linked AI summary
Compressive Phase Retrieval From Squared Output Measurements Via Semidefinite Programming
Henrik Ohlsson, Allen Y. Yang, Roy Dong, S. Shankar Sastry
TL;DR
The paper addresses recovery of sparse signals when only squared magnitudes, not output phases, are observed. It uses lifting to formulate recovery as a semidefinite program, with exact recovery supported under stated conditions. The formulation extends compressive sensing to magnitude-only observations, though the current implementation faces computational and memory limits.
Problem
The paper asks how to recover sparse parameters when output phase is omitted and only squared-magnitude measurements are available.
Source: §1 · pp. 2–3, §2 · p. 5Method
Lifting turns the phase-retrieval problem into a semidefinite program, with a greedy approximate algorithm also proposed for low-sparsity settings.
Source: §1 · p. 3, §4.1 · p. 10Results
With high probability, the lifted SDP recovers the exact solution, sparse or dense, when the measurement count is at least of order O(n log n).
Source: §2 · p. 6Takeaways & Limitations
The SDP formulation provides a way to apply compressive sensing when only squared-magnitude measurements are available.
Source: §8 · p. 23The current CPRL implementation runs into computational and memory limits, and more efficient SDP numerics are needed to exploit its benefits fully.
Source: §7.2 · p. 22
Abstract
from arXiv · showhide
Given a linear system in a real or complex domain, linear regression aims to recover the model parameters from a set of observations. Recent studies in compressive sensing have successfully shown that under certain conditions, a linear program, namely, l1-minimization, guarantees recovery of sparse parameter signals even when the system is underdetermined. In this paper, we consider a more challenging problem: when the phase of the output measurements from a linear system is omitted. Using a lifting technique, we show that even though the phase information is missing, the sparse signal can be recovered exactly by solving a simple semidefinite program when the sampling rate is sufficiently high, albeit the exact solutions to both sparse signal recovery and phase retrieval are combinatorial. The results extend the type of applications that compressive sensing can be applied to those where only output magnitudes can be observed. We demonstrate the accuracy of the algorithms through theoretical analysis, extensive simulations and a practical experiment.
1 Introduction
The paper asks whether sparse signals can be recovered from squared-magnitude measurements when output phase is missing, and proposes a convex semidefinite formulation. It situates this problem at the intersection of compressive sensing and phase retrieval.
1 Introduction
- For underdetermined linear systems, least squares is non-unique, while ℓ1-based criteria seek sparse parameters and are known as LASSO, BPDN, or ℓ1-minimization.The λ parameter in the ridge objective trades off fit against the ℓ2 norm of x.Source: §1 · p. 2
- Squared-magnitude observations arise when output phase is lost; Fourier-transform modulus measurements are one example, with applications in optics, coherent diffraction, and astronomical imaging.The paper focuses its derivation primarily on complex signals and says the results should extend to real-domain signals.Source: §1 · pp. 2–3
- A phase-retrieval solution is unique only up to global phase, and Fourier measurements can also admit time-reversed or time-shifted ambiguities.The paper treats these ambiguities as acceptable in phase-retrieval applications.Source: §1 · p. 3
- Compressive phase retrieval asks whether convex programming can recover a sparse signal, up to global ambiguity, from squared-magnitude measurements.The paper frames this as an alternative to combinatorially expensive exact solutions to sparse recovery and phase retrieval.Source: §1 · pp. 2–3
- The proposed lifting-based convex formulation relaxes sparse phase retrieval as a semidefinite program and is evaluated against traditional compressive sensing and PhaseLift.The paper also derives bounds for guaranteed recovery and reports extensive experiments.Source: §1 · p. 3
1.1 Background
- Earlier phase-retrieval methods used iterative Fourier updates or special measurements, while lifted SDP approaches lacked the proposed sparsity constraint.The cited greedy compressive phase-retrieval method is nonconvex, assumes the true signal's ℓ1 norm is known, and provides no recovery guarantees.Source: §1.1 · pp. 4–5
2 CPR via SDP
CPRL lifts sparse phase retrieval into a semidefinite program by replacing a rank constraint with a trace penalty and adding an entrywise sparsity penalty. The section contrasts its sparse-signal regime with PhaseLift and illustrates CPRL’s support recovery.
2 CPR via SDP
- The CPR feasibility problem matches squared output magnitudes, and seeking the sparsest feasible signal addresses cases with too few measurements for uniqueness.The section relaxes the nonconvex sparsity objective using ℓ1 regularization before applying lifting.Source: §2 · p. 5
- Lifting represents the signal by a rank-1 positive semidefinite matrix, then relaxes rank using a trace penalty and adds an entrywise ℓ1 penalty for sparsity.The signal estimate is recovered from the lifted matrix’s rank-1 decomposition.Source: §2 · p. 6
- PhaseLift’s compared objective minimizes trace without a sparsity penalty, whereas CPRL adds an entrywise ℓ1 penalty to target sparse signals.The section notes that exact solutions to phase retrieval and compressed sensing are combinatorially expensive.Source: §2 · pp. 5–6
- PhaseLift’s lifted program recovers sparse or dense signals with high probability when N is at least of order O(n log n).Its source signal is not assumed sparse; CPR’s target regime is region II, below the PhaseLift sampling regime and above CPR’s dashed success boundary.Source: §2 · pp. 6–7, Figure 1 · p. 7
- With 32 squared observations, CPRL identifies both nonzero elements in the example, while PhaseLift gives a dense estimate.After a global phase shift, CPRL’s estimate is approximately equal to the true signal.Source: §2 · p. 8, Figure 2 · p. 8
3 Stable Numerical Solutions for Noisy Data
For noisy measurements, the paper models error on the observed squared magnitudes and adapts CPRL to an approximate SDP. It uses a rank-1 approximation when noise prevents the lifted estimate from being exactly rank 1, and reports support recovery in a noisy example.
3 Stable Numerical Solutions for Noisy Data
- The paper places measurement noise on the squared magnitudes, rather than on the linear output before squaring.It says this matches practical phase-retrieval settings where noise enters when intensities are measured.Source: §3 · p. 9
- The approximate CPRL SDP minimizes trace plus an ℓ1 sparsity penalty while keeping the lifted measurements within ℓ2 error ϵ.The estimate is extracted from the lifted matrix using its rank-1 decomposition; the paper says a nonzero ϵ should be assumed to account for machine rounding error.Source: §3 · p. 9
- When noise means the lifted estimate is not exactly rank 1, the paper uses its largest-singular-value rank-1 approximation.The discussion says sparse signals can require fewer measurements in practice when measurements are noise free.Source: §3 · p. 10
- With uniformly distributed measurement noise between −1 and 1, CPRL recovers the two nonzero elements, while PhaseLift gives a dense estimate.The noisy test reuses Example 1’s data with added noise.Source: §3 · p. 10
4 Computational Aspects
The computational section motivates a greedy approximation because standard SDP toolboxes struggle as the lifted matrix grows. GCPRL builds a solution through a greedy procedure and, in the reported simulations, recovers the true sparsity pattern with runtimes several magnitudes faster than standard CVX interior-point methods.
4.1 A Greedy Algorithm
- Because standard SDP toolboxes struggle when the lifted matrix is large, the paper proposes a greedy approximate algorithm for solving CPRL when low signal sparsity is expected.The text presents GCPRL as less computationally heavy than solving the original SDP.Source: §4.1 · pp. 10–11
- The GCPRL simulations use complex unit-Gaussian sampling and randomly chosen nonzero signal entries with values on the complex unit circle.They vary n, N, and k while fixing n/N = 2.Source: §4.1 · p. 11
- Across simulations with n/N = 2, GCPRL always recovers the true sparsity pattern and runs several magnitudes faster than standard CVX interior-point methods.The reported average runtimes use a standard two-core laptop, Matlab, and CVX for the low-dimensional SDP; the simulations use γ = 10 and ϵ = 10^-3.Source: §4.1 · p. 11
5 The Dual
The section presents the CPRL primal SDP, rewrites its constraints through a Lagrangian form, and gives a dual optimization problem. The supplied passages do not state a performance result for this dual formulation.
5 The Dual
- The CPRL primal minimizes trace plus an ℓ1 penalty subject to matching the lifted measurements and positive semidefiniteness.The objective and constraints specify the optimization problem that the section proceeds to rewrite.Source: §5 · p. 11
- The section introduces h(X) to encode the constraints as h(X) = 0 and writes a Lagrangian form with multipliers and matrix variables.The displayed form constrains Y to be positive semidefinite and Z by an infinity-norm bound.Source: §5 · p. 12
- The dual maximizes μᵀb subject to an infinity-norm bound on Z and a positive-semidefinite condition on the residual matrix.The provided dual expression defines Y through I, Z, and the measurement operators.Source: §5 · p. 12
6 Analysis
The analysis develops recovery guarantees for the lifted CPR problem under RIP, RIP-1, and mutual coherence, and identifies Fourier dictionaries as another analysis setting. These guarantees are conditional on properties of the measurement operator and, in the RIP case, one bound is described as impractical.
6 Analysis
- The analysis is organized around RIP, RIP-1, mutual coherence, and a final subsection on Fourier dictionaries.The supplied passages describe the analysis topics but do not state a Fourier-dictionary recovery result.Source: §6 · pp. 12–13
6.1 Analysis Using RIP
- Under RIP with ε < 1, the lifted solution is unique and equals x̄x̄H; CPRL also recovers x̄x̄H when its solution has rank 1.The RIP condition is specified at sparsity 2∥X*∥0 for uniqueness, while the CPRL corollary uses 2∥X̃∥0.Source: §6.1 · pp. 13–14
- Theorem 8’s error bound is described as impractical because it contains both ∥X̃ − X*∥2 and Tr(X̃ − X*).The paper then introduces a weaker bound without supplying its expression in these passages.Source: §6.1 · p. 16
- RIP conditions may be hard to verify for an individual operator, and the analysis notes that B may not satisfy RIP.RIP arguments are more useful for claims about classes of operators; even a particular random Gaussian matrix can be hard to check.Source: §6.1 · p. 17, §6.3 · p. 18
6.2 Analysis Using RIP-1
- If the CPRL solution has rank 1 and B is (ε, 2∥X̃∥0)-RIP-1 with ε < 1, it equals x̄x̄H.The paper states that the corresponding theorems carry over by replacing the 2-norm with the ℓ1-norm.Source: §6.2 · p. 17
6.3 Analysis Using Mutual Coherence
- Under rank 1, CPRL recovers x̄x̄H when ∥X̃∥0 < 0.5(1 + 1/μ(B)).The paper notes that mutual coherence is more tractable than spark, though it may give less tight bounds.Source: §6.3 · p. 18
7 Experiment
Simulations find CPRL pays only a slight sampling penalty relative to full-output CS, with fixed-sparsity recovery needing few additional squared observations as signal dimension grows. A saxophone recording illustrates recovery up to global phase, although the current CVX implementation limits scaling.
7.1 Simulation
- CPRL's SDP needs only slightly higher sampling than CS for the same success rate, despite missing phase; CS receives the complete output y.Figure 4 plots 95% success-rate curves.Source: Figure 4 · p. 19, §7.1 · p. 20
- With sparsity fixed, increasing signal dimension does not significantly increase the squared observations needed for accurate recovery by CPRL or CS.The reported degradation from CS to CPRL when phase is omitted depends largely on signal sparsity.Source: Figure 5 · p. 20, §7.1 · p. 20
- For 10 ≤ n ≤ 2000 and 5 ≤ N ≤ 45, Theorem 13 guarantees X*=X̄ only for rank-one solutions with a single nonzero component; the guarantee is conservative.For n=20 and a two-sparse signal, the simulations indicate that N>25 was needed with high probability for correct recovery.Source: §7.1 · p. 21
7.2 Audio Signals
- The audio experiment models a real recording with sparse Fourier coefficients, mixes its time-domain signal using normalized rows, and observes squared magnitudes.It uses a tenor saxophone recording of one sustained note, with s=32 samples, N=30 measurements, and n=2s Fourier coefficients.Source: §7.2 · p. 22
- CPRL's recovered audio estimate has coefficient phases π apart, so one global rotation makes it real, consistent with recovery up to global phase.Figure 7 compares the retrieved signal with the original audio signal.Source: §7.2 · p. 22, Figure 7 · p. 23
- CPRL captures the signal trend with fewer than s measurements, but the current CVX implementation hits computational and memory limits.The authors say exploiting more precise estimates with fewer measurements requires a higher ambient dimension and a more efficient SDP implementation.Source: §7.2 · p. 22
8 Conclusion and Discussion
The conclusion presents CPRL as an SDP formulation for compressive phase retrieval with squared-magnitude measurements. It also identifies solver speed as a future direction for high-dimensional applications.
8 Conclusion and Discussion
- The proposed compressive phase retrieval method is an SDP formulation for applying compressive sensing when only squared-magnitude measurements are available.Source: §8 · p. 23
- Numerical illustrations are described as state-of-the-art, while speeding up the standard interior-point SDP solver is identified as future work.Faster solvers would facilitate exploring high-dimensional CPR applications in optics, medical imaging, and computer vision.Source: §8 · p. 23
- Figure 8 shows the magnitude of CPRL-retrieved x; the audio estimate is formed as z_est=F_inv x.Source: Figure 8 · p. 24