GPU accelerated greedy algorithms for compressed sensing

被引：24

作者：

Blanchard J.D. ^{[1
]}

Tanner J. ^{[2
]}

机构：

[1] Department of Mathematics and Statistics, Grinnell College, Grinnell

[2] Mathematics Institute, University of Oxford

来源：

Mathematical Programming Computation | 2013年 / 5卷 / 3期

基金：

美国国家科学基金会;

关键词：

Combinatorial optimization; Compressed sensing; CoSaMP; Graphics processing units; Greedy algorithms; HTP; IHT; NIHT; Parallel computing; Sparse approximation; Subspace pursuit;

D O I：

10.1007/s12532-013-0056-5

中图分类号：

学科分类号：

摘要：

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 a second which permits large-scale testing at dimensions currently unavailable in the literature. The GPU implementations exhibit up to 70× acceleration over standard Matlab central processing unit implementations using automatic multi-threading. © Springer-Verlag Berlin Heidelberg and Mathematical Optimization Society 2013.

引用

页码：267 / 304

页数：37

共 36 条

[1]

Alabi T., Blanchard J., Gordon B., Steinbach R., Fast k-selection algorithms for graphics processing units, ACM J. Exp. Algorithmics, 17, 2, pp. 421-4229, (2012)

[2]

Allison D., Noga M., Selection by distributive partitioning, Inf. Process. Lett., 11, 1, pp. 7-8, (1980)

[3]

Beliakov G., Parallel calculation of the median and order statistics on GPUs with application to robust regression, Computing Research Repository, (2011)

[4]

Berg E.V.D., Friedlander M.P., Probing the Pareto frontier for basis pursuit solutions, SIAM J. Sci. Comput., 31, 2, pp. 890-912, (2008)

[5]

Blanchard J.D., Tanner J., GAGA: GPU Accelerated Greedy Algorithms, (2013)

[6]

Blanchard J.D., Tanner J., Performance Comparisons of Greedy Algorithms in Compressed Sensing, (2013)

[7]

Blumensath T., Davies M.E., Iterative hard thresholding for compressed sensing, Appl. Comput. Harmon. Anal., 27, 3, pp. 265-274, (2009)

[8]

Blumensath T., Davies M.E., Normalised iterative hard thresholding

[9]

Guaranteed stability and performance, IEEE Select. Topics Signal Process., 4, 2, pp. 298-309, (2010)

[10]

Candes E.J., Compressive sampling, International Congress of Mathematicians, 3, pp. 1433-1452, (2006)

← 1 2 3 4 →