Approximate Matrix Multiplication with Application to Linear Embeddings
This work addresses computational efficiency in matrix operations for applications like embeddings, but it is incremental as it builds on prior methods with specific improvements.
The paper tackles the problem of approximating matrix multiplication by analyzing a dimensionality-reduction algorithm, improving the error dependence and showing that projection dimensions depend on nuclear rank rather than input size. It applies this to linear embeddings, proving that point-sets with bounded nuclear rank can be projected to a dimension-independent number of dimensions with additive error guarantees.
In this paper, we study the problem of approximately computing the product of two real matrices. In particular, we analyze a dimensionality-reduction-based 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 low-dimensional embeddings. Namely, we show that any Euclidean point-set with bounded nuclear rank is amenable to projection onto number of dimensions that is independent of the input dimensionality, while achieving additive error guarantees.