Compressed Sensing: Computation and Relaxation of Conditions for Equivalence between l1 and l0 Minimization, Sparco remark and an addendum.

Here is an update on Computation and Relaxation of Conditions for Equivalence between l1 and l0 Minimization by Allen Yang, John Wright and Yi Ma. The abstract reads

In this paper, we investigate the exact conditions under which the l1 and l0 minimizations arising in the context of sparse error correction or sparse signal reconstruction are equivalent. We present a much simplified condition for verifying equivalence, which leads to a provably correct algorithm that computes the exact sparsity of the error or the signal needed to ensure equivalence. In the case when the encoding matrix is imbalanced, we show how an optimal diagonal rescaling matrix can be computed via linear programming, so that the rescaled system enjoys the widest possible equivalence.

As stated in this interesting paper:

The main contribution of this paper is a simple, novel algorithm for determining when l1-l0 equivalence holds in a given linear system of equations.

I wonder if this type of algorithm should not be included in Sparco. While Sparco wants to be agnostic with regards to the reconstruction solver (so that everyone can use theirs), measurement matrices and other algorithm checking UUP and/or l0-l1 correspondance might add some additional value to the software.

There is also an addendum to the published version of a paper we covered before (Single Pixel Imaging via Compressive Sampling). It reads:

Erratum for "Single Pixel Imaging via Compressive Sampling"

In page 91, paragraph 5 of the appendix, where the paper reads

"...and so each measurement follows a Poisson distribution with mean and
variance (PT/2) for BS and (PTM/2N) for CS."

it should read

"...and so each measurement follows a Poisson distribution with mean and
variance (PT/2) for BS and (PTN/2M) for CS."

Image courtesy: NASA/JPL-Caltech/Cornell/ASU/Texas A&M/Navigation camera, Opportunity rover camera watching Martian clouds.