CS: Bayesian CS via Belief Propagation, Iterative Decoding of High-Rate LDPC, DeVore's third lecture, Convex Sparse Matrix Factorizations

Two improved versions have appeared on Arxiv. Both papers have now been submitted for publication:

• Dror let me know about Bayesian Compressive Sensing via Belief Propagation by Dror Baron, Shriram Sarvotham, and Richard Baraniuk.
• On the Iterative Decoding of High-Rate LDPC Codes With Applications in Compressed Sensing by Fan Zhang, Henry Pfister

The Course Notes of the third lecture given by Ron DeVore in Paris has been released on Albert Cohen's page. It features "Capturing Functions in High Dimensions" and seems to aim at giving bounds for nonlinear compressed sensing and should have an impact in manifold signal processing. Interesting. The first two lectures were mentioned here. The beginning of the lecture starts with

1.1 Classifying High Dimensional Functions:

Our last two lectures will study the problem of approximating (or capturing through queries) a function f defined on ⊂ R^N with N very large. The usual way of classifying functions is by smoothness. The more derivatives a function has the nicer it is and the more efficiently it can be numerically approximated. However, as we move into high space dimension, this type of classification will suffer from the so-called curse of dimensionality which we shall now quantify

In other news, in the direction of dictionary learning we have: Convex Sparse Matrix Factorizations by Francis Bach, Julien Mairal, Jean Ponce. The abstract reads:

We present a convex formulation of dictionary learning for sparse signal decomposition. Convexity is obtained by replacing the usual explicit upper bound on the dictionary size by a convex rank-reducing term similar to the trace norm. In particular, our formulation introduces an explicit trade-off between size and sparsity of the decomposition of rectangular matrices. Using a large set of synthetic examples, we compare the estimation abilities of the convex and nonconvex approaches, showing that while the convex formulation has a single local minimum, this may lead in some cases to performance which is inferior to the local minima of the non-convex formulation.

Credit: JAXA, the movie taken by the Kaguya probe as it crashes on the Moon on June 11th, 2009.