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.

Reference:

[1] Compressive Radar Imaging Using White Stochastic Waveforms by Mahesh C. Shastry, Ram M. Narayanan and Muralidhar Rangaswamy.


Credit photo: NASA, from here