Kimonas Fountoulakis (University of Edinburgh)

LPs in Compressed Sensing
Wednesday 2 November 2011 at 15.30, JCMB 6206

Abstract

Classical sampling theorems (Nyquist, Shannon, Kotelnikov) state that exact reconstruction from a sampled signal is achieved if the sampling rate is double as the bandwidth of the signal. On the contrary, recent advances on the field of Signal Processing revealed that such a high rate is unnecessary under the condition that the signal is known a-priori to have a sparse representation. Signals with such a property can be undersampled and still allow an exact reconstruction of the sparsest representation, consequently exact reconstruction of the signal. This new field of undersampling methods is named Compressed Sensing/Compressive Sampling (CS). The name originates from the fact that a fraction of the signal is directly acquired rather than acquiring the whole signal and then discarding the smallest elements of its sparsest representation. Reconstruction algorithms which solve the linearized L1-norm (Basis Pursuit) program are employed to provide the exact sparsest solution of the incomplete systems that arise from the field of CS. Compressed Sensing programs lead to very well conditioned optimization problems and therefore can be solved easily by simple first-order methods. To the best of our knowledge, there is no second-order method which can be as efficient as the first order methods on CS programs. We demonstrate that a second-order method such as an interior point algorithm can be specialized for such problems and offer a competitive alternative to the existing approaches. Computational experience on large scale one-dimensional discrete signals (n = 2^18) confirms that the new approach is efficient and compares favourably with other state-of-the-art solvers.