KAUST Research Workshop on Optimization and Big Data
In this talk, I will focus on FFTLasso, a new solver for large scale LASSO problems developed at the Image and Video Understanding Lab (IVUL) at KAUST. The LASSO sparse representation problem has been studied and used in a variety of different areas, ranging from signal processing and information theory to computer vision and machine learning. In the vision community, it found its way into many important applications, including face recognition, tracking, super resolution, image denoising, to name a few. Despite advances in efficient sparse algorithms, solving large-scale LASSO problems remains a challenge. To circumvent this difficulty, people tend to downsample and subsample the problem (e.g. via dimensionality reduction) to maintain a manageable sized LASSO, which usually comes at the cost of losing solution accuracy. FFTLasso is proposed as a novel circulant reformulation of the LASSO that lifts the problem to a higher dimension, where ADMM can be efficiently applied to its dual form. Because of this lifting, all optimization variables are updated using only basic element-wise operations, the most computationally expensive of which is a 1D FFT. In this way, there is no need for a linear system solver nor matrix-vector multiplication. Since all operations in FFTLasso are element-wise in the Fourier domain, the sub-problems are completely independent and can be trivially parallelized (e.g. on one or more GPUs). I will highlight the efficiency gain of FFTLasso on both synthetic and real large-scale data and showcase its use on the face recognition task.