Signal Processing

CoSaMP

Q: How many measurements does CoSaMP need to recover a k-sparse signal?

CoSaMP provides a uniform recovery guarantee when the m by N sensing matrix satisfies the restricted isometry property with constant delta_4k less than 0.1. For a random Gaussian or sub-Gaussian matrix this requires only m on the order of k times log(N/k) measurements, far below the N samples a Nyquist sampler would collect. As a concrete example, recovering a signal with N = 1024 coefficients and sparsity k = 20 typically succeeds with m near 200 to 250 measurements, a roughly 4 to 5 times reduction in acquired data. The guarantee is stable: if the true signal is only approximately sparse and the measurements carry noise, the recovery error is bounded by a constant times the best k-term approximation error plus the noise norm.

Q: How does CoSaMP differ from orthogonal matching pursuit?

Orthogonal matching pursuit (OMP) adds exactly one index to the support per iteration and never removes one, so it needs at least k iterations and can be derailed permanently by a single wrong early choice. CoSaMP instead identifies the 2k largest entries of the current residual proxy each iteration, merges them with the existing k-element estimate to form a 3k candidate set, solves least squares on that set, and then prunes back to the best k entries. Because the prune step can discard earlier mistakes, CoSaMP corrects bad choices, converges in a fixed number of iterations independent of k, and carries a rigorous RIP-based recovery proof that standard OMP lacks.

Q: What is the computational cost of one CoSaMP iteration?

Each iteration is dominated by two matrix-vector products with the m by N sensing matrix (forming the proxy and the new residual) plus a least-squares solve restricted to 3k columns. For a dense unstructured matrix the cost is on the order of m times N per iteration. When the sensing matrix is a structured operator such as a partial FFT or a random convolution, those products drop to O(N log N), which is why hardware sub-Nyquist receivers favor structured measurement matrices. The number of iterations needed to reach a target accuracy is logarithmic in the signal-to-noise ratio, so total runtime is essentially a small constant times the cost of a few transform evaluations.

/koh-samp/ (Compressive Sampling Matching Pursuit)

Short for Compressive Sampling Matching Pursuit, this greedy algorithm reconstructs a k-sparse signal from far fewer linear measurements than the Nyquist rate would demand. Introduced by Needell and Tropp in 2008, it advanced the framework of compressive sensing by adding a rigorous recovery proof to a fast iterative scheme. Each pass identifies the 2k largest entries of a residual proxy, merges them with the running k-element estimate into a 3k candidate set, solves a small least-squares fit, then prunes back to the best k coefficients. Because the prune step can discard earlier mistakes, CoSaMP converges in a fixed number of iterations and delivers stable recovery whenever the sensing matrix obeys the restricted isometry property with δ_4k < 0.1. In RF systems it underpins sub-Nyquist wideband receivers, where a 4 to 8 GHz spectral sweep is captured with 4 to 5 times fewer samples than a conventional digitizer.

Category: Signal Processing

Class: Greedy sparse recovery

RIP bound: δ_4k < 0.1

Inside the Identify-Merge-Estimate-Prune Loop

CoSaMP solves the same inverse problem as basis-pursuit convex optimization, recovering a sparse coefficient vector x from compressed measurements y = Φx, but it does so greedily rather than by linear programming. The starting point is a residual proxy, formed by applying the matched filter Φ^T to the current residual. The entries of this proxy with the largest magnitude reveal where the signal energy most likely lives, which is the geometric insight that makes the support search reliable when the sensing matrix is well conditioned on sparse subsets.

Each iteration runs four steps in sequence. First, the algorithm identifies the 2k indices with the largest proxy magnitude. Second, it merges that set with the support of the current estimate, producing a candidate set of up to 3k indices. Third, it estimates the signal by solving an ordinary least-squares problem restricted to those columns of Φ. Fourth, it prunes the least-squares solution back to its k largest entries, fixing the new support and the new residual for the following pass. Unlike orthogonal matching pursuit, which commits to one index forever, the prune step lets CoSaMP retract a poor early decision, which is what gives it both speed and a clean theoretical guarantee.

The guarantee rests on the restricted isometry property (RIP). A matrix Φ satisfies RIP of order s with constant δ_s if it nearly preserves the norm of every s-sparse vector. When δ_4k stays below about 0.1, CoSaMP recovers any k-sparse signal exactly in the noiseless case and recovers approximately sparse, noisy signals with an error bounded by the best k-term approximation error plus the measurement-noise norm. Random Gaussian, Bernoulli, and partial-Fourier matrices satisfy this property with high probability once the measurement count m reaches a small multiple of k·log(N/k).

Recovery Guarantee and Halting Condition

Sensing model (k-sparse x, m measurements):
y = Φx + e, Φ ∈ ℝ^m×N, ‖x‖₀ ≤ k

Residual proxy (per iteration):
u = Φ^T(y − Φa), Ω = supp(u, 2k)

Stable recovery bound (RIP δ_4k < 0.1):
‖x − a‖₂ ≤ C × ( ‖x − x_k‖₂ + (1/√k)‖x − x_k‖₁ + ‖e‖₂ )

Measurement count:
m ≈ C₀ × k × log(N / k)

Where x_k = best k-term approximation of x, a = current estimate, e = noise, C ≈ 20 and C₀ are constants. Example: N = 1024, k = 20 recovers reliably with m ≈ 200 to 250 measurements.

Greedy Sparse-Recovery Algorithm Comparison

Algorithm	Indices per iteration	Can retract?	RIP guarantee	Iterations	Cost per iteration
CoSaMP	Add 2k, prune to k	Yes	δ_4k < 0.1	Fixed (~6 to 10)	O(mN) or O(N log N)
Subspace Pursuit	Add k, prune to k	Yes	δ_3k < 0.165	Fixed	O(mN)
OMP	Add 1	No	Weaker / non-uniform	≥ k	O(mN)
Iterative Hard Thresholding	Gradient + threshold to k	Yes	δ_3k < 1/√32 (≈ 0.177)	Many	O(mN)
Basis Pursuit (L1)	Convex solve (no greedy step)	n/a	δ_2k < 0.414	Interior point	O(N³) class

Common Questions

Frequently Asked Questions

How many measurements does CoSaMP need to recover a k-sparse signal?

Recovery is guaranteed once the m×N sensing matrix satisfies RIP with δ_4k < 0.1, which random Gaussian or sub-Gaussian matrices achieve with only m ≈ k·log(N/k) rows. For N = 1024 and sparsity k = 20, reliable recovery typically needs m near 200 to 250 measurements, a 4 to 5 times reduction versus collecting all N Nyquist samples. The result is stable: with approximate sparsity and noise, the error is bounded by the best k-term approximation error plus the noise norm.

How does CoSaMP differ from orthogonal matching pursuit?

OMP adds exactly one index per iteration and never removes it, so it needs at least k iterations and a single bad early pick is permanent. CoSaMP instead grabs the 2k largest residual-proxy entries, merges them with the current k-element estimate into a 3k set, solves least squares, then prunes back to the best k. The prune step lets it retract mistakes, converge in a fixed iteration count independent of k, and carry a rigorous RIP recovery proof that standard OMP lacks.

What is the computational cost of one CoSaMP iteration?

Each pass is dominated by two matrix-vector products with Φ plus a least-squares solve on 3k columns, so a dense unstructured matrix costs O(mN) per iteration. When Φ is a structured operator such as a partial FFT or random convolution, those products drop to O(N log N), which is why hardware sub-Nyquist RF receivers favor structured measurement matrices. Iteration count grows only logarithmically in SNR, so total runtime is a small multiple of a few transform evaluations.

Related Terms

← Corrugated Waveguide Cosine Pulse →