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

Achal Shah, Angshul Majumdar
Indian Institute of Technology, Guwahati
IEEE International Symposium on Signal Processing and Information Technology (ISSPIT 2014), 2014


   title={Sparse Recovery on GPUs: Accelerating the Iterative Soft-Thresholding Algorithm},

   author={Shah, Achal and Majumdar, Angshul},



Download Download (PDF)   View View   Source Source   



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.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2018 hgpu.org

All rights belong to the respective authors

Contact us: