Source-linked AI summary
Shannon Theoretic Limits on Noisy Compressive Sampling
Mehmet Akçakaya, Vahid Tarokh
TL;DR
The paper asks how many noisy compressed measurements are needed to recover sparse signals and addresses the gap between information theoretic and practical recovery results. It analyzes several recovery criteria with a joint-typicality decoder and proves linear measurement scaling in the linear sparsity regime, while also treating sublinear sparsity.
Problem
The paper studies the measurement requirements for recovering L-sparse signals in C^M from noisy compressed samples and the gap between information theoretic and L1-based recovery.
Method
The paper analyzes several recovery metrics using a decoder based on joint typicality to characterize sparse-recovery performance limits.
Results
O(L) measurements are asymptotically necessary and sufficient for several recovery metrics in the linear sparsity regime, with P remaining constant for Error Metrics 2 and 3.
Takeaways & Limitations
The results establish asymptotically linear measurement scaling for several noisy sparse-recovery criteria when sparsity grows linearly with ambient dimension.
Abstract
from arXiv · showhide
In this paper, we study the number of measurements required to recover a sparse signal in ${\mathbb C}^M$ with $L$ non-zero coefficients from compressed samples in the presence of noise. For a number of different recovery criteria, we prove that $O(L)$ (an asymptotically linear multiple of $L$) measurements are necessary and sufficient if $L$ grows linearly as a function of $M$. This improves on the existing literature that is mostly focused on variants of a specific recovery algorithm based on convex programming, for which $O(L\log(M-L))$ measurements are required. We also show that $O(L\log(M-L))$ measurements are required in the sublinear regime ($L = o(M)$).
I. INTRODUCTION
The paper studies Shannon theoretic limits for recovering sparse signals from noisy compressed measurements, focusing on how the required measurement count scales with sparsity and ambient dimension. Using joint typicality across several recovery metrics, it shows linear measurement scaling in the linear sparsity regime and analyzes the sublinear regime.
- Problem: The problem is to determine the number of noisy compressed measurements needed to recover an L-sparse signal in C^M.The measurement model uses an N × M matrix, with sparsity measured by the number of nonzero coefficients.
- Motivation: The paper addresses a gap between information theoretic decoders and practical L1-based recovery, which requires O(L log(M −L)) measurements.Prior information theoretic results achieve O(L) measurements in the linear sparsity regime, while L1 constrained quadratic programming requires the larger order.
- Approach: The analysis considers multiple recovery metrics, including metrics described as more Shannon theoretic or statistical in nature.This broadens the focus beyond a single performance metric used in earlier noisy-recovery work.
- Approach: Joint typicality provides the decoder used to characterize sparse-recovery performance limits, although it may not be computationally feasible in practice.The decoder is used as an information theoretic analysis tool rather than presented as a practical algorithm.
- Results: The paper also states analogous theorems for the sublinear sparsity regime, L = o(M).The introduction identifies this regime separately from the linear sparsity setting.
II. MAIN RESULTS
The paper studies noisy sparse recovery using Gaussian measurements and evaluates asymptotic reliability under three recovery error metrics. Its main results give achievability and converse conditions, including exponential error behavior for several metrics.
- Problem and setup: The model uses an unknown sparse vector, Gaussian measurement matrices, noisy samples, and a decoder that outputs the estimated support.Recovery is asymptotically reliable when the average decoding error tends to zero as M grows.
- Error Metric 1: For Error Metric 1, the paper proves both sufficient and necessary measurement conditions for asymptotically reliable sparse recovery.The corresponding achievability and converse results are stated in Theorems 2.1 and 2.3.
- Error Metric 1: Under Error Metric 1, the probability that a fixed Gaussian measurement matrix has error at least ξ is controlled with exponentially improving reliability.The paper also reports that the average decoder error decays super-polynomially in L under the achievability conditions.
- Error Metric 3: For Error Metric 3, achievability and converse theorems are proved, including exponential failure below the converse measurement condition.This metric is described as originating from Shannon Theory and characterizing recovery of subspace information.
A. Discussion of The Results
The results show that asymptotically reliable sparse recovery in the linear sparsity regime requires and can achieve a number of measurements linear in L. For Error Metrics 2 and 3, this holds while P remains constant, and corresponding converses establish necessity.
- O(L) measurements are sufficient for asymptotic reliable sparse recovery under Error Metric 1.
- The O(L) result leaves a gap relative to O(L log(M −L)) measurements required by L1 constrained quadratic programming.
- O(L) measurements are sufficient for asymptotic reliable sparse recovery under Error Metrics 2 and 3, while P remains constant.
- O(L) measurements are asymptotically necessary for the considered recovery criteria.
- A Gaussian measurement matrix supports reliable sparse recovery as long as N = O(L), with failure probability tending to zero exponentially fast in M.
- When the number of measurements is below specified constant multiples of L, the error probability tends to one with overwhelming probability.
A. Notation
The notation defines submatrices formed from selected measurement-matrix columns and projection matrices onto their spans and orthogonal complements.
- a_i denotes the ith column of the measurement matrix A.
- A_J is the matrix whose columns are the measurement-matrix columns indexed by J.
- Π_B projects orthogonally onto the subspace spanned by the columns of B, while Π⊥_B projects onto its orthogonal complement.
B. Joint Typicality
The paper introduces joint typicality to characterize whether a noisy observation and a candidate support are compatible, then analyzes its probabilities using Gaussian structure and chi-square tails.
- Joint typicality tests a noisy observation y = Ax + n against a candidate index set J of size L.
- A candidate set is δ-jointly typical when A_J has rank L and the observation satisfies the associated typicality condition.
- The model assumes Gaussian measurement entries, Gaussian noise, and an L-sparse signal.
- For any L-index set I, the Gaussian submatrix A_I has rank L with probability one.
- The analysis separates the true support I from competing sets J with overlap K < L and applies unitary transformations to preserve Gaussian independence.
- The resulting energy terms are chi-square random variables with N −L degrees of freedom, so tail bounds control typicality probabilities.
C. Proofs of Theorems For Different Error Metrics
The proofs establish reliable recovery and converse bounds across three error metrics, using error-event bounds, asymptotic analysis, and technical lemmas. The arguments also expose stringent signal-growth and power requirements for Error Metric 1.
- Error Metric 1: The Error Metric 1 proof bounds decoder failure through the events E0, EC I, and incorrect support recovery.The analysis uses technical lemmas and asymptotic bounds to show perr(D|x) → 0 under the theorem’s conditions.
- Technical analysis: Technical lemmas control maxima, derivatives, and polynomial roots to establish the asymptotic error bounds used in the proofs.For example, the analysis shows that f′′ crosses zero exactly twice and that f′ crosses zero once, making the latter point a local minimum.
- Error Metric 2: The Error Metric 2 proof requires error probabilities to vanish for support overlaps up to (1 − α)L, rather than only exact support recovery.Its achievability argument allows Lµ2(x) to converge to a constant while keeping P from growing with N.
- Error Metric 2: The Error Metric 2 achievability analysis shows perr(D|x) → 0 exponentially fast as L → ∞ when N exceeds a linear factor of L.The stated sufficient condition is N > C5L, with C5 depending on β, γ, P, and ν.
IV. PROOFS OF CONVERSES
The converse proofs suppress the dependence of x on M when that relationship is implicit, simplifying notation throughout the section.
- The proofs write x for x(M) whenever there is no ambiguity.
A. Genie-Aided Decoding and Connection with Noisy Communication Systems
The converse argument recasts sparse-support recovery as communication over a noisy multiple-input single-output channel. Support patterns become codewords, and decoding performance is bounded using channel coding arguments.
- Genie-Aided Decoding and Connection with Noisy Communication Systems: A genie reveals the support I of x, whose nonzero coordinates are represented as xI for the decoder.The support is I = {i1, i2, …, iL}, and xI contains the corresponding L coefficients.
- Genie-Aided Decoding and Connection with Noisy Communication Systems: Each candidate support J defines a codeword formed from the corresponding columns of the measurement matrix and transmitted through a MISO channel.The channel output has coordinates yk = zk + nk, with average signal power ν^2 and noise variance specified in the construction.
- Genie-Aided Decoding and Connection with Noisy Communication Systems: The converse uses the strong converse of channel coding to show that decoding error approaches one exponentially fast when the support-code rate exceeds channel capacity.The argument first ensures that Gaussian codewords satisfy a power constraint with high probability, then applies the channel-coding converse.
- Genie-Aided Decoding and Connection with Noisy Communication Systems: For Error Metric 2, Hamming distortion allows decoded supports to differ from the true support in at most 2αL positions.The associated source is transmitted within distortion 2αL, linking approximate support recovery to reliable communication under distortion.
- Genie-Aided Decoding and Connection with Noisy Communication Systems: For Error Metric 3, the proof assumes the largest nonzero coefficient remains sufficiently related to the noise level so that signal terms are not asymptotically dominated.The paper notes that otherwise such terms are unimportant for recovery and could be replaced by zeros.
V. SUBLINEAR REGIME
In the sublinear regime L = o(M), the paper states equivalent achievability and converse theorems for three recovery-error metrics. These results yield logarithmic dependence on the ambient dimension through conditions involving L log(M − L).
- Proof strategy: The sublinear-regime proofs reuse the linear-regime proof structure and replace the earlier bounds with Equation (21) where required.Technical steps include showing that d(z) is maximized at z = α and deriving a lower bound proportional to (1 − α)L log(M − L).
- Error Metric 1: For Error Metric 1, asymptotic reliable recovery is achievable and impossible below respective conditions involving L log(M − L).The achievability threshold depends on µ(x(M)) and ν, while the converse threshold depends only on P and ν.
- Error Metric 2: For Error Metric 2, asymptotic reliable recovery is achievable and impossible under corresponding threshold conditions when Lµ2(x(M)) and P satisfy the stated assumptions.The achievability theorem assumes Lµ2(x(M)) and P are constant; the converse assumes P is constant.
- Error Metric 3: For Error Metric 3, asymptotic reliable recovery is achievable under a sufficient condition, while a converse applies when nonzero terms decay at the same rate.Both statements assume P is constant, and the converse rules out reliable recovery below its stated threshold.