PaperlayerView exact revision on arXiv

Source-linked AI summary

Asymptotic Analysis of Complex LASSO via Complex Approximate Message Passing (CAMP)

Arian Maleki, Laura Anitori, Zai Yang, Richard Baraniuk

arXiv:1108.0477v2cs.IT

TL;DR

The paper addresses the unknown asymptotic performance of complex-valued LASSO for sparse recovery from undersampled complex measurements. It derives CAMP and a complex state evolution framework, using them to obtain accurate phase-transition and noise-sensitivity formulas for LASSO and CAMP. The results show substantial gains when real and imaginary parts are recovered jointly, including a twofold phase-transition advantage in the high-undersampling regime.

  • Problem

    The precise asymptotic performance of LASSO for complex signals and measurements is not yet known, despite its importance for sparse recovery in the complex domain.

  • Method

    The paper derives complex approximate message passing (CAMP) and extends state evolution to the complex setting for asymptotic analysis of c-LASSO.

  • Results

    The analysis provides accurate formulas for the phase transition and noise sensitivity of c-LASSO and CAMP, with substantial improvement from jointly considering real and imaginary parts.

  • Takeaways & Limitations

    In the very high undersampling regime, the phase transition of CAMP and c-BP is two times higher than that of r-LASSO when real and imaginary parts are grouped.

Abstract

from arXiv · show

Recovering a sparse signal from an undersampled set of random linear measurements is the main problem of interest in compressed sensing. In this paper, we consider the case where both the signal and the measurements are complex. We study the popular reconstruction method of $\ell_1$-regularized least squares or LASSO. While several studies have shown that the LASSO algorithm offers desirable solutions under certain conditions, the precise asymptotic performance of this algorithm in the complex setting is not yet known. In this paper, we extend the approximate message passing (AMP) algorithm to the complex signals and measurements and obtain the complex approximate message passing algorithm (CAMP). We then generalize the state evolution framework recently introduced for the analysis of AMP, to the complex setting. Using the state evolution, we derive accurate formulas for the phase transition and noise sensitivity of both LASSO and CAMP.

I. INTRODUCTION

The paper studies sparse recovery for complex signals and measurements, focusing on complex-valued LASSO and its asymptotic performance. It introduces CAMP and extends state evolution to analyze phase transitions and noise sensitivity, especially when real and imaginary parts are jointly nonzero.

  • Motivation: Complex-valued sparse recovery is relevant because many applications represent signals naturally in the complex domain, with real and imaginary components often zero or non-zero simultaneously.The paper identifies this pairing as prior information that recovery algorithms can exploit.
  • Problem and comparison: Existing analyses of complex LASSO provide performance guarantees but are often inconclusive because of loose constants, motivating an analysis with accurate comparisons.The paper frames the grouping benefit as a central question for complex-valued recovery.
  • Method: CAMP extends AMP to the complex setting and is derived as a fast, efficient algorithm for solving the c-LASSO problem.The extension is technically nontrivial because complex-valued signals and the associated optimization problem introduce features specific to the complex setting.
  • Method: The state evolution framework is extended to the complex setting to predict CAMP performance asymptotically and thereby analyze c-LASSO as N →∞.The framework yields information about phase transitions, noise sensitivity, and least favorable distributions.
  • Model assumptions: The analysis assumes an asymptotic regime with fixed δ = n/N and ρ = k/n, random complex measurements, and paired nonzero real and imaginary coefficients.The paired-coefficient assumption quantifies the improvement available from grouping the components.
  • Problem and comparison: The paper compares c-LASSO with r-LASSO for noise-free and noisy complex measurements, using phase transition and noise sensitivity as performance criteria.The comparison specifically evaluates the benefit of grouping paired real and imaginary components.

2) Noisy measurements:

The paper evaluates noisy complex sparse recovery using noise sensitivity, comparing c-LASSO with r-LASSO and interpreting complex signals as group-sparse structures. State evolution supplies asymptotic predictions, while figures summarize noise-sensitivity contours and comparisons.

  • Noise sensitivity: The noisy model uses complex Gaussian measurement noise, making exact recovery impossible and shifting attention from phase-transition tuning to noise sensitivity.The reconstruction error is characterized through asymptotic mean square error.
  • Noise sensitivity: Noise sensitivity measures how measurement noise degrades reconstruction, and tuning minimizes the worst-case reconstruction error over signal distributions.The comparison declares algorithm A better than B when its optimized noise sensitivity is lower.
  • Analysis framework: CAMP and state evolution provide fast computation and asymptotic performance predictions for complex LASSO, including phase transition and noise sensitivity.The connection between CAMP and c-LASSO makes the asymptotic predictions applicable to c-LASSO as N →∞.
  • Noise-sensitivity contours: As sparsity approaches the phase-transition curve, noise sensitivity grows to infinity.Figure 2 displays contour levels of noise sensitivity together with the phase-transition curve where noise sensitivity is infinite.
  • Comparison framework: For a fixed noise-sensitivity value, c-LASSO’s level set is higher than r-LASSO’s in the contour comparison.Figure 3 uses solid contours for c-LASSO and dotted contours for r-LASSO at noise-sensitivity levels 0.125, 0.5, and 2.
  • Comparison framework: The analysis compares c-LASSO and r-LASSO in noisy and noiseless settings using scenario-specific performance measures.Complex recovery is treated as a group-sparsity case with non-overlapping groups of size two.
  • Related work: Prior group-LASSO analyses showed qualitative benefits but did not quantitatively characterize the difference because of loose constants.This paper instead analyzes mean square error rather than exact recovery or exact support recovery in noisy settings.

III. FORMAL ANALYSIS OF CAMP AND C-LASSO

The formal analysis uses state evolution to track CAMP and c-LASSO asymptotically. It reduces the complex signal dependence to amplitudes, defines fixed-point behavior, and establishes the resulting MSE recursion.

  • III. FORMAL ANALYSIS OF CAMP AND C-LASSO: State evolution predicts asymptotic performance for CAMP and c-LASSO, including phase transition and noise sensitivity.The paper discusses the formal CAMP/c-LASSO connection separately.
  • A. State evolution: The CAMP state is the 5-tuple (m, δ, ρ, σ, G), including normalized MSE, sampling and sparsity ratios, noise level, and nonzero-element distribution.The threshold parameter is also part of the state-evolution analysis.
  • A. State evolution: The signal model uses independent standard Gaussian components and a complex-valued nonzero-element distribution G.G is a probability distribution on C.
  • A. State evolution: The thresholding policy scales with npi(m, σ, δ), and the MSE map Ψ describes the resulting state evolution.The threshold constant τ is tuned according to the paper’s specified schemes.
  • A. State evolution: The recursion updates m_t to m_t+1 and tracks CAMP’s normalized MSE as n, N →∞ with n/N →δ.The next state’s MSE is calculated from the current iteration’s MSE.
  • A. State evolution: A fixed point satisfies Ψ(m*) = m*, and stability is determined from the derivative of Ψ.A unique stable fixed point implies convergence of the state sequence.
  • A. State evolution: The MSE map depends on the amplitude distribution but not on the input signal’s phase distribution.This reduction substantially simplifies state-evolution analysis.

B. Noise-free signal recovery

The state-evolution analysis characterizes CAMP’s noise-free recovery through fixed-point stability and derives its phase transition. In the high-undersampling regime, c-BP and CAMP achieve twice the phase transition of real-valued LASSO.

  • Fixed-point behavior: In Region I, the state-evolution MSE converges to zero, whereas in Region II the zero fixed point is unstable and nonzero initialization does not converge to zero.This separates successful from unsuccessful noise-free recovery according to the MSE map’s fixed-point behavior.
  • Phase transition: ρSE(δ, G, τ) is independent of the distribution G, although the state-evolution function Ψ depends on G.The phase-transition value follows from setting the derivative at zero to one.
  • Phase transition: Optimizing the threshold parameter τ yields the highest CAMP phase transition for a given measurement undersampling ratio δ.The state-evolution framework is used to calculate both the optimal τ and ρSE(δ).
  • High undersampling: As δ → 0, the phase transition of c-BP and CAMP is two times that of r-LASSO, whose asymptotic value is ρR_SE ∼ 1/(2 log(1/δ)).The improvement is attributed to grouping the real and imaginary parts of the signal.
  • Risk of soft thresholding: The soft-thresholding risk r(µ, τ) increases with µ and is concave as a function of µ^2.Its maximum over the specified distribution family is attained by a distribution with mass at zero and at amplitude γ.
  • Risk of soft thresholding: The minimax soft-thresholding risk can be accurately calculated from normal-distribution density and distribution functions.The paper identifies this minimax risk as relevant to the noise-sensitivity analysis.

2) Noise sensitivity of state evolution:

The state-evolution analysis characterizes CAMP’s asymptotic MSE and noise sensitivity, including a unique stable fixed point and an exact match between state-evolution and MSE phase-transition thresholds. It also connects these predictions to asymptotic CAMP and LASSO performance under complex Gaussian measurements.

  • Noise sensitivity of state evolution:: The CAMP state-evolution sequence converges to a unique stable fixed point, so its asymptotic MSE is independent of initialization.The fixed point is identified with fMSE(σ^2, δ, ρ, G, τ).
  • Noise sensitivity of state evolution:: For ρ < ρMSE, Theorem III.11 characterizes the state-evolution noise sensitivity through the condition M♭(ρδ) = δ.The resulting noise-sensitivity function is displayed through contour lines in Figure 2.
  • Noise sensitivity of state evolution:: The worst-case formal MSE is achieved by q = (1 − ϵ)δ0(|X|) + ϵδγ(|X|), independently of σ and τ.This least favorable distribution can guide compressed-sensing system design because performance there guarantees performance at least as good for other input distributions.
  • Noise sensitivity of state evolution:: ρMSE(δ) and ρSE(δ) are exactly equal because both satisfy the same equations after optimizing over τ.The state-evolution threshold is obtained by maximizing over τ, equivalently minimizing the corresponding expression over τ.
  • Noise sensitivity of state evolution:: Under converging complex-Gaussian instances, state evolution predicts both CAMP dynamics and the asymptotic LASSO solution accurately.The CAMP and LASSO theorems express asymptotic behavior using independent complex Gaussian noise and signal variables, with effective variances determined by the state-evolution iterates or fixed point.

E. Discussion

The paper analyzes CAMP convergence and tests whether its asymptotic predictions remain accurate across broader measurement and coefficient ensembles. Simulations support linear convergence, matrix universality, and coefficient-distribution independence.

  • Convergence rate of CAMP: CAMP converges linearly asymptotically, with faster convergence at larger MSE and slower convergence as MSE approaches zero.Theorem III.17 bounds the iterations needed to reach a target accuracy.
  • Convergence rate of CAMP: m200 < 7.1 × 10−10m0 when m=0 < 0.9, demonstrating rapid noise-free error reduction after 200 iterations.For noisy measurements, convergence to the fixed point is faster because the fixed point occurs at larger MSE, where Ψ has a lower derivative.
  • Measurement matrix simulations: Empirical phase transitions of c-LASSO and CAMP closely coincide with the theoretical prediction across tested measurement-matrix ensembles.The experiments use multiple matrix distributions and Monte Carlo recovery trials.

2) Noisy measurements:

The noisy-measurement experiments compare c-LASSO and CAMP across measurement-matrix ensembles using MSE. Their results show similar performance across the tested ensembles, with stronger concentration at larger problem size.

  • Matrix universality: MSE points for c-LASSO and CAMP concentrate along y = x across the tested matrix ensembles, indicating similar performance.The compared ensembles include Gaussian, Rademacher, and Ternary distributions.
  • Matrix universality: For c-LASSO, residual norms are 5.9 × 10−4 and 6 × 10−4 in the Gaussian–Rademacher and Gaussian–Ternary comparisons.These comparisons correspond to the two panels of Figure 6.
  • Matrix universality: For CAMP, residual norms are 9.1 × 10−4 and 9.4 × 10−4 in the Gaussian–Rademacher and Gaussian–Ternary comparisons.These comparisons correspond to the two panels of Figure 7.

B. Proof of Proposition II.1

The proof establishes a complex soft-thresholding result and uses it to support phase-transition independence from the coefficient distribution. The key invariance is that the relevant performance expression does not depend on coefficient phase.

  • MSE comparisons: The proof connects the complex thresholding construction to the MSE calculations used for c-LASSO and CAMP.The surrounding figures compare MSE across Gaussian, Rademacher, and Ternary ensembles.
  • Coefficient ensembles: Phase-transition comparisons across coefficient ensembles agree with Proposition III.4, which states independence from the non-zero coefficient distribution.The comparison is performed at δ = 0.1, with similar behavior reported at other δ values.

C. Proof of Lemma III.2

The proof shows that the state-evolution function is phase-invariant and concave in the MSE variable. These properties support the phase-transition characterization and convergence analysis.

  • Phase independence: The relevant state-evolution expression is independent of the phase of the complex coefficient.The proof establishes this by changing integration variables and using cosine periodicity.
  • Concavity: Lemma V.2 states that Ψ(m) is concave with respect to m.This lemma is then used in the phase-transition proof.
  • Phase independence: Because phase does not affect Ψ, the proof sets the coefficient phase to zero and treats the coefficient as a positive amplitude.This assumption simplifies the concavity calculations.
  • Concavity: ΨX is shown concave in ν2, and Ψ is therefore concave as a convex combination of the conditional functions.The proof establishes the required second-derivative inequality before combining the conditional terms.
  • Phase transition: The phase transition occurs when the derivative condition reaches its boundary, with the critical value obtained by evaluating at m = 1.The threshold parameter τ is selected to maximize the phase transition.

E. Proof of Theorem III.6

The proof shows that the relevant phase-transition parameters vanish as τ grows, then derives their asymptotic behavior using Laplace’s method.

  • δ tends to zero as τ → ∞, establishing the regime needed to analyze the phase transition as δ → 0.
  • Laplace’s method is applied to calculate the leading terms of ρ and δ as τ → ∞.
  • Substituting the leading terms into the formulas for ρ and δ completes the asymptotic derivation.

F. Proof of Lemma III.7

The proof establishes that the complex soft-thresholding risk is independent of phase, increases with amplitude, and is concave in the squared amplitude.

  • The phase θ does not affect the risk function, so the proof sets θ to zero.
  • The risk of complex soft thresholding is an increasing function of µ.
  • The function is concave with respect to µ^2 because its next derivative with respect to µ^2 is negative.

G. Proof of Proposition III.8

The proof characterizes the least favorable distribution for the risk analysis and connects this result to the paper’s asymptotic conclusions for complex recovery algorithms.

  • The main challenge is to characterize the relevant quantity stated in the theorem.
  • The risk function is phase-independent, and the signal-amplitude distribution is represented using a point mass at zero and an absolutely continuous component.
  • The sequence G_m(µ) = δ_m(µ), beginning at m = 1, is the least favorable sequence of distributions.
  • The proof uses Jensen’s inequality, risk monotonicity, and monotone convergence to establish the proposition.
  • The paper reports accurate asymptotic analyses of c-LASSO and CAMP, including simple expressions for their noise sensitivity and phase transition.
Loading 1108.0477v2…