Questions: Compressive Sensing and Sparse Recovery

Question 1

In compressive sensing, you measure a K-sparse signal using M random measurements where M = 2K. Can you always recover the signal exactly?

• A. Yes, M = 2K is sufficient because 2K measurements can determine 2K unknowns (the support of the K-sparse signal and the K nonzero values)
• B. Not necessarily — recovery requires M > C·K·log(N/K) for some constant C > 1, and M = 2K may not satisfy this if N is large relative to K
• C. No, because random measurements discard information and violate the uncertainty principle
• D. Yes, but only if the signal is Gaussian; for deterministic signals, more measurements are needed

Answer: (B)

Recovery requires the measurement matrix to satisfy RIP, which for random matrices holds with high probability only if M > C·K·log(N/K). The logarithmic factor log(N/K) is crucial: for a long signal (large N) with few nonzero coefficients (small K), many measurements are still needed to distinguish the sparse signal from all possible random combinations of the same sparsity. M = 2K is appealing intuitively but insufficient unless N is small or K is large. The log factor reflects the information-theoretic cost of not knowing which K positions are nonzero.

Question 2

The Restricted Isometry Property (RIP) with isometry constant δ_K requires that (1−δ_K)||x||² ≤ ||Φx||² ≤ (1+δ_K)||x||² for all K-sparse vectors x. Why is this property sufficient for basis pursuit recovery?

• A. RIP ensures the measurement matrix preserves distances, so sparse signals cannot collide under measurement
• B. RIP guarantees that the ℓ₁-norm minimization (basis pursuit) will favor the original sparse solution over any other signal consistent with the measurements, because the true sparse signal is the unique minimum
• C. RIP is necessary but not sufficient; additional conditions on noise are required
• D. RIP applies only to Gaussian random matrices, not structured matrices

Answer: (B)

RIP says the measurement matrix acts like a quasi-isometry on sparse vectors: it preserves their geometry. If x is K-sparse and Φx is measured, then any other K-sparse signal x' with Φx' = Φx must have ||Φ(x−x')||² = 0. But RIP says ||Φ(x−x')||² ≥ (1−δ_K)||x−x'||², implying ||x−x'|| = 0, so x = x'. This means the true sparse signal is the unique K-sparse vector consistent with the measurements. Among all vectors consistent with the measurements, basis pursuit's ℓ₁ minimization will find the sparsest, which must be the true signal. RIP with small δ_K ≈ 0.3 ensures stable recovery with noise.

Question 3

Compressive sensing theory assumes the signal is sparse. If the signal is not sparse in any known basis, can compressive sensing still recover it?

• T. True
• F. False

Answer: False

If a signal is not sparse in any basis (truly random or chaotic), then observing any subset of its samples contains little information about the rest, and recovery is impossible — the information-theoretic limits apply. Compressive sensing gains its power from sparsity. However, many real signals (audio, images, video) are sparse or nearly sparse in learned bases (wavelets, dictionary atoms, neural network encodings), and CS applies there. For non-sparse signals, traditional Nyquist sampling at the signal bandwidth is necessary.

Question 4

In a compressive sensing application, you use a structured measurement matrix (e.g., Fourier subsampling: measure only M randomly chosen Fourier coefficients) instead of a Gaussian random matrix. Is performance as good?

• T. True
• F. False

Answer: False

Structured matrices are computationally efficient and fast to apply (no need to compute M arbitrary random dot products), but they do not satisfy RIP as reliably as unstructured Gaussian matrices. Fourier subsampling works well for signals sparse in time (few nonzero samples), but if the signal is sparse in frequency (few nonzero Fourier coefficients), then subsampling Fourier coefficients can alias and cause recovery to fail. Modern research uses structured matrices with theoretical guarantees (circulant matrices, binary matrices with specific properties), but as a rule, unstructured random matrices offer the best guaranteed performance for arbitrary sparse signals.

Question 5

Explain the phase diagram of compressive sensing: why does recovery succeed when M/N > C·K·log(N/K) but fail when M/N is below this threshold? What does the log(N/K) factor mean intuitively?

Model answer: The measurement rate M/N must exceed a critical threshold that depends on sparsity K and signal length N. Below the threshold, the subspace of solutions consistent with the measurements is large (many K-sparse signals fit the same measurements), and basis pursuit cannot distinguish the true signal. Above the threshold, RIP is satisfied and the true signal is the unique sparsest solution. The log(N/K) factor comes from information theory: to identify which K positions (out of N) are nonzero requires log(N choose K) ≈ K·log(N/K) bits of information. Since each measurement provides ≈ 1 bit of information (a random inner product), you need M ≈ K·log(N/K) measurements to encode the support. The constant C ≈ 1.0–1.5 depends on the RIP quality; typical statements use C ≈ 3–5 to be conservative.

This phase transition is sharp: below the threshold, recovery almost surely fails; above it, almost surely succeeds. It is one of the most beautiful results in signal processing, because it gives a principled way to choose M. In practice, you solve basis pursuit anyway and check whether recovery is accurate (compare to known signal or use cross-validation), but the phase diagram provides a rough guideline.