GPU Accelerated Greedy Algorithms for Compressed Sensing. J.D. Blanchard and J. Tanner; Mathematical Programming Computation, 5(3): 267-304, 2013.
For appropriate matrix ensembles, greedy algorithms have proven to be an efficient means of solving the combinatorial optimization problem associated with compressed sensing. This paper describes an implementation for graphics processing units (GPU) of hard thresholding, iterative hard thresholding, normalized iterative hard thresholding, hard thresholding pursuit, and a two-stage thresholding algorithm based on compressive sampling matching pursuit and subspace pursuit. The GPU acceleration of the former bottleneck, namely the matrix-vector multiplications, transfers a significant portion of the computational burden to the identification of the support set. The software solves high-dimensional problems in fractions of second which permits large-scale testing at dimensions currently unavailable in the literature. The GPU implementations exhibit up to 70x acceleration over standard Matlab central processing unit implementations using automatic multi-threading.
Performance Comparisons of Greedy Algorithms for Compressed Sensing J.D. Blanchard and J. Tanner; Numerical Linear Algebra with Applications, Vol. 22(2) (2015) 254-282.
Compressed sensing has motivated the development of numerous sparse approximation algorithms designed to return a solution to an underdetermined system of linear equations where the solution has the fewest number of nonzeros possible, referred to as the sparsest solution. In the compressed sensing setting, greedy sparse approximation algorithms have been observed to be both able to recovery the sparsest solution for similar problem sizes as other algorithms and to be computationally efficient; however, little theory is known for their average case behavior. We conduct a large scale empirical investigation into the behavior of three of the state of the art greedy algorithms: NIHT, HTP, and CSMPSP. The investigation considers a variety of random classes of linear systems. The regions of the problem size in which each algorithm is able to reliably recovery the sparsest solution is accurately determined, and throughout this region additional performance characteristics are presented. Contrasting the recovery regions and average computational time for each algorithm we present algorithm selection maps which indicate, for each problem size, which algorithm is able to reliably recovery the sparsest vector in the least amount of time. Though no one algorithm is observed to be uniformly superior, NIHT is observed to have an advantageous balance of large recovery region, absolute recovery time, and robustness of these properties to additive noise and for a variety of problem classes. The algorithm selection maps presented here are the first of their kind for compressed sensing.
The development of this software and the performance analysis of NIHT, HTP, and CSMPSP has led to the development of a new algorithm which exploits the computational advantages of these algorithms. The CGIHT family of algorithms is introduced in the following paper along with theoretical, uniform recovery guarantees and extensive empirical testing.
CGIHT: Conjugate Gradient Iterative Hard Thresholding for Compressed Sensing and Matrix Completion J.D. Blanchard, J. Tanner and K. Wei; Information and Inference, Vol. 4(4) (2015) 289-327.
We introduce the conjugate gradient iterative hard thresholding (CGIHT) family of algorithms for the efficient solution of constrained underdetermined linear systems of equations arising in compressed sensing, row-sparse approximation and matrix completion. CGIHT is designed to balance the low per iteration complexity of simple hard thresholding algorithms with the fast asymptotic convergence rate of employing the conjugate gradient method. We establish provable recovery guarantees and stability to noise for variants of CGIHT with sufficient conditions in terms of the restricted isometry constants of the sensing operators. Extensive empirical performance comparisons establish significant computational advantages for CGIHT both in terms of the size of problems, which can be accurately approximated and in terms of overall computation time.
The performance of the algorithms under the model y=Ax+e for a misfit or noise vector e is provided in the following paper:
Conjugate Gradient Iterative Hard Thresholding: observed noise stability in compressed sensing J.D. Blanchard, J. Tanner and K. Wei, IEEE Transactions on Signal Processing, 63(2): 528-537, 2015.
Conjugate gradient iterative hard thresholding (CGIHT) for compressed sensing combines the low per iteration computational cost of simple line search iterative hard thresholding algorithms with the improved convergence rates of more sophisticated sparse approximation algorithms. This paper shows that the average case performance of CGIHT is robust to additive noise well beyond its theoretical worst case guarantees and, in this setting, is typically the fastest iterative hard thresholding algorithm for sparse approximation. Moreover, CGIHT is observed to benefit more than other iterative hard thresholding algorithms when jointly considering multiple sparse vectors whose sparsity patterns coincide.
GPU Accelerated Greedy Algorithms for Compressed Sensing
Copyright 2010-2022 J. Blanchard and J. Tanner
J. Blanchard’s work is supported by the National Science Foundation Grant DMS 1112612. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.