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.
compression, latent semantic indexing, matrix decomposition, semidiscrete decomposition (SDD), singular value decomposition (SVD)
The published version has several typographical errors. You may wish instead to check the older version.
@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},
}