Probabilistic reasoning in compressed sensing

Compressed sensing is an area of information theory where one seeks to recover an unknown signal from few measurements. A signal is often modeled as a vector in \(\mathbb{R}^n\), and linear measurements are given as \(y = Ax\) where \(A\) is an \(m \times n\) matrix. The best known results of compressed sensing are for random linear measurements, thus \(A\) is a random matrix. We will learn about some probabilistic successes and challenges in this area, with many connections to sampling theory, random matrix theory, and stochastic geometry.