Algorithm 805: Computation and Uses of the Semidiscrete Matrix Decomposition

Abstract

We present algorithms for computing a semidiscrete approximation to a matrix in a weighted norm, with the Frobenius norm as a special case. The approximation is formed as a weighted sum of outer products of vectors whose elements are +/- 1 or 0, so the storage required by the approximation is quite small. We also present a related algorithm for approximation of a tensor. Applications of the algorithms are presented to data compression, filtering, and information retrieval; software is provided in C and in Matlab.

Publication
ACM Transactions on Mathematical Software
Date
Citation
T. G. Kolda, D. P. O’Leary. Algorithm 805: Computation and Uses of the Semidiscrete Matrix Decomposition. ACM Transactions on Mathematical Software, Vol. 26, No. 3, pp. 415-435, 2000. https://doi.org/10.1145/358407.358424

Keywords

compression, latent semantic indexing, matrix decomposition, semidiscrete decomposition (SDD), singular value decomposition (SVD)

Comments

The published version has several typographical errors. You may wish instead to check the older version.

BibTeX

@article{KoOl00,  
author = {Tamara G. Kolda and Dianne P. O'Leary}, 
title = {Algorithm 805: Computation and Uses of the Semidiscrete Matrix Decomposition}, 
journal = {ACM Transactions on Mathematical Software}, 
volume = {26}, 
number = {3}, 
pages = {415--435}, 
month = {September}, 
year = {2000},
doi = {10.1145/358407.358424},
}