Pages

Wednesday, September 10, 2008

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:

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


Finally, there are new versions of the following articles:

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

1 comment:

  1. I am on Ile de Re now....arghhh! :)

    Well, although the compund we are somewhat resembles Alcatrazz, it is actually pretty nice here ;)

    Jort

    ReplyDelete