A Multilevel Approach for l-1 Penalized Least Squares Minimization

The area of sparse approximation of signals is drawing tremendous attention in recent years. Typically, sparse solutions of under-determined linear systems of equations are required. Such solutions are often achieved by minimizing an l-1 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. In this work, 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. Analytic observations suggest, and numerical results confirm, that this new approach may significantly enhance the performance of existing iterative shrinkage algorithms in cases where the matrix is given explicitly.