CS: MPTK Codec, Sparse Sampling, Learning, Compressed Counting, Separation of stereo speech signals, Wikimization

Today, we mostly have talks/codes and presentations dealing with sparsity and sometimes compressed sensing. Here they are:

Remi Gribonval points us to the fact that Emmanuel Ravelli has just released two packages based on MPTK:

mptkcodec: audio codec based on MPTK (C++)

• Presentation: This software is a fine-grain scalable audio codec based on MPTK. It is an implementation of the algorithms described in the paper "Union of MDCT bases for audio coding". It includes a modified version of MPTK 0.5.2, a C++ library for coding/decoding MPTK books and several standalone utilities.

mdctmex: Matlab functions for audio signal representations and coding (Matlab/C++)

• Presentation: Matlab functions (MEX-files and M-files) including: MDCT, fast MDCT, Matching Pursuit in a union of MDCT/MCLT bases, modified Matching Pursuit (pre-echo control, adaptive dictionary), coefficients interleaving, bitplane coding (simple, adaptive). Algorithms are described in the publications "Union of MDCT bases for audio coding" and "Matching Pursuit in adaptive dictionaries for scalable audio coding". The Matching Pursuit functions are based on MPTK (modified version of MPTK 0.5.2).
  

Martin Vetterli, talks about the finite rate of innovation in his ITA'08 talk entitled Sparse Sampling: Variations on a Theme by Shannon. The slides are here (12Mb). The abstract of the presentation reads:

Sampling is not only a beautiful topic in harmonic analysis, with an interesting history, but also a subject with high practical impact, at the heart of signal processing and communications and their applications. The question is very simple: when is there a one-to-one relationship between a continuous-time function and adequately acquired samples of this function?

A cornerstone result is of course Shannon's sampling theorem, which gives a sufficient condition for reconstructing the projection of a signal onto the subspace of bandlimited functions, and this by taking inner products with a sinc function and its shifts. Many variations of this basic framework exist, and they are all related to a subspace structure of the classes of objects that can be sampled.

Recently, this framework has been extended to classes of non-bandlimited sparse signals, which do not have a subspace structure. Perfect reconstruction is possible based on a suitable projection measurement. This gives a sharp result on the sampling and reconstruction of sparse continuous-time signals, namely that 2K measurements are necessary and sufficient to perfectly reconstruct a K-sparse continuous-time signal. In accordance with the principle of parsimony, we call this sampling at Occam's rate.

We first review this result and show that it relies on structured Vandermonde measurement matrices, of which the Fourier matrix is a particular case. It also uses a separation into location and value estimation, the first being non-linear, while the second is linear. Because of this structure, fast, O(K^3) methods exist, and are related to classic algorithms used in spectral estimation and error correction coding. We then generalize these results to a number of cases where sparsity is present, including piecewise polynomial signals, as well as to broad classes of sampling or measurement kernels, including Gaussians and splines.

Of course, real cases always involve noise, and thus, retrieval of sparse signals in noise is considered. That is, is there a stable recovery mechanism, and robust practical algorithms to achieve it. Lower bounds by Cramer-Rao are given, which can also be used to derive uncertainty relations with respect to position and value of sparse signal estimation. Then, a concrete estimation method is given using an iterative algorithm due to Cadzow, and is shown to perform close to optimal over a wide range of signal to noise ratios. This indicates the robustness of such methods, as well as their practicality.

Next, we consider the connection to compressed sensing and compressive sampling, a recent approach involving random measurement matrices, a discrete set up, and retrieval based on convex optimization. These methods have the advantage of unstructured measurement matrices (actually, typically random ones) and therefore a certain universality, at the cost of some redundancy. We compare the two approaches, highlighting differences, similarities, and respective advantages.

Finally, we move to applications of these results, which cover wideband communications, noise removal, and superresolution imaging, to name a few. We conclude by indicating that sampling is alive and well, with new perspectives and many interesting recent results and developments.

This is joint work with Thierry Blu (CUHK), Lionel Coulot, Ali Hormati (EPFL), Pier-Luigi Dragotti (ICL) and Pina Marziliano (NTU).

Francis Bach has some slides of an interesting course entitled learning with sparsity inducing norms given at Ile de Re. Did they have to put the students on an island so they wouldn't escape :)

Ping Li has a talk on Compressed Counting and I am still trying to make sense of it.

The only paper of the list is entitled Separation of stereo speech signals based on a sparse dictionary algorithm by Maria Jafari and Mark Plumbley. The abstract reads:

We address the problem of source separation in echoic and anechoic environments, with a new algorithm which adaptively learns a set of sparse stereo dictionary elements, which are then clustered to identify the original sources. The atom pairs learned by the algorithm are found to capture information about the direction of arrival of the source signals, which allows to determine the clusters. A similar approach is also used here to extend the dictionary learning K singular value decomposition (K-SVD) algorithm, to address the source separation problem, and results from the two methods are compared. Computer simulations indicate that the proposed adaptive sparse stereo dictionary (ASSD) algorithm yields good performance in both anechoic and echoic environments.

Wikimization has a series of compressed sensing related papers and presentations here. Out of the ones I haven't listed before here is a selection:

• Compressed Sensing with Contiguous Fourier Measurements: Presented by Jean-François Mercier with Laurent Demanet and George Papanicolaou at the Applied Mathematics Seminar, Stanford University, July 21, 2008
• Optimization Problems in Compressed Sensing: by Jalal Fadili, CNRS, ENSI Caen France, at the Applied Mathematics Seminar, Stanford University, July 21, 2008
• Compressed Sensing in Astronomy: Presented by Jean-Luc Starck with Jérôme Bobin at the Applied Mathematics Seminar, Stanford University, July 21, 2008

• Highly Undersampled 0-Norm Reconstruction: Presented by Christine Law at Lucas Center for Imaging, Stanford University, July 9, 2008 (771KByte)

• Advances in Compressive Sensing for MRI: Presented by Joshua Trzasko with Armando Manduca at the SIAM Conference on Imaging Science 2008, San Diego, California, July 7, 2008

• Nonconvex Compressive Sensing: Presented by Rick Chartrand with Valentina Staneva, Wotao Yin, & Kevin Vixie at the SIAM Conference on Imaging Science 2008, San Diego, California, July 7, 2008

In the video section of the Wikimization site, I found the following two sets of presentations:

• International Society for Magnetic Resonance in Medicine (ISMRM Toronto 2008), Randy Duensing & Feng Huang (requires Adobe Flash Player): Objective Comparison of Alternate Reconstruction Strategies: An Unmet Need. You need to go to the Wikimization site to find out both the username and password.
• Convex Optimization, Stanford University, Stephen Boyd: Tutorials for a graduate level course, 2008

Finally, there are new versions of the following articles:

• Multi-Task Compressive Sensing with Dirichlet Process Priors by Yuting Qi, Dehong Liu, Lawrence Carin, David Dunson
• Necessary and Sufficient Conditions for Success of the Nuclear Norm Heuristic for Rank Minimization, Benjamin Recht, Weiyu Xu, and Babak Hassibi

credit: Steins as seen by Rosetta
These images of asteroid (2867) Steins were captured during the seven minutes surrounding Rosetta's approach to within 800 kilometers of the asteroid on September 5, 2008. Credit: ESA ©2007 MPS for OSIRIS Team MPS / UPD / LAM / IAA / RSSD / INTA / UPM / DASP / IDA / montage by Emily Lakdawalla