Computation and Uses of the Semidiscrete Matrix Decomposition
Abstract
We derive algorithms for computing a semidiscrete approximation to a
matrix in the Frobenius and weighted norms. The approximation is formed
as a weighted sum of outer products of vectors whose elements are plus or
minus $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; and software is provided in C and in
Matlab.
(Also cross-referenced as UMIACS-TR-99-22)