### 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.