CS: Sparse Recovery of Positive Signals with Minimal Expansion, A Numerical Exploration of CS Recovery, Coordinate Descent Optimization

Today we have two presentations and two papers:
A presentation entitled Sparse Recovery of Positive Signals with Minimal Expansion presented by Alex Dimakis, a joint work with M. Amin Khajehnejad , Weiyu Xu, Babak Hassibi. It illustrates part of this paper I mentioned earlier this week ( Sparse Recovery of Positive Signals with Minimal Expansion ). A necessary and sufficient condition for a measurement matrix for positive signals, hmm, this is very interesting. Now we just need to find out a way to say how a given measurement matrix is an expander. More on that later.

Of belated interest is Probabilistic analysis of LP decoding by Alex Dimakis, a joint work with Costas Daskalakis, Richard Karp, Martin Wainwright.

We also have two other papers:

A Numerical Exploration of Compressed Sampling Recovery by Charles Dossal, Gabriel Peyré and Jalal Fadili. The abstract reads:

This paper explores numerically the efficiency of ℓ1 minimization for the recovery of sparse signals from compressed sampling measurements in the noiseless case. Inspired by topological criteria for ℓ1-identifiability, a greedy algorithm computes sparse vectors that are difficult to recover by ℓ1- minimization. We evaluate numerically the theoretical analysis without resorting to Monte-Carlo sampling, which tends to avoid worst case scenarios. This allow one to challenge sparse recovery conditions based on polytope projection and on the restricted isometry property.

Coordinate Descent Optimization for $\ell^1$ Minimization with Application to Compressed Sensing; a Greedy Algorithm by Yingying Li and Stanley Osher. The abstract reads:

We propose a fast algorithm for solving the Basis Pursuit problem, minu{|u|1, : Au = f}, which has application to compressed sensing. We design an efficient method for solving the related unconstrained problem minu E(u) = |u|_1 +λ||Au−f||_2^2 based on a greedy coordinate descent method. We claim that in combination with a Bregman iterative method, our algorithm will achieve a solution with speed and accuracy competitive with some of the leading methods for the basis pursuit problem.

Credit photo: NASA/JPL/Space Science Institute, a new moon of Saturn.