Invited Session Wed.1.H 1028

Wednesday, 10:30 - 12:00 h, Room: H 1028

Cluster 21: Sparse optimization & compressed sensing [...]

Algorithms for sparse optimization II


Chair: Kimon Fountoulakis



Wednesday, 10:30 - 10:55 h, Room: H 1028, Talk 1

Kimon Fountoulakis
Matrix-free interior point method for compressed sensing problems

Coauthors: Jacek Gondzio, Pavel Zhlobich


We consider the class of l1-regularization methods
for sparse signal reconstruction from the field of Compressed
Sensing. Such problems are very well conditioned and, indeed,
can be solved easily by first-order methods, such as,
{\tt GPSR, FPC\AS, SPGL1, NestA}.
Interior point methods rely on second-order information.
They have many advantageous features and one clear drawback:
in general, the solution of a Newton's system has
computational complexity O(n3).
We remove this disadvantage by employing the matrix-free
interior point method with suitable preconditioners which
cleverly exploit special features of compressed sensing
problems. Spectral analysis of the preconditioners is presented.
Computational experience with large-scale one-dimensional
signals (n=220) confirms that the new approach is efficient
and compares favourably with other state-of-the-art solvers.



Wednesday, 11:00 - 11:25 h, Room: H 1028, Talk 2

Xiangfeng Wang
Linearized alternating direction methods for Dantzig selector

Coauthor: Xiaoming Yuan


The Dantzig selector was recently proposed to perform variable selection and model fitting in the linear regression model, and it can be solved numerically by the alternating direction method (ADM). In this paper, we show that the ADM for Dantzig selector can be speeded up significantly if one of its resulting subproblems at each iteration is linearized. The resulting linearized ADMs for Dantzig selector are shown to be globally convergent, and their efficiency is verified numerically by both simulation and real world data-sets.



Wednesday, 11:30 - 11:55 h, Room: H 1028, Talk 3

Sergey Voronin
Iteratively reweighted least squares methods for structured sparse regularization


We describe two new algorithms useful for obtaining sparse regularized solutions to large inverse problems, based on the idea of reweighted least squares.
We start from the standpoint of l1 minimization, and show
that by replacing the non-smooth one norm ||x||1 = ∑k=1N |xk| with a reweighted two norm: k=1N wk x2k, with the weights being refined at each successive iteration, we can formulate two new algorithms with good numerical performance.
We then discuss a generalization of both variants, useful
in cases of structured sparsity, where different sets of coefficients demand different treatment. We discuss in particular, an example from a large inverse problem from Geotomography, where Wavelets
are used to promote sparsity. We show that to build up a solution from a dictionary of different Wavelet bases and to have control over the different components of each Wavelet basis, the minimization of a more general functional:
||Ax - b||22 + ∑k=1N λ k |xk|qk for 1 ≤ qk < 2 is desirable. We show that our proposed schemes extend to this more general case.


  The deal is that Indiana Loans Online online can save your time, nerves and make a solution of all your financial problems. On the global pharmaceutical market this medicine was issued in 2003 by two companies - Eli Lilly and ICOS. Initially, permission to sell Cialis was obtained in Europe, Australia, New Zealand.