Wednesday, March 23, 2011

CS: Multiplicative Noise Effect on the Donoho-Tanner Phase Transition (Part 1)

In the course of evaluating an experimental system, one is often faced with some uncertainties on the coefficients of the measurement matrix. While some the work in the literature is focused on additive noise [1], we believe it is not the most appropriate way of figuring out how a compressive sensing system is really behaving. In our approach, multiplicative noise is instantiated as a random matrix E. A is the measurement matrix of interest. We are looking at solving the following linear system:

y = (A + E) x

Out approach goes as follows: We first take a random x, produce Ax = y and then solve for x in y_1 = (A + E)x. We then counted the number of times the y and y_1 were different above a certain small value. If E is the zero matrix, then we ought to have obtain the Donoho-Tanner transition curve. Our interest is evaluating how large ||E|| must be before the DT transition becomes inexistent. We are interested in seeing not just the effect of the noise level but also how Basis Pursuit or a LASSO approach perform on this transition. Of educational interest is the evaluation of DT phase transition with the traditional Least Square solver.

More on that tomorrow.



Bob et Carla said...

Hi Igor. You might want to take a look at this paper:

Herman, M.A.; Strohmer, T.; , "General Deviants: An Analysis of Perturbations in Compressed Sensing," Selected Topics in Signal Processing, IEEE Journal of , vol.4, no.2, pp.342-349, April 2010
doi: 10.1109/JSTSP.2009.2039170

Igor said...

Bob, thanks for the pointer. It's after reading this paper and other that I got started thinking this was an issue. I need to put some of these references in the introduction no doubt.