GAGA: GPU Accelerated Greedy Algorithms
by Jeffrey D. Blanchard and Jared Tanner
with contributions from Ke Wei and Rodrigo Mendoza-Smith
  • Home
  • Get GAGA
  • License
  • Research
  • Register
  • Download GAGA

GPU Accelerate Greedy Algorithms for Compressed Sensing

New Release: GAGA 1.2.0, October 2015

Welcome to GAGA, a software package for solving large compressed sensing problems with millions of unknowns in fractions of a second by exploiting the power of graphics processing units.  The current release GAGA 1.2.0 consists of ten greedy algorithms using five matrix ensembles and six algorithms tailored for use with expander matrices.  This release is set to compile as Matlab executables to enhance your compressed sensing research and applications.  A user guide is available for download detailing the capabilities including simple implementations for large-scale testing at problem sizes previously too computationally expensive for extensive testing.
The current version, GAGA 1.2.0, contains ten greedy algorithms for compressed sensing with three clases of matrix multiplication, generic dense matrices, sparse matrices, and the subsampled discrete cosine transform. New to GAGA 1.2.0 are six algorithms specificaly designed for the compressed sensing problem with expander matrices. For large-scale testing, there are a total of five randomly generated matrix ensembles and three randomly generated sparse vector ensembles. For applications, the algorithms are equipped to employ any dense matrix and any sparse matrix in COO format (the default in Matlab). GAGA provides massive acceleration with up to 70x speed-ups in the algorithms' subroutines over a CPU based matlab implementation. For large scale testing, the GPU based random problem generation can offer up to 1600x acceleration.

Greedy Algorithms

Conjugate Gradient Iterative Hard Thresholding (3 variants)
Normalized Iterative Hard Thresholding
Fast Iterative Hard Thresholding
Iterative Hard Thresholding
Hard Thresholding Pursuit
CSMPSP: CoSaMP/Subspace Pursuit
1-ALPS(2)
Thresholding

Expander Algorithms

Serial L0
Parallel L0
Expander Recovery
Sparse Matching Pursuit
Sequential Sparse Matching Pursuit
Parallel LDDSR

Random Matrix Ensembles

Dense Gaussian Matrices
Dense Binary Matrices
Sparse Binary Matrices
Sparse Expander Matrices
Subsampled Discrete Cosine Transform

Random Sparse Vector Ensembles

Sparse Binary Vectors
Sparse Gaussian Vectors
Sparse Uniform Vectors
GPU Accelerated Greedy Algorithms for Compressed Sensing
Copyright 2010-2015 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.
Web Hosting by iPage
Photo used under Creative Commons from Riebart