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

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 L¹ 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.)