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)