Compressive Sensing & L1 Reconstruction Simulator

Q: Does compressive sensing violate the Nyquist sampling theorem?

No, it does not. The Nyquist theorem gives the number of samples needed to perfectly recover an arbitrary band-limited signal. Compressive sensing restricts the class to K-sparse (or compressible) signals and uses that prior, allowing the number of measurements to drop to M = O(K log(N/K)). The Candes-Tao-Donoho results from 2006 show that if the sensing matrix satisfies the RIP (Restricted Isometry Property), L1 minimization recovers the signal almost surely. Nyquist is not broken — the two theorems address different problem classes.

Q: How should I choose the sensing matrix? What is the difference between Gaussian and DFT?

In theory, Gaussian random or Bernoulli ±1 matrices satisfy the RIP with near-optimal constants and need the fewest measurements. In practice, however, you are usually limited to a physically realizable matrix: random rows of a DFT (discrete Fourier transform) for MRI, Hadamard or Bernoulli patterns for a single-pixel camera. This tool reproduces the trend that the RIP constant delta_2K worsens in the order Gaussian → Bernoulli → DFT → Hadamard. Design with the hardware in mind and target delta_2K < 0.4.

Q: When should I use Basis Pursuit, Iterative Soft Thresholding or OMP?

Basis Pursuit (BP) solves the L1 problem exactly as a linear or second-order cone program, giving the best accuracy at the smallest number of measurements but costing about N^3 operations. IST/FISTA only repeats soft thresholding, costs N·M·iter, and is practical for large problems such as 256² or 512² MRI images. OMP (Orthogonal Matching Pursuit) greedily picks one non-zero index at a time; it is fast when K is small and known but cannot recover from a wrong selection. Switching the algorithm in this tool shows the difference in noise amplification and computational cost.

Q: Can a real system really achieve 4x faster MRI or single-pixel imaging?

Yes, under the right conditions and in production today. MRI images are nearly sparse in the wavelet domain (K/N ≈ 5–10%), so sub-sampling k-space to 1/4 still produces diagnostic-quality reconstructions; this has been demonstrated on Siemens/GE/Philips clinical scanners. Rice University's Baraniuk group published the single-pixel camera in 2008, recovering a 64×64 image from M = 1638 measurements (40% compression) using a single photodiode. The technique is also widely used in seismic, wireless and genomic applications. However, signals that violate the K-sparse assumption (e.g. white noise) gain nothing from CS.

Compressive Sensing & L1 Reconstruction Simulator

A hands-on simulator for compressive sensing: recover a "sparse" N-dimensional signal that has only K non-zero entries from far fewer than Nyquist measurements, using L1 minimization. Change the signal dimension, number of measurements, sensing matrix, noise level and reconstruction algorithm to watch the Candes-Tao bound, the RIP constant and the reconstruction error update in real time.

Parameters

Signal dimension N

Number of samples in the signal x to recover

Sparsity K

Number of non-zero entries (the K in K-sparse)

Measurements M

Size of the compressed observation vector y

Sensing matrix Φ

A matrix that satisfies the RIP requires fewer M for recovery

Noise std. σ

Measurement noise y = Φx + n, n ~ N(0, σ²)

Reconstruction algorithm

BP = exact / IST = iterative / OMP = greedy

Results

—

Compression M/N (%)

—

Min. M (Candes-Tao)

—

Info ratio M/M_req

—

RIP constant δ_2K

—

Recon. error ‖x̂−x‖₂

—

Complexity log10(ops)

—

Φx → y → x̂ pipeline visualization

Left: N-dimensional sparse signal x with K spikes. Centre: M×N sensing matrix Φ. Right: M-dimensional compressed measurement y and the L1-reconstructed x̂. Colour intensity is amplitude; green = successful recovery, red = failure.

Original vs reconstructed signal

Recovery success rate vs compression M/N

Theory & Key Formulas

$$\min_x \|x\|_1 \text{ s.t. } \|y - \Phi x\|_2 \leq \epsilon,\quad M \geq C\,K\,\log(N/K)$$

The L1 minimization problem (Basis Pursuit) and the Candes-Tao bound on the number of measurements. y: measurement vector (M×1), Φ: sensing matrix (M×N), x: sparse signal (N×1), ε: noise tolerance, constant C ≈ 2–5.

$$\text{RIP}: (1-\delta_{2K})\|x\|_2^2 \leq \|\Phi x\|_2^2 \leq (1+\delta_{2K})\|x\|_2^2$$

Restricted Isometry Property. When δ_2K is below about 0.4, L1 recovery is stable. Gaussian and Bernoulli matrices satisfy this asymptotically for M ≥ 5K·log(N/K).

$$\|\hat{x} - x\|_2 \leq C_1 \sigma \sqrt{M}\,/\,\sqrt{M - C_2 K \log(N/K)}$$

Upper bound of the noisy reconstruction error. As M approaches the theoretical minimum, the denominator goes to zero and the error blows up. Noise amplification follows BP < IST < OMP.

Compressive Sensing & L1 Reconstruction

🙋

I keep hearing "compressive sensing", but how is it actually different from ordinary data compression like ZIP?

🎓

Good question. ZIP-style compression first measures the whole signal and then throws away the redundancy. Compressive sensing (CS) does the opposite: it collects only a few measurements in the first place. Instead of N samples, it takes M (≪ N) and reconstructs the N-dimensional signal afterwards by computation. In MRI that means about 1/4 of the scan time; in a single-pixel camera it lets a single photodiode capture an image. The 2006 result by Candes, Tao and Donoho — "under certain conditions you can recover the signal exactly with probability one" — was the breakthrough.

🙋

Wait, you can reconstruct what you didn't measure? Linear-algebra-wise it's an underdetermined system (M equations for N unknowns), right?

🎓

Exactly — algebraically it has infinitely many solutions. But if you add the prior that the signal is K-sparse, i.e. only K of N entries are non-zero, the answer becomes unique. That K is the "Sparsity K" slider in this tool. Then you just look for the solution that minimizes the L1 norm ‖x‖₁ = Σ|xᵢ|, and miraculously you land on the correct answer. L2 minimization (ordinary least squares) spreads small values across every entry and fails, but the "corners" of L1 snap onto the sparse solution.

🙋

So how far can M be pushed down? The stats above show an "Info ratio M/M_req".

🎓

The magic formula from Candes-Tao is M ≥ C·K·log(N/K). For N=500, K=20 you get M_req ≈ 129; even for N=10⁶, K=10⁴ you only need M ≈ 50,000. The cost grows logarithmically, not linearly. The default M = 100 is below M_req = 129, so the info ratio is around 0.78 and the verdict says "no recovery guarantee". Push the M slider above 130 and the verdict turns green.

🙋

When I switch the sensing matrix Φ from Gaussian to Hadamard, the RIP δ gets worse. What's that about?

🎓

The RIP (Restricted Isometry Property) says "applying Φ to any 2K-sparse vector approximately preserves its energy." If δ_2K stays below about 0.4, L1 recovery is stable. Gaussian and Bernoulli random matrices come close to the theoretical optimum, but in real applications you cannot choose Φ freely: MRI gives you random rows of a DFT, a single-pixel camera gives you Hadamard, and so on. When the RIP is worse, you compensate by collecting more measurements M.

🙋

Finally, how do I decide between BP, IST and OMP? The complexity log10(ops) differs by 1–2 orders.

🎓

Basis Pursuit solves the L1 problem exactly as a linear program or SOCP — CVXPY or MOSEK can do it. It's about N³, so N = 10⁴ is the realistic ceiling. For MRI-scale problems with N = 512² = 262,144, FISTA (the accelerated IST) is the standard at N·M·iter cost. OMP is fastest when K is small and known but is unforgiving: pick the wrong support index and you cannot recover. In research, people typically benchmark "best achievable accuracy" with BP first and then ship with FISTA for speed.

Frequently Asked Questions

No, it does not. The Nyquist theorem gives the number of samples needed to perfectly recover an arbitrary band-limited signal. Compressive sensing restricts the class to K-sparse (or compressible) signals and uses that prior, allowing the number of measurements to drop to M = O(K log(N/K)). The Candes-Tao-Donoho results from 2006 show that if the sensing matrix satisfies the RIP (Restricted Isometry Property), L1 minimization recovers the signal almost surely. Nyquist is not broken — the two theorems address different problem classes.

In theory, Gaussian random or Bernoulli ±1 matrices satisfy the RIP with near-optimal constants and need the fewest measurements. In practice, however, you are usually limited to a physically realizable matrix: random rows of a DFT (discrete Fourier transform) for MRI, Hadamard or Bernoulli patterns for a single-pixel camera. This tool reproduces the trend that the RIP constant δ_2K worsens in the order Gaussian → Bernoulli → DFT → Hadamard. Design with the hardware in mind and target δ_2K < 0.4.

Basis Pursuit (BP) solves the L1 problem exactly as a linear or second-order cone program, giving the best accuracy at the smallest number of measurements but costing about N³ operations. IST/FISTA only repeats soft thresholding, costs N·M·iter, and is practical for large problems such as 256² or 512² MRI images. OMP (Orthogonal Matching Pursuit) greedily picks one non-zero index at a time; it is fast when K is small and known but cannot recover from a wrong selection. Switching the algorithm in this tool shows the difference in noise amplification and computational cost.

Yes, under the right conditions and in production today. MRI images are nearly sparse in the wavelet domain (K/N ≈ 5–10%), so sub-sampling k-space to 1/4 still produces diagnostic-quality reconstructions; this has been demonstrated on Siemens/GE/Philips clinical scanners. Rice University's Baraniuk group published the single-pixel camera in 2008, recovering a 64×64 image from M = 1638 measurements (40% compression) using a single photodiode. The technique is also widely used in seismic, wireless and genomic applications. However, signals that violate the K-sparse assumption (e.g. white noise) gain nothing from CS.

Real-World Applications

Medical imaging (faster MRI): This is the most successful real-world application of compressive sensing. MRI images are nearly sparse in the wavelet domain, so sub-sampling k-space to 1/2–1/4 and recovering with L1 minimization (CS-MRI) still produces diagnostic-quality images. The technique is shipping in clinical scanners such as Siemens Compressed Sensing GRASP, GE HyperSense and Philips Compressed SENSE, directly cutting cardiac-MRI breath-hold time and paediatric-MRI sedation time. Similar research is under way for low-dose CT.

Single-pixel camera and specialty imaging: The single-pixel camera announced by Baraniuk's group at Rice University in 2008 uses a DMD (digital micromirror device) to project Hadamard or Bernoulli patterns and captures images with just one photodiode. It is most useful in the terahertz, infrared and X-ray bands where CCD arrays are difficult to build, and is now being deployed in near-infrared and quantum imaging.

Wireless, radar and seismic signals: 5G millimetre-wave sparse channel estimation, wide-band spectrum sensing in cognitive radio, ground-penetrating radar and sparse reflectivity estimation in seismic exploration are all standard CS application areas because the underlying signals are physically a "small number of arriving waves". Sub-Nyquist receivers that drop ADC sampling rates by ~10x are now in hardware.

Genomics and group testing: The "pooled testing" approach that became famous during COVID-19 is essentially compressive sensing. Estimating the infection status of N people (K positives with K ≪ N) from M pooled samples fits CS exactly, cutting the number of test kits by orders of magnitude. The same idea appears in single-cell RNA-seq gene-expression estimation.

Common Misconceptions and Pitfalls

The biggest pitfall is not checking whether the signal is actually K-sparse. The whole CS theory relies on "K-sparse or K-compressible". Real-world signals are rarely sparse as-is; you must first check whether they become sparse in an appropriate transform domain such as wavelet, DCT or curvelet. For images, wavelet gives roughly K/N ≈ 5%; for audio, DCT gives roughly K/N ≈ 10%. Pure white-noise-like signals gain nothing from CS. Choosing the right basis (dictionary) accounts for about 90% of the practical work.

Second, overestimating noise robustness. The error bound ‖x̂−x‖₂ ≤ C·σ·√M / √(M−M_req) shows that as M approaches M_req, the denominator shrinks and the error explodes. The "exact recovery at M = M_req" reported in papers is the noiseless ideal. In practice, take M ≥ 1.5–3 × M_req to keep a noise margin. Systems with low SNR (e.g. MRI below 20 dB) need an even larger M.

Finally, do not throw BP at a large problem without estimating its cost. Basis Pursuit is a beautiful exact solver but is N³: even N = 10,000 takes ~10¹² operations and a 512² = 262,144 image takes ~10¹⁶. Production uses first-order methods like FISTA, ADMM or SPGL1, or neural-network unrolled LISTA. The standard recipe is: measure the achievable accuracy ceiling with BP in research and ship FISTA for speed–accuracy balance.