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.
Let be the true signal.
Let be the representation of in a functional basis space.
Let for some universal transform basis (e.g., Fourier, wavelet, etc.).
Let be the measured signal, where is the measurement matrix.
Our objective is to obtain a subsampled version of from , and then recover , i.e.,
As stated, this optimization is a underspecified / indeterminate problem (i.e., there are infinitely many solutions for ), so we constrain the solutions to be sparse:
However, minimizing norms is NP hard, so we relax the problem with the norm:
|||Because it requires combinatorial optimization.|