
Statistics 2014
Approximate Matrix Multiplication with Application to Linear EmbeddingsAbstract: In this paper, we study the problem of approximately computing the product of two real matrices. In particular, we analyze a dimensionalityreductionbased approximation algorithm due to Sarlos [1], introducing the notion of nuclear rank as the ratio of the nuclear norm over the spectral norm. The presented bound has improved dependence with respect to the approximation error (as compared to previous approaches), whereas the subspace  on which we project the input matrices  has dimensions proportional to the maximum of their nuclear rank and it is independent of the input dimensions. In addition, we provide an application of this result to linear lowdimensional embeddings. Namely, we show that any Euclidean pointset with bounded nuclear rank is amenable to projection onto number of dimensions that is independent of the input dimensionality, while achieving additive error guarantees.
