KAUST Research Workshop on Optimization and Big Data
Bernard Ghanem is currently an Assistant Professor in the CEMSE division and a theme leader at the Visual Computing Center at KAUST. Before that, he was a Senior Research Scientist at the University of Illinois Urbana-Champaign (UIUC) in Singapore. His research interests lie in computer vision, machine learning, and optimization geared towards real-world applications. He received his Bachelor’s degree from the American University of Beirut (AUB) in 2005 and his MS/PhD in from UIUC in 2010. His work has received several awards and honors, including the Henderson Graduate Award from UIUC, CSE fellowship awards from UIUC, a Best Paper Award (CVPRW 2013), a two-year KAUST Seed Fund, and a Google Faculty Research Award in 2015. He has co-authored more than 50 peer reviewed conference and journal papers in his field.
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.