L1 Optimization

Suppose you need to reconstruct a signal $X$ from a set of measurements $y$. $y$ usually does not contain complete information about $X$ due to real world constraints, e.g. you cannot deploy too many sensors. How do we reconstruct $X$? One approach is to assume that $X$ is sparse, i.e. there are not many non-zero elements (i.e. less unknown). So, we want to find the matrix $X$ with the minimum number of non-zero entries. In other words, we are trying to minimize $||X||_0$, by finding a transformation $\Phi$:

$\min{||X||_0}$

subject to

$\Phi X = y$ 

It's perfect, but there is only one problem. Computing $l_0$ is NP hard, which in simple terms means, it needs exponential time (not practical). There have been some approximation solutions of $l_0$ optimization (see this paper, for example), but in most cases, we usually use  $l_1$ as an approximation of $l_0$:

$||X||_1 = \sum_i{|x_i|}$

This is the basis for what is called as "compressive sensing" and "$l_1$ regularization" which has many applications in machine learning and signal processing, especially in bio-medical applications.