Source-linked AI summary
A probabilistic and RIPless theory of compressed sensing
Emmanuel J. Candes, Yaniv Plan
TL;DR
The paper addresses recovery of nearly sparse signals from few noisy measurements when RIP-based analysis is unavailable or difficult. It models sensing vectors as independent draws from a distribution satisfying isotropy and incoherence, and proves RIPless recovery guarantees. The main conclusion is that accurate recovery can require about s log n noisy Fourier measurements, with broader guarantees scaling according to coherence.
Problem
The paper asks whether nearly sparse signals can be recovered from about s log n Fourier coefficients despite noise, when RIP is unavailable at that sampling rate.
Method
The paper samples sensing vectors independently from a distribution F and analyzes convex ℓ1 recovery using isotropy, incoherence, and weaker-than-RIP proof tools.
Results
Accurate recovery is possible from about s log n noisy DFT coefficients, and the framework supports stable recovery without requiring RIP or a random signal model.
Takeaways & Limitations
The theory provides a simple general framework covering standard compressive-sensing models while reducing the theoretically required measurements in settings such as Fourier sampling.
Takeaways & Limitations
Universal recovery for all signals simultaneously would require RIP or a closely related condition, unlike the fixed-signal guarantees studied here.
Abstract
from arXiv · showhide
This paper introduces a simple and very general theory of compressive sensing. In this theory, the sensing mechanism simply selects sensing vectors independently at random from a probability distribution F; it includes all models - e.g. Gaussian, frequency measurements - discussed in the literature, but also provides a framework for new measurement strategies as well. We prove that if the probability distribution F obeys a simple incoherence property and an isotropy property, one can faithfully recover approximately sparse signals from a minimal number of noisy measurements. The novelty is that our recovery results do not require the restricted isometry property (RIP) - they make use of a much weaker notion - or a random model for the signal. As an example, the paper shows that a signal with s nonzero entries can be faithfully recovered from about s log n Fourier coefficients that are contaminated with noise.
1 Introduction
The paper develops a general compressive-sensing framework based on random sensing vectors satisfying isotropy and incoherence, targeting approximately sparse signals with noisy measurements. It establishes RIPless recovery at near-minimal sampling rates, including about s log n Fourier measurements.
- Motivation: Compressive sensing can recover sufficiently sparse signals from far fewer data bits than classical acquisition methods.The framework treats sparsity as information content and uses nonadaptive random Fourier sampling with ℓ1 minimization.
- Open questions: The paper asks whether nearly sparse signals can be recovered from about s log n Fourier coefficients, including when measurements contain noise.These questions address realistic signals and imperfect measurements, for which exact sparsity and noiseless data are unavailable.
- RIPless theory: RIP may not apply at the target sampling rate because it is unknown whether it holds when m is on the order of s log n.The paper therefore develops recovery guarantees without requiring RIP or a random signal model.
- Recovery guarantees: The framework claims stable recovery from a minimal number of samples, with approximately s-sparse signals requiring an added approximation-error term.For noisy Fourier measurements, the resulting guarantees are described as optimal up to logarithmic factors.
- General framework: Random sensing vectors are independently sampled from a distribution F that satisfies isotropy and incoherence properties.The framework includes Fourier sampling and is intended to encompass standard and new measurement models.
- Recovery guarantees: For a fixed s-sparse signal, ℓ1 minimization can recover accurately from about µ(F)s log n noisy measurements under the stated sensing assumptions.The required sample count depends on the coherence parameter µ(F); when µ(F)=O(1), this becomes about s log n.
1.3 Examples of incoherent measurements
The paper characterizes useful sensing distributions through isotropy and incoherence, illustrates the framework across measurement models, and proves high-probability ℓ1 recovery guarantees. Coherence determines the minimal sampling rate, while isotropy prevents rank-deficient sensing behavior.
- Distribution properties: Isotropy prevents unrecoverable directions by ensuring the sensing distribution is not rank deficient in expectation.With enough measurements, the normalized Gram matrix approaches the identity and the sensing matrix becomes well conditioned.
- Distribution properties: Independent mean-zero, unit-variance components produce isotropic sensing vectors, and light-tailed components yield incoherence.The Gaussian ensemble is a special case with µ(F)=6 log n.
- Measurement examples: Subsampled orthogonal transforms, including DFT and Hadamard models, provide isotropic measurements whose coherence depends on the largest matrix entry.For Hadamard or complex Fourier matrices, µ(F)=1.
- Measurement examples: Random convolution is isotropic and incoherent when the convolution kernel has equal-magnitude Fourier components and is sufficiently spread out.The construction extends to higher-dimensional spatial convolutions.
- Measurement examples: Continuous-frequency frame sampling is isotropic with µ(F)=1 and models settings such as non-equispaced MRI frequency samples.Swapping time and frequency gives random time-point sampling of nearly sparse trigonometric polynomials.
- Recovery theorem: For noiseless data, an arbitrary fixed s-sparse signal is the unique ℓ1 minimizer with high probability under the incoherent sampling theorem.The sample requirement scales with coherence, sparsity, and log n, and the bound is described as information-theoretically sharp.
1.6 Main results
The paper develops a general noisy-recovery framework using weak conditions instead of RIP, covering arbitrary fixed signals and multiple sensing ensembles. Its guarantees reach near-minimal measurement rates, while universal recovery remains outside the framework.
- Noisy recovery: m ≥ Cβ · µ(F) · s̄ · log n measurements suffice for recovery of an arbitrary fixed vector under the stated sensing and noise conditions.The theorem assumes Gaussian noise, while also allowing other noise models satisfying ∥A*z∥ℓ∞ ≤ λn.
- Framework: Robust error bounds require neither a random signal model nor RIP, RIP-1, restricted eigenvalue, or compatibility conditions.The guarantees concern an arbitrary fixed sparse signal with high probability over the sensing mechanism, rather than all signals simultaneously.
- Measurement complexity: The theory bridges the region where RIP holds and the minimum-measurement region for perfect recovery of exactly sparse signals from noisy data.For partial DFT matrices, prior RIP guarantees require C · s · log^4 n measurements, whereas the paper identifies a rate on the order of µ(F) · s · log n.
- Measurement complexity: µ(F) · s · log n measurements are information-theoretically necessary for perfect recovery of some sparse signals, so the measurement rate is sharp up to constants.The paper states that substantially fewer measurements cannot provide a similar recovery guarantee.
- Scope and trade-offs: For Gaussian measurements, the general theory initially loses a logarithmic factor, requiring s log^2 n rather than s log n/s samples, although specialization recovers a near-optimal bound.The paper presents this loss as the price of a simple theory covering a wide range of sensing strategies.
- Framework: The framework applies to standard compressive-sensing models and some new sensing strategies, including Fourier measurements and matrices formed by sampling rows from orthogonal matrices.Its proofs are designed as a simple, general theory rather than a model-specific analysis.
2 Fundamental Estimates
The paper builds recovery proofs from local isometry, low-distortion, and off-support incoherence estimates, supplemented by a weaker RIP for noisy, nonsparse signals. These conditions are weaker or more targeted than requiring the full RIP and are established using Bernstein-type concentration tools.
- Core estimates: The proof uses estimates E1–E4 for noiseless recovery, while combining them with the weak RIP yields stability and robustness.The estimates include local isometry, low-distortion, off-support incoherence, and uniform off-support incoherence.
- Concentration tools: Matrix Bernstein inequalities establish local isometry for a fixed support, using independence and bounded self-adjoint random matrices.The variance calculation is controlled by the coherence parameter and support size.
- Core estimates: Low-distortion preserves the norm of an arbitrary fixed sparse vector under slightly weaker requirements than uniform near-isometry on a support.Its proof applies a vector Bernstein inequality.
- Core estimates: Off-support incoherence controls correlations between columns outside the support and measurements of supported vectors.Bernstein inequalities and a union bound provide the required control.
- Weak RIP: The weak RIP requires submatrices formed from a fixed support and a small additional set of columns to remain well conditioned.It combines local conditioning with a restricted-isometry-type requirement and is proved using majorizing measures.
- Comparison: E1–E4 can offer better constants or weaker requirements than the weak RIP, while relying on simpler standard concentration theorems.The paper presents them as independently useful tools despite their implication by the weak RIP.
3 Noiseless and Sparse Recovery
Noiseless recovery is proved by constructing an inexact dual certificate in the row space of the sensing matrix. The golfing scheme builds this certificate from independent row blocks, yielding ℓ1 recovery with about µ(F)s log n measurements.
- Dual certificates: A dual certificate in the row space of A makes an s-sparse feasible vector the unique ℓ1 minimizer.The certificate conditions control the support sign pattern and the off-support infinity norm.
- Dual certificates: The inexact duality lemma gives the same uniqueness conclusion under approximate certificate conditions.The proof uses feasibility, an ℓ1 subgradient inequality, and full rank of A_T.
- Certificate construction: With probability at least 1 − e^(-β) − 1/n, the constructed vector satisfies the inexact dual certificate conditions under the theorem’s hypotheses.Extra row batches are sampled so that failed batches can be discarded while enough working batches remain.
- Recovery guarantee: m ≥ µ(F)s(19 log n + 2) ensures the local-isometry and uniform-incoherence conditions jointly with probability at least 1 − 3/n.These conditions, together with the certificate lemma, imply noiseless recovery.
- Golfing scheme: The golfing scheme partitions A into independent row blocks and iteratively constructs a row-space certificate.The residual on the support decreases geometrically while the off-support components remain controlled.
- Recovery guarantee: The certificate construction ultimately requires m ≥ C(1 + β)µ(F)s log n for the desired high-probability guarantee.The total sample count aggregates the row-block requirements.
4 General Signal Recovery from Noisy Data
The paper extends recovery from exact sparse signals to arbitrary signals under noisy measurements using LASSO and the Dantzig selector. A weak RIP, noise-correlation control, and error lemmas yield bounds that include approximation error.
- Noise model: The noisy analysis assumes Gaussian white noise for the proof but states that the result also holds for other noise distributions satisfying a noise-correlation bound.The Dantzig selector uses the constraint ∥A∗(y − A x̄)∥ℓ∞ ≤ 4λ_n.
- Recovery conditions: The weak RIP implies both the needed restricted isometry condition and a column-norm bound used to control the noise term.Together with the noise-correlation estimate, these conditions hold with probability at least 1 − 4/n − 6e^(-β).
- LASSO analysis: The LASSO proof first establishes a tube constraint on the error h and then bounds its support and off-support components using the weak RIP.The argument partitions the off-support indices into blocks according to the magnitudes of h.
- LASSO analysis: The error analysis converts feasibility and ℓ1 optimality into inequalities involving measurement residuals, approximation error, and the inexact dual certificate.A bound on the dual certificate representation v = A∗w controls the remaining inner product term.
- Dantzig selector: The Dantzig-selector proof parallels the LASSO argument while handling an additional term involving ∥Ah∥ℓ2.The paper sketches the corresponding intermediate bounds and concludes the proof by combining them with the earlier estimates.
5 Discussion
The paper presents a general random-sensing framework that achieves accurate recovery from nearly minimal noisy measurements without requiring the full RIP. It leaves relaxation of isotropy and independent sampling as open directions.
- Contributions: Sensing vectors are drawn independently from a probability distribution, giving a framework that covers standard and new compressive-sensing models.The framework includes Fourier measurements and supports tractable convex recovery of nearly sparse signals.
- Contributions: s-sparse signals can be accurately recovered from about s log n noisy DFT coefficients.The paper attributes this improvement to stability arguments that do not require the restricted isometry property.
- Contributions: The results establish stable recovery from a minimal number of samples without requiring the restricted isometry property to hold.The stated framework applies to nearly sparse signals and noisy compressive samples.
- Open questions: The paper leaves open how far isotropy can be relaxed and how correlated sensing vectors would change the results.The stated assumptions include independently sampled sensing vectors.
A Proof of Theorem 2.7 (the weak RIP)
The proof establishes a weak-RIP bound for matrices with independently sampled rows satisfying isotropy and incoherence, using expectation bounds, concentration, and Gaussian-process estimates.
- The matrix A has independent rows drawn from a distribution F satisfying isotropy and incoherence conditions.
- The target bound holds uniformly for vectors supported on a fixed set T together with a varying disjoint set R.
- The proof first bounds the relevant random variable in expectation and then controls deviations above that expectation with high probability.
- m ≥ C µ[s log m ∨ r log n log^4 m] is the measurement condition used in Lemma A.1.
- The argument combines prior results, Jensen-based symmetrization and comparison, and a conditional Gaussian-process estimate.
A.1 Proof of Lemma A.3
The proof of Lemma A.3 controls a Gaussian-process bound through majorizing measures, metric construction, packing, and covering-number estimates across multiple scales.
- The proof uses the majorizing measure theorem for a collection of zero-mean random variables with subgaussian increments.
- The metric is selected by bounding variances between process increments, using norms associated with the sets B and D.
- Packing and dual Sudakov lemmas provide tools for controlling covering numbers and Gaussian-process complexity.
- The proof bounds the relevant covering-number integral using volumetric estimates and a diameter bound for B × D.
- The construction defines functions ϕk on coarse and fine scales and verifies that they are uniformly bounded and satisfy the required multiscale condition.
A.2 Fine scale: k ≥1
At fine scales, the proof verifies the majorizing-measure condition by combining the metric estimates with packing and covering-number bounds.
- The fine-scale argument shows that the required majorizing-measure inequality holds for k ≥ 1.
- The packing-number bound supplies the final estimate, and the same calculation also applies for k = 0, −1 because ϕk ≤ 3 there.
- The relevant covering-number integral is bounded using crude covering estimates and a standard volumetric estimate for the Euclidean ball.
- The resulting bound is dominated by σ^-1, which establishes the claim.
A.3 Coarse scale: k ≤0
At coarse scales, the proof bounds the majorizing-measure quantities by controlling function magnitudes, separated points, and Gaussian-process expectations.
- For coarse scales, ϕk is bounded by 3 under the stated relationship between the diameter scale and m.
- The construction represents separated points through minimizers zj and zx, then uses their geometry to restrict the space containing the points.
- Packing and covering arguments are used to control the number of separated points at coarse scales.
- A Rademacher-sequence bound, together with a lemma extending prior work, controls the supremum over admissible supports R.
- The Gaussian-process estimate yields EG(z) ≤ C m s µ(1 + R2), after combining intermediate bounds.
A.4 Concentration around the mean
The proof bounds concentration around the mean using a Banach-space tail theorem and a norm on positive semidefinite matrices. With sufficiently many measurements, the failure probability decreases exponentially in the parameter β.
- m ≥ C_ε μ[s log m ∨ r log n log^4 m] ensures E X ≤ ε for any ε > 0.
- m ≥ C μ β[s log m ∨ r log n log^4 m] yields failure probability decreasing as e^-β.
- The concentration argument applies a theorem for independent symmetric Banach-space-valued random variables bounded by a common norm radius.
- The setup uses a norm defined on positive semidefinite matrices to control the relevant random quantity.
- The remaining concentration steps follow the cited framework and complete the proof of Theorem 2.7.
B Stochastic Incoherence
The stochastic incoherence extension conditions on rows with small entries, replacing deterministic coherence with a likely good event and a resulting near-isotropy condition. The adjusted arguments preserve the results with modified constants, while the proof may impose a stronger isotropy requirement than necessary.
- Stochastic Incoherence: Conditioning on the likely event that every row has small entries recreates deterministic coherence, while no guarantees are given outside that event.
- Stochastic Incoherence: The conditioned row distribution remains independent but satisfies near isotropy rather than exact isotropy, and the theorems extend with adjusted absolute constants.
- Stochastic Incoherence: The near-isotropy extension reproves the needed lemmas using the same principle, with the remaining calculations left analogous.
- Near-isotropy proof: For W = Eaa*, the proof bounds the restriction W_T,T and decomposes A_T* A_T − W_T,T before applying matrix Bernstein.
- Near-isotropy proof: σ^2 ≤ m(s + 1)μ, and this bound follows from the matrix Bernstein inequality.
- Near-isotropy proof: The noisy results require ∥A_T* A_T − I∥ ≤ 1/4, achievable under near isotropy by slightly increasing the measurement count.
- Good-event conditioning: The proof makes the stochastic incoherence event explicit by requiring each row’s entries to satisfy the coherence bound.
- Good-event conditioning: Jensen’s inequality and the requirement P(E^c) ≤ (mn)^−1 are used in deriving a sufficient condition for near isotropy.