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

SCAIM Seminar
September 10, 2013 7:30 pm

Speaker:  Irad Yavneh, Technion

Location:  ESB 4133

Intended Audience:  Public

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. (Joint work with Eran Treister)

Some relevant references:
1.            Michael Elad, Sparse and Redundant Representations, From Theory to Applications in Signal and Image Processing, Springer, 2010.
2.            Alfred M. Bruckstein, David L. Donoho, and Michael Elad, “From Sparse Solutions of Systems of Equations to Sparse Modeling of Signals and Images”, SIAM Review, 51 (1), 34–81 (2009)
3.            Eran Treister and Irad Yavneh, “A multilevel iterated-shrinkage approach to L1 penalized least-squares minimization”, IEEE Trans. Sig. Proc., 60 (12) , 6319-6329   (2012)

Irad Yavneh received his B.Sc. degree in Aeronautical Engineering from the Technion in 1984 and his Ph.D. degree in Applied Mathematics from the Weizmann Institute of Science in 1991. He is a Professor at the Faculty of Computer Science, Technion – Israel Institute of Technology. His research interests include multigrid and multiscale computational techniques, scientific computing and computational physics, image processing and analysis, and geophysical fluid dynamics. He is Section Editor of the Computational Methods in Science and Engineering section of the SIAM Journal on Scientific Computing, serves on the editorial board of Numerical Linear Algebra and Applications, and is Program Co-Chair of the Copper Mountain Conference on Multigrid Methods.