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 dimensionality-reducing map having $m=O(\tilde{r}/{\epsilon }^2)$ rows. Here $\tilde{r}$ is the maximum stable rank, i.e. squared ratio of Frobenius and operator norms, of the two matrices being multiplied. This is a quantitative improvement over previous work of [MZ11, KVZ14], and is also optimal for any oblivious dimensionality-reducing 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 shown in prior work, implies quantitative improvements for approximate least squares regression and low rank approximation. Our main result has also already been applied to improve dimensionality reduction guarantees for $k$-means clustering [CEMMP14], and implies new results for nonparametric regression [YPW15]. We also separately point out 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 most $\tilde{r}$, one can achieve the spectral norm guarantee for approximate matrix multiplication of $A^{T}B$ by deterministically sampling $O(\tilde{r}/{\epsilon }^2)$ rows that 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].

v3: minor edits; v2: fixed one step in proof of Theorem 9 which was wrong by a constant factor (see the new Lemma 5 and its use; final theorem unaffected)

References in corpus (3)

• Improved Distributed Principal Component Analysis
• Randomized sketches for kernels: Fast and optimal non-parametric regression
• New Probabilistic Bounds on Eigenvalues and Eigenvectors of Random Kernel Matrices

Cited by in corpus (23)

• Sketching as a Tool for Numerical Linear Algebra
• The Singular Value Decomposition, Applications and Beyond
• Streaming PCA: Matching Matrix Bernstein and Near-Optimal Finite Sample Guarantees for Oja's Algorithm
• Dimensionality Reduction for k-Means Clustering and Low Rank Approximation
• Robust high dimensional factor models with applications to statistical machine learning
• Co-Occuring Directions Sketching for Approximate Matrix Multiply
• Faster PAC Learning and Smaller Coresets via Smoothed Analysis
• Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra
• Compressed Deep Networks: Goodbye SVD, Hello Robust Low-Rank Approximation
• Sharper Bounds for Regularized Data Fitting
• A Simple Approach to Optimal CUR Decomposition
• On the Convergence of Inexact Predictor-Corrector Methods for Linear Programming
• Almost Optimal Tensor Sketch
• Localized sketching for matrix multiplication and ridge regression
• Matrix Norms in Data Streams: Faster, Multi-Pass and Row-Order
• Adaptive Newton Sketch: Linear-time Optimization with Quadratic Convergence and Effective Hessian Dimensionality
• Optimal Sampling Algorithms for Block Matrix Multiplication
• Efficient Non-oblivious Randomized Reduction for Risk Minimization with Improved Excess Risk Guarantee
• Efficient Anomaly Detection via Matrix Sketching
• Random Sampling for Distributed Coded Matrix Multiplication
• Sparse Coresets for SVD on Infinite Streams
• Non-PSD Matrix Sketching with Applications to Regression and Optimization
• Faster Projective Clustering Approximation of Big Data