YALL1 is a Matlab program by Yin Zhang, Junfeng Yang, and Wotao Yin that solves the following $l^1$ minimization problems
basis pursuit \[ \min \norm{\mat W \vec x}_1 \quad \mbox{such that} \quad \mat A \vec x = \vec b \]
L1/L1 \[ \min \norm{\mat W \vec x}_1 + \frac{1}{\nu} \norm{\mat A \vec x - \vec b}_1 \]
L1/L2 (basis pursuit denoising) \[ \min \norm{\mat W \vec x}_1 + \frac{1}{2\rho} \norm{\mat A \vec x - \vec b}_2^2 \]
L1/L2 constrained \[ \min \norm{\mat W \vec x}_1 \quad \mbox{such that} \quad \norm{\mat A \vec x - \vec b}_2^2 \lt \delta \]
Where the measurement matrix $\mat A \in \real^{m \times n}$ has $m \lt\lt n$, and the solution $\vec x$ is known to be (approximately) sparse. The unitary sparsifying basis $\mat W$ is optional. YALL1 also solves positively constrained variants of these problems ($\vec x > 0$).
Astute readers may have noted that $\mat A$ has far more columns than rows, making the problem $\mat A \vec x = \vec b$ underdetermined: there exist an infinite number of satisfactory $\vec x$. Recent work on what has come to be known as compressed sensing has shown that sparse solutions ($\vec x$ having only a few non-zero coefficients) can be found very efficiently using techniques based on the $l^1$ norm (the sum of coefficients) rather than the more traditional $l^2$ norm (least squares). Furthermore, in many cases these sparse solutions are physically interpretable and/or serve quite well in image compression, signal acquisition, and classification tasks.
Compressed sensing research has been very active since 2006, both in terms of the theoretical/mathematical foundation and applications. A good overview is given in
Emmanuel Candès; and Michael Wakin, An introduction to compressive sampling (PDF link). IEEE Signal Processing Magazine, 25(2), pp. 21 – 30, March 2008
See also Terence Tao’s blog entry, a comprehensive directory of compressed sensing research, the Nuit Blanche blog, and a tons of videos.
Two neat applications:
Single pixel camera: The matrix $\mat A$ represents the random configurations of mirrors reflecting light onto a single photodetector, which records $\vec b$; the reconstruction $\vec x$ is the picture you took with a freaking single pixel camera.
Face recognition: (PDF link) The columns of $\mat A$ correspond to images of people’s faces, $\vec b$ is the face of an unknown person, and the largest components of $\vec x$ indicates the most similar face.