Algorithm 805: Computation and uses of the semidiscrete matrix decomposition

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