Cohen, Michael B. ;
Nelson, Jelani ;
Woodruff, David P.
Optimal Approximate Matrix Product in Terms of Stable Rank
Abstract
We prove, using the subspace embedding guarantee in a black box way, that one can achieve the spectral norm guarantee for approximate matrix multiplication with a dimensionalityreducing map having m = O(˜r/epsilon^2) rows. Here r˜ is the maximum stable rank, i.e., the squared ratio of Frobenius and operator norms, of the two matrices being multiplied. This is a quantitative improvement over previous work of [Magen and Zouzias, SODA, 2011] and [Kyrillidis et al., arXiv, 2014] and is also optimal for any oblivious dimensionalityreducing map. Furthermore, due to the black box reliance on the subspace embedding property in our proofs, our theorem can be applied to a much more general class of sketching matrices than what was known before, in addition to achieving better bounds. For example, one can apply our theorem to efficient subspace embeddings such as the Subsampled Randomized Hadamard Transform or sparse subspace embeddings, or even with subspace embedding constructions that may be developed in the future.
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, 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 kmeans clustering, and also implies new results for nonparametric regression.
Lastly, we point out that the proof of the "BSS" deterministic rowsampling result of [Batson et al., SICOMP, 2012] can be modified to obtain deterministic rowsampling for approximate matrix product in terms of the stable rank of the matrices. The original "BSS" proof was in terms of the rank rather than the stable rank.
BibTeX  Entry
@InProceedings{cohen_et_al:LIPIcs:2016:6278,
author = {Michael B. Cohen and Jelani Nelson and David P. Woodruff},
title = {{Optimal Approximate Matrix Product in Terms of Stable Rank}},
booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
pages = {11:111:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770132},
ISSN = {18688969},
year = {2016},
volume = {55},
editor = {Ioannis Chatzigiannakis and Michael Mitzenmacher and Yuval Rabani and Davide Sangiorgi},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6278},
URN = {urn:nbn:de:0030drops62788},
doi = {10.4230/LIPIcs.ICALP.2016.11},
annote = {Keywords: subspace embeddings, approximate matrix multiplication, stable rank, regression, low rank approximation}
}
2016
Keywords: 

subspace embeddings, approximate matrix multiplication, stable rank, regression, low rank approximation 
Seminar: 

43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Issue date: 

2016 
Date of publication: 

2016 