Implementing two compressed sensing algorithms on GPU

Compressed sensing (CS) is a new branch for information theory from the development of mathematical in 21^st. CS provides a state-of-art technique that we can reconstruct sparse signal from a very limited number of measurements. In CS, reconstruct algorithm often need dense computation. The well-know algorithms like Basis Pursuit (BP) or Matching Pursuit (MP) is not likely to implement in PCs in practice. In this paper, we consider to use GPU (Graphic Processing Unit) and its large-scale computation ability to solve this problem. Based on the recently released NVIDIA CUDA 6.0 Tool Kit and CUBLAS library we study the GPU implementation of Orthogonal Matching Pursuit (OMP), and Two-Step Iterative Shrinkage algorithm (TwIST) implementing on GPU. The result shows that compared with CPU, implementing those algorithms on GPU can get an obvious speed up without losing any accuracy.