CS Theorem (Candès-Tao 2006): M ≥ c·K·log(N/K) random measurements suffice for exact recovery if A satisfies RIP.
True sparse signal (orange) vs OMP recovery (blue). Residual in gray.
Geometric intuition: l1 ball (diamond) vs l2 ball (circle) — l1 promotes sparsity at corners.