PaperlayerView exact revision on arXiv

Source-linked AI summary

Compressed Sensing and Redundant Dictionaries

Holger Rauhut, Karin Schnass, Pierre Vandergheynst

arXiv:math/0701131v2math.PRcs.IT

TL;DR

Compressed sensing lacked a corresponding framework for signals sparse in redundant dictionaries rather than orthonormal bases. The paper analyzes random measurement matrices composed with deterministic dictionaries, establishes recovery-relevant isometry properties, and studies Basis Pursuit and thresholding, with numerical comparisons across methods.

  • Problem

    Compressed-sensing theory had primarily addressed signals sparse in orthonormal bases, motivating recovery from few measurements for signals sparse in redundant dictionaries.

  • Method

    The paper studies Ψ = AΦ, combining a random measurement matrix A with a deterministic redundant dictionary Φ, and analyzes Basis Pursuit and thresholding.

  • Results

    The composed matrix has small restricted isometry constants with high probability, supporting Basis Pursuit recovery from few random measurements; thresholding also receives high-probability recovery conditions.

  • Takeaways & Limitations

    Compressed sensing can be applied to signals sparse in redundant dictionaries, with Basis Pursuit and thresholding providing supported reconstruction approaches.

  • Takeaways & Limitations

    Thresholding requires samples depending on the largest-to-smallest coefficient ratio and is guaranteed only for a given signal rather than uniformly for all signals.

Abstract

from arXiv · show

This article extends the concept of compressed sensing to signals that are not sparse in an orthonormal basis but rather in a redundant dictionary. It is shown that a matrix, which is a composition of a random matrix of certain type and a deterministic dictionary, has small restricted isometry constants. Thus, signals that are sparse with respect to the dictionary can be recovered via Basis Pursuit from a small number of random measurements. Further, thresholding is investigated as recovery algorithm for compressed sensing and conditions are provided that guarantee reconstruction with high probability. The different schemes are compared by numerical experiments.

1 Introduction

Compressed sensing seeks stable recovery from few random measurements, but the established theory primarily treated signals sparse in an orthonormal basis. This paper extends the framework to redundant dictionaries by studying random measurement matrices composed with deterministic dictionaries and comparing Basis Pursuit, thresholding, and OMP.

  • Motivation: Compressed sensing aims to reconstruct sparse signals from a small number of random measurements when collecting all coordinates is impractical.The decoder is assumed to have sufficient resources for reconstruction.
  • Scope: Prior compressed-sensing theory focused on signals with very sparse representations in an orthonormal basis.The paper identifies extension to redundant dictionaries as its central research question.
  • Motivation: Redundant dictionaries broaden the class of modelable signals, including examples such as two orthonormal bases and damped sinusoids for NMR spectroscopy.This added flexibility motivates extending compressed sensing beyond a single orthonormal basis.
  • Recovery methods: Basis Pursuit replaces computationally infeasible ℓ0 minimization with an ℓ1-based convex relaxation solvable by mathematical programming.The ℓ0 formulation is impractical because its solution is NP-hard.
  • Recovery theory: Uniform uncertainty principles require small restricted isometry constants, meaning relevant submatrices are well-conditioned enough to support recovery guarantees.For BP, the cited theorem gives exact recovery in the noiseless case under its stated isometry condition.
  • Redundant dictionaries: For a redundant dictionary Φ ∈ R^d×K with K > d, the signal is modeled as y = Φx with a coefficient vector x having few nonzero components.Measurements take the form s = Ay = AΦx, so sparse coefficients in Φ drive reconstruction.
  • Approach: The paper studies whether random A can make the composed matrix Ψ = AΦ suitable for recovery under conditions on Φ, n, and S.The target is successful recovery with high probability for signals sparse in the fixed dictionary.
  • Contributions: The paper analyzes random-dictionary compositions for BP, investigates thresholding, and compares BP, thresholding, and OMP through numerical simulations.The authors had not theoretically analyzed OMP for compressed sensing but included simulations for all three approaches.

2 Isometry Constants for AΦ

The paper analyzes how random measurement matrices affect the restricted isometry constants of a deterministic redundant dictionary. Concentration arguments yield probabilistic bounds that support uniform Basis Pursuit recovery, with coherence-based estimates and ensemble-specific examples.

  • Method: The analysis uses concentration of measure to study restricted isometry constants for composed matrices Ψ = AΦ.The approach is inspired by proofs of the Johnson–Lindenstrauss lemma and applies concentration inequalities to random matrix–dictionary products.
  • Global bounds: Theorem 2.2 gives a high-probability restricted-isometry bound for Ψ = AΦ when A satisfies the stated concentration condition and the measurement count meets condition (2.8).The result holds with probability at least 1 − e^−t and recovers the orthonormal-basis case when δ(Φ) = 0.
  • Local bounds: For a dictionary sub-dictionary ΦΛ, the local isometry bound combines the dictionary distortion with a random-matrix term as δΛ(Φ) + δ + δΛ(Φ)δ.The proof uses an ε-covering of the unit sphere, concentration bounds, and a union bound.
  • Dictionary dependence: Coherence µ and Babel function µ1(k) provide crude bounds on the dictionary restricted isometry constants, which can then be inserted into the composed-matrix estimate.This connects dictionary geometry to the number of measurements required for recovery.
  • Measurement bounds: For Gaussian and Bernoulli ensembles, Corollary 2.4 gives n ≥ C1(S log(K/S) + C2 + t), with C1 ≤ 356.18 and C2 ≈ 5.57.The resulting constants are explicitly stated, though the paper notes they are probably not optimal.
  • Recovery implications: Combining the estimates with the Basis Pursuit recovery theorem yields uniform recovery of all signals sparse in a redundant dictionary using one suitable random measurement matrix.The Dirac–DCT example illustrates the resulting sample estimates for a union of two orthonormal bases.

3 Recovery by Thresholding

This section establishes high-probability thresholding recovery from random measurements for signals sparse in a redundant dictionary. The guarantees depend on dictionary structure, coefficient balance, and whether recovery is required for one signal or uniformly for all signals.

  • 3 Recovery by Thresholding: Thresholding relies on stability of signal–atom inner products after multiplication by a random matrix.The analysis begins by controlling how random measurements preserve the comparisons used by thresholding.
  • 3 Recovery by Thresholding: With probability exceeding 1 −e−t, thresholding reconstructs the support and signal from s = Ay = AΦx under the theorem’s measurement condition.The result assumes a normalized signal whose support is recoverable by thresholding with margin ε.
  • 3 Recovery by Thresholding: The thresholding success probability is obtained by combining bounds for good components falling below the threshold and bad components exceeding it.The proof estimates both failure events and solves for n to achieve probability at least 1 −e−t.
  • 3 Recovery by Thresholding: For a signal y = ΦΛx with |Λ| = S, recovery depends on the minimum coefficient magnitude |xmin| and dictionary-dependent conditions.The corollary explicitly uses |xmin| = mini∈Λ |xi| and a sufficient recovery condition for thresholding.
  • 3 Recovery by Thresholding: The required sample count can be linear in sparsity S, but thresholding additionally depends on the largest-to-smallest coefficient ratio and is not uniform over all sparse signals.For Gaussian measurements with an ONB, some signal may still require n quadratic in S for thresholding to succeed uniformly.
  • 3 Recovery by Thresholding: For the Dirac–DCT dictionary with balanced coefficients and S ≤2p−2, the estimate is n ≥6C3 S(log(2)(2p + 2) + t), versus n ≥C3 S(log(2)(2p + 1) + t) when using one ONB.The comparison illustrates the additional measurement cost associated with the redundant dictionary.
  • 3 Recovery by Thresholding: An analogous OMP result was not obtained because of stochastic dependency issues.The authors state that this analysis remained difficult and incomplete.

4 Numerical Simulations

The simulations compare BP, thresholding, and OMP using random Gaussian measurements for Dirac–DCT and canonical dictionaries. They follow the theoretical pattern that redundant dictionaries require more measurements, while thresholding performs weakest and BP’s advantage over OMP is modest.

  • 4 Numerical Simulations: The experiments use the Dirac–DCT dictionary in dimension d = 256, with coherence µ = 1/128 ≈0.0884 and six Gaussian measurement matrices.Measurement counts range from 64 to 224 in steps of 32.
  • 4 Numerical Simulations: Support sizes vary across randomly generated signals, and recovery is evaluated by counting correct-support reconstructions for BP, thresholding, and OMP.BP and OMP use normalized Gaussian coefficients, while thresholding uses unit-magnitude coefficients with random signs.
  • 4 Numerical Simulations: The same experimental setup is repeated with the canonical Dirac basis for comparison, with results shown in Figures 1, 2, and 3.Figure 1 covers BP, Figure 2 thresholding, and Figure 3 OMP as functions of support and sample sizes.
  • 4 Numerical Simulations: Recovery requires more measurements when the sparsity-inducing dictionary is not an orthonormal basis.This agrees with the theoretical predictions.
  • 4 Numerical Simulations: Thresholding gives the weakest results, while BP improves over OMP without a significant performance advantage.The comparison is notable because BP is substantially more computationally intensive than OMP in practice.

5 Conclusions & Future Work

The paper extends compressed sensing to redundant dictionaries and establishes recovery for Basis Pursuit and thresholding, while identifying unresolved questions for OMP, Fourier matrices, and dictionary incoherence.

  • Conclusions: Compressed sensing applies to signals sparse in redundant dictionaries, not only orthonormal bases.The paper’s central conclusion broadens the signal classes addressed by compressed sensing.
  • Conclusions: Basis Pursuit and thresholding can reconstruct redundant-dictionary-sparse signals from small numbers of random measurements with high probability.The conclusion states this stability result for both recovery methods.
  • Conclusions: Thresholding is faster and easier to implement than Basis Pursuit but requires sample counts depending on the largest-to-smallest coefficient ratio.Its guarantee is signal-specific with high probability rather than uniform over all signals.
  • Conclusions: Orthogonal Matching Pursuit appears numerically effective and faster than Basis Pursuit, with no apparent dependence on the coefficient ratio.The paper reports this as numerical evidence rather than a comparable recovery theorem.
  • Future Work: Future work includes proving an OMP recovery theorem, studying random Fourier matrices, and relaxing the dictionary incoherence assumption.The authors note that stochastic dependence of updated OMP residuals complicates the proof.

A Proof of Lemma 3.1

The proof establishes a concentration bound for a Gaussian random-matrix expression by controlling its moments and then applying an independent-sum inequality; the Bernoulli case follows analogously.

  • Proof strategy: The proof invokes Bennett’s inequality, also called Bernstein’s inequality, as its main independent-sum tail bound.This inequality is used after establishing the required moment estimate.
  • Proof strategy: Theorem A.1 supplies a tail estimate for independent zero-mean random variables satisfying moment bounds with constants M and v_i.The theorem uses v = Σ_i v_i.
  • Gaussian case: Lemma 3.1 is reduced to bounding a Gaussian chaos variable Z of order 2 and the moments of independent copies of it.The proof defines Z from independent standard Gaussians, shows EZ = 0, and derives moment bounds before applying Theorem A.1.
  • Gaussian case: The second moment of Z is computed using independence of the Gaussian variables, completing the moment-control step.The argument explicitly determines E|Z|^2 and uses the norm assumptions on x and y.
  • Bernoulli case: For Bernoulli random matrices, the proof replaces Gaussian variables with ±1 Bernoulli variables and retains the final bound.Because g_k^2 = 1, the last term in the corresponding estimate vanishes.
Loading math/0701131v2…