K. Fountoulakis, J. Gondzio, P. Zhlobich
Abstract
We consider a class of optimization problems for sparse signal
reconstruction which arise in the field of Compressed Sensing
(CS). A plethora of approaches and solvers exist
for such problems, for example GPSR, FPC_AS, SPGL1,
NestA, l_1-l_s, PDCO to mention a few.
Compressed Sensing applications lead to very well conditioned
optimization problems and therefore can be solved easily by simple
first-order methods.
Interior point methods (IPMs) rely on the Newton method hence they use
the second-order information. They have numerous advantageous features
and one clear drawback: being the second-order approach they need
to solve linear equations and this operation has (in the general
dense case) an $\mathcal{O}(n^3)$ computational complexity. Attempts
have been made to specialize IPMs to sparse reconstruction problems
and they have led to interesting developments implemented in
l_1-l_s and PDCO softwares. We go a few steps
further. First, we use the matrix-free interior point method,
an approach which redesigns IPM to avoid the need to explicitly
formulate (and store) the Newton equation systems. Secondly, we exploit
the special features of the signal processing matrices within
the matrix-free IPM. Two such features are of particular interest:
an excellent conditioning of these matrices and the ability to perform
inexpensive (low complexity) matrix-vector multiplications with them.
Computational experience with large scale one-dimensional
signals ($n=2^{20}$) confirms that the new approach is efficient
and compares favorably with other state-of-the-art solvers.
Key words: Matrix-free Interior Point, Preconditioned Conjugate Gradient, Compressed Sensing, Compressive Sampling, l_1-regularization.