We give two different characterizations of the type of dimensionality-reducing map Π that can be used for spectral error approximate matrix multiplication (AMM). Both imply a random data-oblivious Π with m = O(r/ε 2 ) rows suffices, wherer is the maximum stable rank, i.e. squared ratio of Frobenius and operator norms, of the matrices being multiplied. This answers the main open question of [MZ11, KVZ14] , and is optimal for any random oblivious map. Both characterizations apply to a general class of random Π, and one even to deterministic Π. where the columns of U form an orthonormal basis for E. In one characterization, we show if this tail bound was established via the moment method, then to obtain AMM it suffices that D be an (ε, δ, 2r)-OSE. That is, we show being an OSE for dimension (i.e. rank) k implies black box AMM for matrices of stable rank k. Once this is shown, our main result is then just a simple corollary of the fact that subgaussian maps with m = Ω((d + log(1/δ))/ε 2 ) rows are (ε, δ, d)-OSE's. Also, for all known OSE's, the best analyses indeed are via the moment method (or tools such as matrix Chernoff, which themselves also imply moment bounds). Thus our theorem can be applied to a much more general class of sketching matrices than just the subgaussian sketches in [MZ11, KVZ14], in addition to achieving better bounds. This includes fast subspace embeddings such as the Subsampled Randomized Hadamard Transform [Sar06, LWM + 07] or sparse subspace embeddings [CW13, MM13, NN13, Coh16], or even constructions that may be developed in the future, to show that rank bounds in their analyses in previous work can automatically be replaced with stable rank. Our second characterization identifies certain deterministic conditions which if satisfied imply the AMM guarantee. We show these conditions are sufficiently precise to yield optimal results for subgaussian maps and even a deterministic Π such as the truncated SVD. Our main theorem, via connections with spectral error matrix multiplication proven in previous work, implies quantitative improvements for approximate least squares regression and low rank approximation [Sar06] , and implies faster low rank approximation for popular kernels in machine learning such as the gaussian and Sobolev kernels. Our main result has also already been applied to improve dimensionality reduction guarantees for k-means clustering [CEM + 15], and also implies new results for nonparametric regression when combined with results in [YPW15] . Lastly, we point out a minor but interesting observation that the proof of the "BSS" deterministic row-sampling result of [BSS12] can be modified to show that for any matrices A, B of stable rank at mostr, one can achieve the spectral norm guarantee for approximate matrix multiplication of A T B using a deterministic sampling matrix with O(r/ε 2 ) non-zero entries which can be found in polynomial time. The original result of [BSS12] was for rank instead of stable rank. Our observation leads to a stronger version of a main theorem of [KMST10]. * MIT. micohen@mit.edu.
Recently, Cohen et al. REF further improve the dependence on ǫ and give a bound of O(r/ǫ 2 ), wherer is the maximum stable rank.
Optimal approximate matrix product in terms of stable rank
ArXiv
ArXiv
Computer Science Mathematics