Sparse Recovery on GPUs: Accelerating the Iterative Soft-Thresholding Algorithm

Solving linear inverse problems where the solution is known to be sparse is of interest to both signal processing and machine learning research. The standard algorithms for solving such problems are sequential in nature - they tend to be slow for large scale problems. In the past, researchers have used Graphics Processing Units to accelerate such algorithms. But these acceleration schemes were trivial - speed-ups were achieved by computing the matrix vector products on a GPU. In this work, we propose a novel technique to accelerate a popular recovery algorithm (Iterative Soft Thresholding Algorithm - ISTA). The computational bottleneck in ISTA is in computing the gradient in every iteration. We accelerate this step by efficiently computing the gradient numerically via inexpensive updates that can be easily parallelized on the GPU. Experimental results show that the proposed method can achieve more than an order of magnitude improvement, even for moderate sized problems.