PaperlayerView exact revision on arXiv

Source-linked AI summary

Recovering Compressively Sampled Signals Using Partial Support Information

Michael P. Friedlander, Hassan Mansour, Rayan Saab, Ozgur Yilmaz

arXiv:1010.4612v2cs.ITeess.SYmath.OC

TL;DR

The paper asks how compressed sensing recovery can use partial support information without relying on fully known support. It analyzes weighted ℓ1 minimization and shows that sufficiently accurate support estimates yield stable, robust recovery under weaker conditions and smaller error bounds.

  • Problem

    Standard ℓ1 minimization does not incorporate prior support information, motivating recovery methods that can exploit partial support estimates.

  • Method

    The paper studies weighted ℓ1 minimization with weights determined by an estimated support, including nonzero weights and explicit support-estimate accuracy.

  • Results

    When the support estimate is at least 50% accurate, weighted ℓ1 minimization outperforms standard ℓ1 in accuracy, stability, and robustness under weaker sufficient conditions and with smaller error bounds.

  • Takeaways & Limitations

    Partial support information can improve compressed sensing recovery guarantees and reconstruction-error bounds when incorporated through weighted ℓ1 minimization.

Abstract

from arXiv · show

In this paper we study recovery conditions of weighted $\ell_1$ minimization for signal reconstruction from compressed sensing measurements when partial support information is available. We show that if at least 50% of the (partial) support information is accurate, then weighted $\ell_1$ minimization is stable and robust under weaker conditions than the analogous conditions for standard $\ell_1$ minimization. Moreover, weighted $\ell_1$ minimization provides better bounds on the reconstruction error in terms of the measurement noise and the compressibility of the signal to be recovered. We illustrate our results with extensive numerical experiments on synthetic data and real audio and video signals.

I. INTRODUCTION

Compressed sensing enables recovery from far fewer measurements than the signal dimension, but standard recovery does not use prior support information. This paper studies weighted ℓ1 recovery that exploits such information while keeping measurements non-adaptive.

  • Motivation: Compressed sensing can recover sparse or approximately sparse signals from n ≪ N measurements.Many audio, image, video, and radio-frequency signals are sparse or approximately sparse in suitable transform domains.
  • Motivation: Standard ℓ1 minimization provides stable and robust recovery under suitable measurement conditions but does not incorporate prior support information.Its recovery guarantees apply to inaccurate measurements y = Ax + e with bounded noise.
  • Prior support information: Prior support estimates can be obtained from temporal correlation in video and audio or from coefficients likely to carry most signal energy.Low-frequency DCT or wavelet coefficients are especially likely to be nonzero for images.
  • Prior support information: Weighted ℓ1 minimization incorporates prior support information by assigning lower weights to entries expected to be large.Earlier approaches often used zero weights on the estimated support; this paper considers a broader weighted formulation.
  • Previous work: Earlier studies established weighted recovery approaches for partially known support, including noisy, compressible, probabilistic, and geometric formulations.The introduction positions the paper within prior work on modified compressed sensing and related weighted ℓ1 methods.

C. Contributions

The paper develops weighted ℓ1 recovery guarantees for partial support estimates, allowing nonzero weights and accounting for support-estimate accuracy. It shows improved recovery behavior when the estimate is sufficiently accurate and evaluates the approach numerically.

  • Contributions: The method assigns weight ω ∈ [0, 1] on an estimated support and weight 1 elsewhere.Unlike approaches using zero weights, the analysis allows ω to be nonzero.
  • Contributions: The paper derives stability and robustness guarantees for weighted ℓ1 minimization that generalize standard ℓ1 recovery results.The guarantees explicitly account for the accuracy of the partial support estimate.
  • Contributions: At least 50% support-estimate accuracy is sufficient for weighted ℓ1 minimization to outperform standard ℓ1 in accuracy, stability, and robustness.The comparison concerns the corresponding recovery behavior under the paper’s sufficient conditions.
  • Experiments: Numerical experiments cover synthetic signals and audio and video signals.The paper compares theoretical results with standard ℓ1 recovery and prior methods.

II. COMPRESSED SENSING OVERVIEW

The compressed sensing overview formulates noisy measurements of a compressible signal and reviews standard ℓ1 recovery guarantees. Under suitable matrix conditions, the reconstruction error scales with measurement noise and signal compressibility, with exact recovery in the sparse noiseless case.

  • Measurement model: The signal is modeled through noisy measurements y = Ax + e with a known n × N matrix and bounded noise ∥e∥2 ≤ ϵ.The setting allows n ≪ N, so measurements can be much fewer than the ambient dimension.
  • Standard ℓ1 recovery: Standard compressed sensing recovers x by solving an ℓ1 minimization problem when the measurement matrix satisfies the restricted isometry property.The restricted isometry constant δk quantifies the relevant matrix condition.
  • Recovery guarantee: For compressible signals, the standard ℓ1 reconstruction error scales with measurement noise and the signal’s best k-term approximation error.The theorem provides explicit constants under a sufficient condition on the measurement matrix.
  • Recovery guarantee: When x = xk and the measurements are noise-free, the standard ℓ1 guarantee yields exact recovery.This is the sparse noiseless specialization of the overview theorem.

III. COMPRESSED SENSING WITH PARTIAL SUPPORT ESTIMATION

The paper develops weighted ℓ1 recovery guarantees for noisy compressive measurements when only partial support information is available. Its guarantees improve on standard ℓ1 and prior support-based conditions when the support estimate is sufficiently accurate, while nonzero weights can help when estimates are inaccurate.

  • Main result: Weighted ℓ1 minimization stably and robustly recovers sparse and compressible signals from noisy measurements with partially inaccurate support information.Theorem 3 uses a weighted objective parameterized by the support-estimate size and accuracy, with error bounds depending on measurement noise and signal compressibility.
  • Main result: More than 50% support-estimate accuracy makes weighted ℓ1 outperform standard ℓ1 in sufficient conditions and stability constants.The comparison gives C′0 < C0 and C′1 < C1 if and only if α > 0.5; at α = 0.5, the constants and sufficient conditions coincide.
  • Condition and error comparisons: As support accuracy α increases, the RIP requirement weakens and the associated recovery-error constants decrease.For a = 3, 70% accuracy with ω = 0.2 permits ˆδ(ω) < 0.763, compared with ˆδ(1) < 0.5 for standard ℓ1; the constants C′0 and C′1 also decrease with α.
  • Condition and error comparisons: Nonzero weights improve reconstruction quality especially for noisy and compressible signals, including some cases where support accuracy exceeds 50%.Using nonzero weights also adds robustness when α < 0.5, whereas zero weights perform worst for highly inaccurate support estimates.
  • Scope: Choosing the weight optimally is outside the paper’s scope, although the experiments show that the best choice depends on support-estimate accuracy and signal conditions.Zero weights give the smallest error-bound constants when α > 0.5, but the worst recovery performance when α < 0.5.
  • Comparison with prior conditions: The proposed sufficient condition guarantees recovery with less accurate prior support information than Vaswani and Lu’s condition under the same measurement setting.For Gaussian measurement matrices, the comparison uses n/N = 0.5 and evaluates the admissible unknown-support ratio u/k; across several aspect ratios, the proposed condition can guarantee recovery where the prior condition does not.

IV. NUMERICAL EXAMPLES

The experiments compare standard and weighted ℓ1 minimization for sparse and compressible signals with partial, potentially inaccurate support information. They use synthetic signals and evaluate recovery numerically, including phase-diagram comparisons based on restricted-isometry bounds.

  • The study examines recovery when the available partial support information may be inaccurate.
  • The experiments compare standard and weighted ℓ1 minimization for synthetically generated sparse and compressible signals with partial prior support information.SPGL1 is used to solve both optimization problems.
  • Figure 3 compares phase diagrams for Gaussian measurement matrices satisfying sufficient recovery conditions under standard ℓ1 and weighted ℓ1 with ω = 0.Weighted cases use α = 0.3, 0.6, and 0.8; curves use upper bounds on restricted isometry constants derived in [15].

A. The sparse case

For sparse signals, recovery performance is evaluated over measurement counts, support-estimate sizes, support accuracy, and weight choices. The experiments show a strong dependence on support accuracy, with different preferred weights above and below α = 0.5.

  • Experimental setup: N = 500 and k = 40 are fixed while Gaussian measurement matrices vary in dimension n from 80 to 200.Noisy experiments use ϵ = ∥x∥2/20.
  • Experimental setup: 20-experiment average SNR is measured in dB for weighted ℓ1 recovery in both noise-free and noisy cases.Recovery uses a support estimate of size |eT| = 40, corresponding to ρ = 1.
  • Results: α ≥ 0.5: ω = 0 achieves the best recovery, while ω = 1 produces the worst SNR in the noise-free experiments.
  • Results: α < 0.5: recovery performance shifts toward larger ω values in severely underdetermined cases with small n.
  • Results: Larger support estimates favor better reconstruction, but recovery is more sensitive to support accuracy α than to estimate size relative to k.
  • Interpretation: Intermediate weights can yield the best recovery when the measurement matrix does not support full recovery of a k-sparse signal.The paper notes that a complete mathematical analysis of the dependencies among ω, ˆk, ˆα, and theorem parameters is beyond scope.

B. The compressible case

The compressible-signal experiments use power-law coefficient decay and examine recovered SNR as support-estimate size varies. Across tested decay rates and sparsity levels, intermediate weighting gives the best qualitative recovery behavior.

  • Experimental setup: The compressible signal coefficients decay as j−p with p > 1.The experiments use p = 1.1, then repeat with p = 1.5 and p = 2.
  • Experimental setup: For p = 1.1, recovered SNR is evaluated against support-estimate size using the best 40-term approximation.
  • Results: ω ≈ 0.5 produces the best average recovery for the p = 1.1 experiment.The paper attributes this behavior to balancing error-bound constants against off-support component norms.
  • Results: The same qualitative behavior appears for p = 1.5 with k = 20 and p = 2 with k = 10.

V. STYLIZED APPLICATIONS

The paper applies standard and weighted ℓ1 minimization to real video and audio signals that are compressively sampled. Figure 5 evaluates weighted recovery while varying the support-estimate size and support accuracy.

  • Standard and weighted ℓ1 minimization are applied to recover real video and audio signals that are compressively sampled.
  • Figure 5 measures average recovered SNR while varying support-estimate size ρ for α = 0.7, 0.5, and 0.3.The experiment fixes k = 40, N = 500, and n = 100.

A. Recovery of video signals

The paper applies weighted ℓ1 minimization to video compressed sensing by exploiting support information from preceding frames. In Foreman experiments, this approach improves reconstruction quality and can reduce measurements per frame.

  • Adjacent video frames have spatial-transform coefficients that are nonzero in roughly the same locations, enabling partial support estimation.
  • Each video frame is measured using a random restriction matrix composed with an orthonormal spatial sparsifying basis.For frame j, the measurement operator is A_j = R_jD, with R_j selecting n_j pixels from N.
  • Weighted ℓ1 recovery estimates each subsequent frame’s support from energy-contributing coefficients in the previous two recovered frames.The estimate is the union of selected locations from those frames.
  • 1 dB average PSNR improvement is obtained with ω = 0.5 versus standard ℓ1 using the same number of measurements.Weighted ℓ1 also outperforms standard ℓ1 when standard recovery uses n_j = n_0 and weighted recovery uses n_j = n_0/2.2.

B. Recovery of audio signals

The paper evaluates weighted ℓ1 minimization for compressively sampled speech by exploiting frequency structure and support persistence across adjacent blocks. Two speech signals are reconstructed from randomly retained samples while varying the weight parameter.

  • The audio model assumes DCT-domain compressibility, slowly changing supports of large adjacent-block coefficients, and large low-frequency coefficients.
  • For each block, the support estimate combines frequencies up to 4 kHz with the largest n_j/16 recovered coefficients from the previous block.The previous-block contribution is empty for the first block.
  • Experiments use one male and one female speech signal with N = 2048 and ω ∈ {0, 1/6, 2/6, . . . , 1}.Performance is illustrated using reconstructed-signal SNR.

VI. PROOF OF THEOREM 3

The proof of Theorem 3 derives weighted error bounds by decomposing the support and estimated-support sets, applying weighted optimality and feasibility, and controlling tail coefficients through sorted partitions.

  • The estimated support is partitioned into its overlap with T_0 and its complementary portion, with α + β = 1.Figure 11 illustrates these sets and their relationship to the weight vector w.
  • Weighted optimality gives an ℓ1 inequality comparing the weighted estimated-support and complement terms of x + h with those of x.
  • The proof expands the weighted norm over intersections of the estimated support and T_0, then rearranges terms using forward and reverse triangle inequalities.
  • The complement of T_0 is partitioned into disjoint sets T_j containing successively sorted groups of large coefficients of h_{T_0^c}.T_1 contains the largest ak coefficients, T_2 the second largest group, and so on.
  • Feasibility of x* and x yields ||Ah||_2 ≤ 2ε, which is combined with the preceding norm inequalities to bound the reconstruction error.The argument also requires a positive denominator in the final bound.
Loading 1010.4612v2…