Optimal Approximate Matrix Product in Terms of Stable Rank

DOI10.4230/LIPICS.ICALP.2016.11MaRDI QIDQ4598143zbMATH OpenOpenAlexFDO

Authors Michael B. Cohen, Jelani Nelson, David P. Woodruff

Publication date 19 December 2017

Full work available at URL https://arxiv.org/abs/1507.02268

zbMATH Keywords

approximate matrix multiplicationlow rank approximationregressionstable ranksubspace embeddings

Mathematics Subject Classification ID

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(ilder/varepsilo{n}^2)$ rows. Here $ilder$ 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 $ilder$, one can achieve the spectral norm guarantee for approximate matrix multiplication of $A^{T}B$ by deterministically sampling $O(ilder/varepsilo{n}^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].

Recommendations

• On best rank \(n\) matrix approximations
• On the Best Approximation of the Hierarchical Matrix Product
• scientific article; zbMATH DE number 756190
• On optimality of approximate low rank solutions of large-scale matrix equations
• Generalized Rank-Constrained Matrix Approximations
• Rank constrained matrix best approximation problem
• Accurate solutions of product linear systems associated with rank-structured matrices
• scientific article; zbMATH DE number 3945129
• A cross-product approach for low-rank approximations of large matrices
• Strongly stable rank and applications to matrix completion

Cited in

(20)

• Robust high-dimensional factor models with applications to statistical machine learning
• Bootstrapping the operator norm in high dimensions: error estimation for covariance matrices and sketching
• Turning Big Data Into Tiny Data: Constant-Size Coresets for $k$-Means, PCA, and Projective Clustering
• Faster kernel ridge regression using sketching and preconditioning
• Practical sketching algorithms for low-rank matrix approximation
• Sharper bounds for regularized data fitting
• Performance of Johnson--Lindenstrauss Transform for $k$-Means and $k$-Medians Clustering
• Finding low-rank solutions via nonconvex matrix factorization, efficiently and provably
• Low rank matrix-valued Chernoff bounds and approximate matrix multiplication
• Sketching for principal component regression
• scientific article; zbMATH DE number 7651209 (Why is no real title available?)
• M-IHS: an accelerated randomized preconditioning method avoiding costly matrix decompositions
• Optimal sampling algorithms for block matrix multiplication
• An Improved Analysis and Unified Perspective on Deterministic and Randomized Low-Rank Matrix Approximation
• Randomized Nyström Preconditioning
• Optimal eigenvalue approximation via sketching
• Random projections for linear programming: an improved retrieval phase
• Turning big data into tiny data: coresets for unsupervised learning problems
• Efficient algorithms for Tucker decomposition via approximate matrix multiplication
• Subspace embedding with random Khatri-Rao products and its application to eigensolvers

This page was built for publication: Optimal Approximate Matrix Product in Terms of Stable Rank

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4598143)