CS: Some recovery conditions for basis learning by L1-minimization

In the category, sparse dictionary: how to make them and find them here is an interesting paper by Remi Gribonval and Karin Schnass entitled Some recovery conditions for basis learning by L1-minimization. The abstract reads:

Many recent works have shown that if a given signal admits a sufficiently sparse representation in a given dictionary, then this representation is recovered by several standard optimization algorithms, in particular the convex l1 minimization approach. Here we investigate the related problem of infering the dictionary from training data, with an approach where l1-minimization is used as a criterion to select a dictionary. We restrict our analysis to basis learning and identify necessary / sufficient / necessary and sufficient conditions on ideal (not necessarily very sparse) coefficients of the training data in an ideal basis to guarantee that the ideal basis is a strict local optimum of the l1-minimization criterion among (not necessarily orthogonal) bases of normalized vectors. We illustrate these conditions on deterministic as well as toy random models in dimension two and highlight the main challenges that remain open by this preliminary theoretical results.

The following paper is only available through its abstract: Sparse representations of audio: from source separation to wavefield compressed sensing by Remi Gribonval. The abstract reads:

Sparse signal representations, which are at the heart of today's coding standards (JPEG, MPEG, MP3), are known to have had a substantial impact in signal compression. Their principle is to represent high-dimensional data by a combination of a few elementary building blocks, called atoms, chosen from a large collection called a dictionary. Over the last five years, theoretical advances in sparse representations have highlighted their potential to impact all fundamental areas of signal processing. We will discuss some current and emerging applications of sparse models in musical sound processing including: signal acquisition (Compressed Sensing - sampling wave fields at a dramatically reduced rate) and signal manipulation (e.g., source separation and enhancement for digital remastering). We will conclude by discussing the new algorithmic and modeling challenges raised by these approaches.

Image Credit: NASA/JPL/Space Science Institute, W00046997.jpg was taken on June 24, 2008 and received on Earth June 26, 2008. The camera was pointing toward SATURN-RINGS at approximately 725,870 kilometers away, and the image was taken using the CL1 and CL2 filters. This image has not been validated or calibrated. A validated/calibrated image will be archived with the NASA Planetary Data System in 2009.