Efficient Band Approximation of Gram Matrices for Large Scale Kernel Methods on GPUs. Hussein, M. & Abd-Almageed, W. In Proceedings of the Conference on High Performance Computing Networking, Storage and Analysis, of SC '09, pages 31:1–31:10, 2009. ACM. event-place: Portland, Oregon
Efficient Band Approximation of Gram Matrices for Large Scale Kernel Methods on GPUs [link]Paper  doi  abstract   bibtex   
Kernel-based methods require O(N2) time and space complexities to compute and store non-sparse Gram matrices, which is prohibitively expensive for large scale problems. We introduce a novel method to approximate a Gram matrix with a band matrix. Our method relies on the locality preserving properties of space filling curves, and the special structure of Gram matrices. Our approach has several important merits. First, it computes only those elements of the Gram matrix that lie within the projected band. Second, it is simple to parallelize. Third, using the special band matrix structure makes it space efficient and GPU-friendly. We developed GPU implementations for the Affinity Propagation (AP) clustering algorithm using both our method and the COO sparse representation. Our band approximation is about 5 times more space efficient and faster to construct than COO. AP gains up to 6x speedup using our method without any degradation in its clustering performance.
@inproceedings{hussein_efficient_2009,
	location = {New York, {NY}, {USA}},
	title = {Efficient Band Approximation of Gram Matrices for Large Scale Kernel Methods on {GPUs}},
	rights = {All rights reserved},
	isbn = {978-1-60558-744-8},
	url = {http://doi.acm.org/10.1145/1654059.1654091},
	doi = {10.1145/1654059.1654091},
	series = {{SC} '09},
	abstract = {Kernel-based methods require O(N2) time and space complexities to compute and store non-sparse Gram matrices, which is prohibitively expensive for large scale problems. We introduce a novel method to approximate a Gram matrix with a band matrix. Our method relies on the locality preserving properties of space filling curves, and the special structure of Gram matrices. Our approach has several important merits. First, it computes only those elements of the Gram matrix that lie within the projected band. Second, it is simple to parallelize. Third, using the special band matrix structure makes it space efficient and {GPU}-friendly. We developed {GPU} implementations for the Affinity Propagation ({AP}) clustering algorithm using both our method and the {COO} sparse representation. Our band approximation is about 5 times more space efficient and faster to construct than {COO}. {AP} gains up to 6x speedup using our method without any degradation in its clustering performance.},
	pages = {31:1--31:10},
	booktitle = {Proceedings of the Conference on High Performance Computing Networking, Storage and Analysis},
	publisher = {{ACM}},
	author = {Hussein, Mohamed and Abd-Almageed, Wael},
	urldate = {2019-05-01},
	year = {2009},
	note = {event-place: Portland, Oregon},
	keywords = {affinity propagation, {GPU}, Gram matrices, kernel methods, space filling curves, sparse matrices},
	file = {ACM Full Text PDF:C\:\\Users\\Mohamed Hussein\\Zotero\\storage\\UP986ZVL\\Hussein and Abd-Almageed - 2009 - Efficient Band Approximation of Gram Matrices for .pdf:application/pdf}
}

Downloads: 0