compressed-sensing-recovery-bound

IN premise — summaries/2026/08/24/elhage-2022-toy-models-superposition-chunk-12.md

Created 2026-08-25T02:57:59+00:00

In classical compressed sensing, an n-dimensional k-sparse vector can be recovered from an m-dimensional projection if and only if m = Ω(k log(n/k)).

Summary

This sets the hard floor on how many measurements you actually need to reconstruct a signal that is mostly zeros: the number of samples must grow with the sparsity level times the log of the compression ratio, and no clever algorithm can beat that threshold. In practice, it means any system relying on compressed sensing has a fundamental information cost it cannot escape, so engineers must either accept more measurements or relax the sparsity assumption.