Source-linked AI summary
Combining geometry and combinatorics: A unified approach to sparse signal recovery
R. Berinde, A. C. Gilbert, P. Indyk, H. Karloff, M. J. Strauss
TL;DR
Sparse signal recovery has a trade-off between geometric methods with compact, noise-resilient measurements and combinatorial methods with fast, explicit computation. The paper unifies these approaches through unbalanced-expander adjacency matrices and RIP-p, obtaining deterministic recovery schemes and related algorithmic results. It also identifies explicit construction limits and assumptions relevant to the guarantees.
Problem
Sparse recovery requires reconciling geometric methods’ compact, noise-resilient measurements with combinatorial methods’ fast, incremental, explicit computation.
Method
The paper relates sparse binary expander adjacency matrices to RIP-p matrices for p near 1 and combines this characterization with linear-program and combinatorial decoding.
Results
The paper obtains new deterministic measurement matrices and recovery algorithms, including O(k log(n/k)) measurements, O(log(n/k)) update time, and O(n log(n/k)) encoding time.
Takeaways & Limitations
Unbalanced expanders provide a common framework connecting geometric and combinatorial sparse recovery and support both linear-program and sublinear decoding results.
Abstract
from arXiv · showhide
There are two main algorithmic approaches to sparse signal recovery: geometric and combinatorial. The geometric approach starts with a geometric constraint on the measurement matrix and then uses linear programming to decode information about the signal from its measurements. The combinatorial approach constructs the measurement matrix and a combinatorial decoding algorithm to match. We present a unified approach to these two classes of sparse signal recovery algorithms. The unifying elements are the adjacency matrices of high-quality unbalanced expanders. We generalize the notion of Restricted Isometry Property (RIP), crucial to compressed sensing results for signal recovery, from the Euclidean norm to the l_p norm for p about 1, and then show that unbalanced expanders are essentially equivalent to RIP-p matrices. From known deterministic constructions for such matrices, we obtain new deterministic measurement matrix constructions and algorithms for signal recovery which, compared to previous deterministic algorithms, are superior in either the number of measurements or in noise tolerance.
1. Introduction
Sparse signal recovery divides into combinatorial methods with fast, explicit sketching but suboptimal length, and geometric methods with compact, noise-resilient measurements but costly recovery. This paper unifies them through unbalanced-expander adjacency matrices, RIP-p, and new recovery constructions.
- Motivation: Linear sketches compress signals while preserving useful information and support efficient updates, addition, streaming, network measurement, databases, and compressed sensing.A sketch is Φx, and linearity permits updates and sums directly in sketch space.
- Combinatorial approach: Combinatorial methods use sparse binary matrices and iterative identification, offering fast recovery, incremental sketch computation, and explicit constructions, but typically require suboptimal sketch length.Known explicit constructions for exactly k-sparse signals use k^2(log log n)^O(1) measurements.
- Geometric approach: Geometric methods use dense matrices satisfying Euclidean RIP and linear-program decoding, achieving O(k log(n/2k)) Gaussian or O(k log^O(1) n) Fourier measurements with measurement-error resilience.Their recovery procedure solves a linear program with n variables and n+m constraints.
- Unified framework: The paper shows that sparse expander adjacency matrices satisfy RIP-p for p near 1, and that suitable RIP-1 matrices are essentially equivalent to unbalanced expanders.For an unbalanced expander, scaling by d^1/p yields RIP-p for 1 ≤ p ≤ 1 + 1/log n with δ = Cε.
- New algorithms: Combining expander properties with decoding results yields deterministic recovery with O(k log(n/k)) measurements, O(log(n/k)) update time, and O(n log(n/k)) encoding time.The paper also gives noise-resilient recovery and a first scheme achieving the best known measurement and encoding-time bounds simultaneously.
- New algorithms: Expander adjacency matrices can also support sublinear combinatorial recovery for arbitrary vectors, with explicit constructions using O(k^2(log log n)^O(1)) rows.The construction improves the scope of prior bounds that were restricted to exactly k-sparse signals or had Ω(k^2) rows.
2. Unbalanced expanders and RIP matrices
The paper connects unbalanced expanders with RIP-p matrices for p near 1, showing that each framework characterizes the other under suitable conditions. These results yield deterministic sparse matrices with near-optimal measurement bounds.
- Definitions: Unbalanced expanders are bipartite graphs whose small left vertex sets have nearly the maximum possible number of distinct neighbors.A (k, ǫ)-expander requires |N(X)| ≥ (1 − ǫ)d|X| for every X of size at most k.
- Expander constructions: Probabilistic constructions achieve d = O(log(n/k)/ǫ) and m = O(k log(n/k)/ǫ^2) for (k, ǫ)-unbalanced expanders.
- Expander constructions: Explicit constructions provide left degree d = 2^O(log(log(n)/ǫ))^3 and right-set size m = kd/ǫ^O(1).
- RIP-p equivalence: The paper notes that RIP-1 and RIP-2 are incomparable: sparse binary matrices can have O(k log(n/k)) rows for RIP-1 but require Ω(k^2) rows for RIP-2.
- RIP-p equivalence: Scaling an expander adjacency matrix by d^1/p gives RIP-p for 1 ≤ p ≤ 1 + 1/log n, with distortion δ = Cǫ.
- RIP-p equivalence: For p = 1, the normalized adjacency matrix satisfies RIP1,k,2ǫ because expansion controls collisions and preserves the ℓ1 norm of sparse vectors.
- RIP-p equivalence: Conversely, a binary matrix with equal column weight satisfying scaled RIP-1 must be an adjacency matrix of an unbalanced expander.The equivalence arises because insufficient expansion creates edge collisions whose signs can cancel in the ℓ1 norm.
3. LP decoding
The LP decoder recovers sparse approximations from expander measurements because expansion makes kernel vectors ℓ1-smooth. This yields recovery guarantees, including a noise-resilient version, for the ℓ1 minimization program.
- Recovery framework: Expander adjacency matrices enable LP decoding for recovering sparse approximations.
- Kernel smoothness: Kernel vectors of an expander adjacency matrix cannot concentrate their ℓ1 norm on a small set of coordinates.The proof partitions coordinates by magnitude and uses expansion to control interactions between successive groups.
- Recovery guarantees: The noiseless recovery theorem applies when y = v − u lies in the measurement kernel and v has no larger ℓ1 norm than u.
- Recovery guarantees: A noisy analogue replaces the zero kernel condition with measurement discrepancy β = ∥Φy∥1.
4. Experimental Results
Experiments measure correct recovery for random sparse signals using sparse binary matrices and compare the empirical transition with the analytic Gaussian-matrix transition. The observed behavior is consistent with the Gaussian benchmark.
- Experimental setup: For n = 200 and d = 8, recovery probabilities were estimated over a 40 × 40 grid with 50 independent trials per point.
- Experimental setup: The experiment varies sparsity k = ρm and measurement count m = δn for signals with entries in {−1, 0, 1} or {0, 1}.
- Results: The empirical phase transition for binary sparse matrices is consistent with the analytic Gaussian random-matrix transition for LP recovery.
- Results: The theoretical scheme achieves best-known sparse approximate recovery bounds up to constant factors, with empirical asymptotic constants appearing to agree.
5. Sublinear-time decoding of sparse vectors
The section presents a simple sublinear-time decoder for k-sparse vectors using an augmented unbalanced-expander adjacency matrix. Its Reduce procedure identifies coefficients through bit tests and repeatedly halves the remaining support.
- Relation to prior work: The construction simplifies an earlier extractor-based algorithm by using an unbalanced expander, or equivalently a binary RIP-1 matrix.The paper identifies this assumption as the appropriate one for simplifying the algorithm.
- Measurement construction: The measurement matrix is an augmented adjacency matrix of a (k, 1/8)-unbalanced expander, with m log n rows.The augmentation uses a bit-test matrix to encode coefficient indices and values.
- Complexity: The decoder recovers any k-sparse vector in time O(m log^2 n).This is the theorem’s stated reconstruction-time bound.
- Decoding procedure: The Reduce procedure uses votes from isolated rows to construct a partial vector estimate y.A value is retained when it receives at least d/2 matching votes.
- Decoding guarantee: At most half of a k-sparse vector’s nonzero positions remain incorrect after Reduce.The stated guarantee is that x − y is k/2-sparse.
- Recursive recovery: The complete recovery algorithm recursively recovers the residual after subtracting the partial estimate.The final output combines y with Recover(Φ(x − y)).
6. Conclusion
The conclusion presents geometric and combinatorial sparse recovery as manifestations of a common phenomenon centered on unbalanced-expander adjacency matrices. It also reports preliminary evidence that sparse and Gaussian random projections can produce similar polytope projections.
- Unified perspective: Unbalanced-expander adjacency matrices unify the geometric and combinatorial approaches to sparse signal recovery.The paper characterizes both approaches as different manifestations of a common underlying phenomenon.
- Measurement matrices: The paper identifies a broad class of alternative measurement matrices that can be paired with the same or similar sparse-recovery algorithms.These matrices may or may not suit physical measurement processes.
- Experimental observation: Preliminary experiments suggest that Gaussian and sparse random matrices yield similar projections of polytopes.The reported similarity concerns high-dimensional geometric behavior despite the matrices’ structural differences.
Appendix A. HHS(p) decoding
The appendix extends expander-based decoding to arbitrary signals through the HHS(p) algorithm. It provides explicit and random measurement constructions with polynomial-time decoding in the measurement size.
- Algorithm: The HHS(p) algorithm is designed using suitably augmented and concatenated unbalanced-expander adjacency matrices.The modified algorithm is based on HHS from.
- Recovery guarantee: For arbitrary x ∈ R^n, HHS(p) returns an approximation with O(k/ε) nonzero entries.The theorem states this guarantee for a fixed sparsity parameter k and ε ∈ (0, 1).
- Runtime: HHS(p) runs in time polynomial in the measurement size R.The bound applies to both explicit and random constructions.
- Measurement complexity: Explicit constructions use R = O(k^2 log log n^O(1)) measurements, while random constructions use R = O(k polylog n).These are the stated row-count bounds for the two construction types.
- Postprocessing: Truncating the output to its k largest terms produces the modified approximation x̂_k.The appendix states this as Corollary 20.
A.1. The measurement matrices.
The measurement construction separates rapid identification from estimation and uses concatenated normalized adjacency matrices of unbalanced expanders satisfying an RIP_p property near p = 1.
- Matrix structure: The measurement matrix Ψ combines an identification matrix Ω with an estimation matrix Φ.The identification component locates significant signal entries, while the estimation component completes recovery.
- Expander component: The construction uses concatenated normalized adjacency matrices Γ of unbalanced expanders with p = 1 + 1/log(n).The matrices are normalized by d^-1/p.
- RIP property: These normalized expander matrices satisfy RIP_p,k′,δ with δ ≤ Cε′.The construction chooses ε′ so that 4ε′ + 1/(2d^1/p) < 1/2.
- Row complexity: Known explicit constructions use k′^2(log log n)^O(1) rows, whereas random constructions use k′ polylog(n) rows.The appendix denotes either row count by R.
- Identification matrix: The identification matrix has dimensions O(R polylog(n)) × n and factors as Ω = B ⊗^r A.B is a bit-test matrix and A is an isolation matrix.
A.1.1. Identification matrix.
The identification matrix uses a hierarchical product of sifting and noise-reduction matrices, built from unbalanced expanders and organized across logarithmic scales.
- The isolation matrix A has log(k) hierarchical blocks indexed by powers of two, with each block formed from products of 0–1 matrices.
- The sifting matrices S^(j)_s are normalized adjacency matrices of unbalanced expanders, equivalently normalized 0–1 RIPp,s,δ matrices.
- The noise-reduction matrices R^(j)_r attenuate noise around signals containing a single large component.
- Each block has dimension O(R polylog(n)) × n, with the product dimensions determining the critical construction parameters.
- The estimation matrix Φ is an RIPp,K,δ matrix, equivalently an adjacency matrix of an (K, ε)-unbalanced expander, with K = O(k polylog(n)).Its columns are scaled to have unit ℓp norm.
A.2. The HHS(p) algorithm.
The HHS(p) algorithm iteratively identifies substantial signal components, estimates their values, and subtracts their encoded contributions from the measurements.
- Each iteration identifies a small set of positions carrying a substantial fraction of the signal's ℓp weight.
- The algorithm then estimates the values of the identified signal positions.
- Finally, it subtracts the identified components' encoded contribution from the initial measurements.
A.3. Proof sketches.
The proof sketches establish progress through head–tail bounds, expander-based isolation, noise reduction, and RIP-based coefficient estimation, yielding geometric improvement in ℓp error.
- Head and tail: One iteration produces a new approximation whose error is bounded relative to the prior approximation.
- Geometric progress: The algorithm improves the ℓp error geometrically by repeatedly reducing it by a constant factor.
- Proof structure: The proof sequence combines signal head–tail relations, spike isolation, noise reduction, and RIP-based coefficient estimation.
- Head and tail: The analysis first relates the residual's ℓp norm to the tail after removing its largest O(k) components.
- Isolation: Expander-based sifting isolates most significant spikes from one another while limiting the number of outputs corrupted by large noise.
- Significant bands: For a significant (s, r) band, at most s polylog(n) residual terms have magnitude greater than 1/r.
- Noise reduction: Noise reduction converts isolated-spike signals with ℓ1 noise at most 1/s into outputs with noise at most C/r in at least half the outputs.
- Estimation: A small RIPp,L,δ matrix estimates significant coefficients, introducing error controlled by the best K-term approximation error.