Randomized Thoughts and Feedbacks

I bugged Laurent Duval to remind me about a similarity measure between images as I think we too often forget that RSME for image reconstruction is not optimal. Laurent kindly obliged and pointed me to the Structural similarity Index (several implementations of this similarity index can be found here). The initial paper is here.( Image Quality Assessment: From Error Visibility to Structural Similarity, Zhou Wang, Alan C. Bovik, Hamid R. Sheikh and Eero P. Simoncelli). Here is a more recent improvement. 

Thanks Laurent.

John Baez explores the barrier of complexity through some examples from the demoscene. This type of discussion is tangential to the type of discussion we are having so far when it comes to simple/low entropy solutions. In effect, while these little movies are encoded in small codes.they produce amazingly complex scenes, scenes which we might have guessed to be high entropy in the first place. How does this fit in problem 8 of Muthu's functional compressive sensing ?  I don't know. 

Bob let us know about a paper that is not making it through peer-review, Dirk describes semi-continuous nonnegative sparse reconstruction and compressed sensing, Zhilin let us know about other's work and Danny is probably looking for that one person who could implement a randomized PCA using sparse matrices for a future implementation in GraphLab. I came across a paper that I don't think I featured before Simultaneously Sparse Solutions to Linear Inverse Problems with Multiple System Matrices and a Single Observation Vector by Adam Zelinski, Vivek Goyal, Elfar Adalsteinsson and think that this framework might fit perfectly with the Boogie Woogie Grid, we'll see. In another direction I wonder if Low Rank matrix factorization might not be useful for both Earthquake source location and Femtosecond Transient Imaging, here again we'll see.

Finally, after featuring the new solver EM-BG-AMP by Jeremy Vila and Phil Schniter, Florent Krzakala, Marc Mézard, François Sausset,Yifan Sun and Lenka Zdeborová sent me the following:

We saw your post today on Nuit Blanche and we just want to point out that the EM-BG-AMP is included in our approach: that is exactly what we call EM-BP (there may be some minor irrelevant differences in initializations etc, but the core of the algorithm is the same). Theoretical () replica analysis of its performance gives the line called "BP" in the plots we sent you and that you show in
  http://nuit-blanche.blogspot.com/2011/09/stunning-development-in-breaking-donoho.html

If I could summarize our work, we have 3 main points:

1. We prove that exact sampling with a Gaussian-Bernoulli prior gives an exact reconstruction of a sparse signal, up to K=M, irrespective of the original signal distribution. This is a very strong lemma.
2. We then use the EM-BP algorithm, with learning of all parameters (including noise if needed), in order to perform an approximate sampling. This is giving a very good algorithm, superior in some case to the L1 minimization. However, EM-BP does not sample correctly beyond a phase transition that depends on the signal (this is the "BP" phase transition in the plots we sent you).
3. In order to circumvent this problem with BP not being good enough, we introduce the seeded matrix F for which BP samples correctly up to K=M. However note a crucial property, that if one wants to use seeded matrix, one really needs EM-BP in the first place (seeded matrix will not give better performance with most other reconstruction algorithms).

Great so now using Jeremy Vila and Phil Schniter's EM-BG-AMP solver with the banded matrices described in Florent Krzakala, Marc Mézard, François Sausset,Yifan Sun and Lenka Zdeborová's Statistical physics-based reconstruction in compressed sensing should allow one to reproduce these K=M graphs. While we are on the subject of coding theory and its application in compressive sensing through the use of banded matrices, here is a paper that appeared on my radar screen:

Compressed sensing via node-based verification recovery with band sparse matrices by Yuko Sato, Kenta Kasai, Kohichi Sakaniwa. The abstract reads:

We consider compressed sensing via node-based veri fication recovery with band sparse matrices. We observed that recovery performance of compressed sensing with band sparse measurement matrices is better than sparse measurement matrices.

I don't read Japanese that well, but if somebody does and finds something interesting please me know. Let us note that the utilization of figure of merit not traditionally used in compressive sensing makes it difficult to find out whether the approach is interesting. Kenta tells me that a translation should be available by January 2012.

.

Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.