Colloquium | Irad Yavneh, A Multilevel Algorithm for L_1 Minimization with Application to Sparse Representation of Signals

Thursday, September 19, 2013 3:30 pm - 3:30 pm EDT (GMT -04:00)

MC 5158

Speaker

Irad Yavneh, Computer Science, Technion-Israel Institute of Technology

Title

A Multilevel Algorithm for L1 Minimization with Application to Sparse Representation of Signals

Abstract

The area of sparse representation of signals is drawing tremendous attention in recent years in diverse fields of science and engineering. The idea behind the model is that a signal can be approximated as a linear
combination of a few "atoms'' from a pre-specified and over-complete
"dictionary'' (typically represented by columns from a matrix with more
columns than rows). The sparse representation of a signal is often achieved by minimizing an L1 penalized least squares functional. Various
iterative-shrinkage algorithms have recently been developed and are quite effective for handling these problems, often surpassing traditional
optimization techniques. Here we suggest a new iterative multilevel approach that reduces the computational cost of existing solvers for these inverse problems. Our method takes advantage of the typically sparse representation of the signal, and, at each iteration, it adaptively creates and processes a hierarchy of lower-dimensional problems employing well-known iterated shrinkage methods. Analytical observations suggest, and numerical results confirm, that this new approach may significantly enhance the performance of existing iterative shrinkage algorithms in cases where the dictionary is an explicit matrix.
(This is joint work with Eran Treister.)