Vivek Gopalakrishnan

A Quick Formulation of Compressed Sensing

2021-12-27 | A very, very mininal derivation of the optimization

Compressed sensing is a singal processing method for reconstructing a signal from an undersampled set of measurements. Here, we will derive the optimization problem at the core of compressed sensing.

Our objective is to obtain a subsampled version of ss from yy, and then recover sU1xs \stackrel{\mathcal U^{-1}}{\mapsto} x, i.e.,

mins12yCΨs22 . \min_s \frac{1}{2} ||y - C\Psi s||_2^2 \,.

As stated, this optimization is a underspecified / indeterminate problem (i.e., there are infinitely many solutions for ss), so we constrain the solutions to be sparse:

mins12yCΨs22+λs0 . \min_s \frac{1}{2} ||y - C\Psi s||_2^2 + \lambda||s||_0 \,.

However, minimizing l0l_0 norms is NP hard,[1] so we relax the problem with the l1l_1 norm:

mins12yCΨs22+λs1 . \min_s \frac{1}{2} ||y - C\Psi s||_2^2 + \lambda||s||_1 \,.

[1] Because it requires combinatorial optimization.
This is a well-defined problem, and is solvable with linear programming (e.g., basis pursuit, denoising/matching). Additionally, Equation 3 is equivalent to Equation 2 under certain conditions (e.g., ν\nu-incoherence) and constraints on CΨC\Psi. Then, given a noisy, downsampled measurement yy, solve Equation 3 to get s^\hat s, and predict the original signal to be x^=Ψs^\hat x = \Psi \hat s which is equivalent to s^U1x^\hat s \stackrel{\mathcal U^{-1}}{\mapsto} \hat x.