Source-linked AI summary
Lower Bounds for Sparse Recovery
Khanh Do Ba, Piotr Indyk, Eric Price, David P. Woodruff
TL;DR
The paper asks whether the known O(k log(n/k)) measurement bound for linear sparse recovery can be reduced to O(k). It proves, using packing and communication-complexity arguments, that Ω(k log(n/k)) measurements are necessary even for randomized recovery, so the linear bound is tight.
Problem
Whether general linear sparse-recovery sketches can improve the known O(k log(n/k)) bound toward the O(k) length achievable by nonlinear storage remains unresolved.
Method
The paper combines a geometric packing argument for deterministic recovery with a communication-complexity reduction for randomized recovery.
Results
Ω(k log(n/k)) rows are necessary for randomized ℓ1/ℓ1 recovery, matching the known O(k log(n/k)) upper bound.
Takeaways & Limitations
Linear compression cannot attain the O(k) sketch length of the simple nonlinear approach in this recovery setting.
Takeaways & Limitations
The deterministic packing approach fails for a randomized-tail distribution because the resulting signals are almost k-sparse in ℓ2 and can be recovered with O(k) measurements.
Abstract
from arXiv · showhide
We consider the following k-sparse recovery problem: design an m x n matrix A, such that for any signal x, given Ax we can efficiently recover x' satisfying ||x-x'||_1 <= C min_{k-sparse} x"} ||x-x"||_1. It is known that there exist matrices A with this property that have only O(k log (n/k)) rows. In this paper we show that this bound is tight. Our bound holds even for the more general /randomized/ version of the problem, where A is a random variable and the recovery algorithm is required to work for any fixed x with constant probability (over A).
1 Introduction
The paper proves that linear sparse-recovery sketches require Ω(k log(n/k)) measurements, even with randomized matrices, matching known upper bounds. It develops deterministic packing and randomized communication-complexity arguments, while contrasting linear sketches with shorter nonlinear representations.
- 1 Introduction: O(k log(n/k)) linear sketches were known to achieve constant-factor ℓ1/ℓ1 recovery, whereas nonlinear storage of the largest k coefficients needs only O(k) entries.The logarithmic factor matters for compression when n is large.
- 1 Introduction: The result rules out improving the general linear-sketch bound to O(k), despite the shorter nonlinear alternative.The paper describes linear compression as inherently more costly than the simple nonlinear approach.
- 1.1 Our techniques: For deterministic recovery, the proof packs separated head vectors and small ℓ1-tail balls; disjoint images inside a bounded image set force a lower bound on m.The head vectors form a binary error-correcting code, and volume ratios are controlled by scaling to the m-dimensional image space.
- 1.1 Our techniques: The deterministic packing strategy does not extend directly to randomized recovery because random tails can make signals almost k-sparse in ℓ2, enabling O(k)-measurement recovery for that distribution.The paper therefore replaces the packing argument with a different communication-complexity approach.
- 1.1 Our techniques: The randomized proof uses communication complexity to encode d = O(k log(n/k) log n) bits into x, while each measurement conveys only O(log n) bits.This yields m = Ω(k log(n/k)) rows in the discrete bounded-precision setting and is extended to arbitrary matrices through precision decomposition and perturbation control.
2 Preliminaries
The preliminaries define deterministic and randomized approximate ℓ1/ℓ1 recovery, the sketching model, norm-ball notation, and the meaning of sparsity.
- 2 Preliminaries: The paper studies the C-approximate ℓ1/ℓ1 guarantee for recovering a sparse approximation with sparsity parameter k.The supplied definition introduces this guarantee through Equation (2).
- 2 Preliminaries: A deterministic recovery algorithm pairs a fixed m × n observation matrix A with an algorithm mapping Ax to an approximate reconstruction.The guarantee must hold for every signal x.
- 2 Preliminaries: A randomized recovery algorithm samples A from a distribution over m × n matrices and requires the approximation guarantee with probability at least 3/4.The probability is over the randomized measurement matrix and recovery procedure as defined in the model.
- 2 Preliminaries: The notation p(r) denotes an ℓp ball of radius r, while ∥x∥0 denotes the number of nonzero entries of x.The superscript indicating ambient dimension is omitted when clear.
3 Deterministic Lower Bound
The deterministic lower bound uses separated sparse signals and a volume-packing argument to show that sufficiently accurate recovery requires Ω(k log(n/k)) measurements.
- 3 Deterministic Lower Bound: The proof constructs a large set Y of k-sparse binary vectors with pairwise Hamming distance at least k.A Gilbert–Varshamov bound supplies the required packing size.
- 3 Deterministic Lower Bound: Small ℓ1 balls around distinct points in Y must have disjoint images under any valid deterministic recovery scheme.Otherwise one measurement point would require an output close to two well-separated signal points.
- 3 Deterministic Lower Bound: If m is too small, two image balls collide, contradicting the recovery guarantee for points in Y.The contradiction follows because the recovered vector cannot be simultaneously close to two codewords separated by k in ℓ1 distance.
- 3 Deterministic Lower Bound: A volume comparison bounds the number of disjoint image balls by (1 + 1/ε)^m when they lie inside a larger image ball.The argument compares the volumes of images of radius-ε and radius-(1+ε) balls.
- 3 Deterministic Lower Bound: For constant C bounded away from zero, the resulting measurement lower bound is m = Ω(k log(n/k)).This matches the known O(k log(n/k)) deterministic upper bound stated in the paper context.
4 Randomized Upper Bound for Uniform Noise
The randomized analysis shows that uniform ℓ1-ball noise is not a hard distribution: Gaussian measurements can recover separated signal points using only O(k) measurements. The proof relies on the noise having very small ℓ2 norm and on Gaussian separation of signal images.
- 4 Randomized Upper Bound for Uniform Noise: A standard randomized lower-bound strategy seeks a hard input distribution over signal heads and tails.Here the candidate distribution uses separated sparse heads and uniformly random noise from an ℓ1 ball.
- 4 Randomized Upper Bound for Uniform Noise: Uniform noise from an ℓ1 ball has very small ℓ2 norm with high probability, even when its ℓ1 radius is a constant fraction of k.The cited bound is ˜O(k/√n) for the relevant noise distribution.
- 4 Randomized Upper Bound for Uniform Noise: For signals separated by ℓ2 distance at least r, Gaussian measurements preserve enough separation while limiting the noise image.Lemma 4.1 controls both signal differences and noise under the Gaussian matrix.
- 4 Randomized Upper Bound for Uniform Noise: An m × n Gaussian matrix recovers each y ∈ Y with probability 1 − 1/n under the theorem’s parameter condition.The probability is over both the measurement matrix and the uniformly sampled noise.
- 4 Randomized Upper Bound for Uniform Noise: Nearest-image decoding recovers the correct signal whenever the measured noise is less than half the measured separation from every competing signal.A union bound gives total failure probability at most 2/n^2 + 1/(2n) < 1/n.
- 4 Randomized Upper Bound for Uniform Noise: Thus, the deterministic hard-instance construction becomes easy under uniform random noise, even when the noise ball has polynomially larger radius.The paper identifies this failure of the natural hard distribution as the main consequence of the theorem.
- 4 Randomized Upper Bound for Uniform Noise: For binary k-sparse signals with uniform noise from B1(s), m = O(k/ε) measurements suffice for recovery probability 1 − 1/n under the stated condition.The corollary instantiates the general theorem for the sparse signal set used in the deterministic construction.
5 Randomized Lower Bound
The paper proves that randomized ℓ1/ℓ1 sparse recovery still requires Ω(k log(n/k)) measurements, matching the known upper bound. The proof reduces recovery to Augmented Indexing after discretizing and perturbation-controlling the measurement matrix.
- Discretization: Rounding an orthonormal-row matrix to O(log n) bits introduces a perturbation s whose ℓ1 norm is bounded by n^2 2^-b ||v||_1.The perturbation representation is A′v = A(v − s).
- Communication Complexity: Augmented Indexing has communication cost Ω(d), providing the communication lower bound used in the reduction.The theorem applies to public-coin protocols as well as private-coin protocols, up to an O(log d) difference.
- Reduction: The proof encodes d = Ω(k log(n/k) log n) bits into a vector formed from log n exponentially weighted sparse codewords.A maximal family of k-sparse binary vectors contributes log |X| = Ω(k log(n/k)) bits per block.
- Handling Randomization: Random perturbation by a vector from the ℓ1 ball makes recovery for the matrix-dependent shifted input statistically close to recovery for an independent input.The construction chooses u so that the perturbation effect is o(1) in statistical distance while preserving the relevant ℓ1-radius condition.
- Conclusion: The resulting protocol communicates O(m log n) bits, and Augmented Indexing therefore implies m = Ω(k log(n/k)).Each rounded measurement uses O(log n) bits, converting the communication lower bound into a row lower bound.
A Proof of Lemma 3.1
The proof constructs a large binary sparse codebook from a q-ary codebook with prescribed Hamming distance. The Gilbert–Varshamov bound supplies the required codebook size.
- Codebook Construction: A q-ary codebook of block length k and relative distance ǫ yields a binary codebook of dimension qk and minimum distance 2ǫk.Replacing each q-ary character by its q-dimensional standard basis vector preserves codebook size and gives exactly k ones per codeword.
- Codebook Size: The Gilbert–Varshamov bound guarantees a codebook whose size satisfies log L > (1 − H_q(ǫ))k log q.The bound applies when ǫ < 1 − 1/q.
B Proof of Lemma 4.1
The proof derives the lemma by applying standard probabilistic bounds for arbitrary D and selecting D so that both resulting upper bounds equal δ.
- Proof: For any D > 0, standard arguments provide the two probability bounds needed by the lemma.The proof concludes by setting both right-hand sides to δ.
C Proof of Lemma 4.2
The proof bounds coordinate tails for a vector uniformly sampled from an ℓ1 ball by analyzing one coordinate and applying symmetry with a union bound. This yields an ℓ∞ control in terms of the ℓ1 radius.
- Coordinate Distribution: The density of a coordinate magnitude |z_1| at t is proportional to the volume factor (s − t)^(n−1).Normalizing this cross-sectional volume gives the coordinate distribution used for the tail estimate.
- Tail Bound: Pr[|z_1| > αs log n/n] < e^(-α log n), giving an exponentially small tail at the logarithmic threshold.The estimate follows from (1 − α log n/n)^n < e^(-α log n).
- Union Bound: By symmetry across coordinates and a union bound, the coordinate-wise tail estimate yields the lemma’s bound on ||z||_∞.The argument applies the same estimate to every coordinate z_i.