Source-linked AI summary
Optimal approximate matrix product in terms of stable rank
Michael B. Cohen, Jelani Nelson, David P. Woodruff
TL;DR
The paper asks whether spectral-norm approximate matrix multiplication can achieve quadratic ε-dependence while scaling with stable rank rather than a weaker nuclear-rank measure. It obtains this through a black-box reduction from subspace embeddings, yielding optimal oblivious-map bounds and broader applicability to efficient embeddings and deterministic sampling. These guarantees improve analyses of regression and low-rank approximation and support further applications.
Problem
Prior work gave either worse 1/ε dependence with stable rank or quadratic dependence using the weaker nuclear rank, leaving the stable-rank tradeoff unresolved.
Method
The paper characterizes approximate matrix multiplication through subspace-embedding properties and applies those guarantees in a black-box manner, also modifying deterministic BSS row sampling.
Results
m = O((k + log(1/δ))/ε^2) rows suffice for (k, ε, δ)-approximate matrix multiplication, with optimal scaling for oblivious maps; deterministic sampling achieves O(k/ε^2) nonzero rows.
Takeaways & Limitations
The result applies beyond subgaussian maps to SRHT, sparse, and future subspace embeddings, and improves guarantees for generalized regression and low-rank approximation.
Takeaways & Limitations
Some stated applications require additional subspace-embedding conditions, including a 1/2-embedding for the column space of A in generalized regression.
Abstract
from arXiv · showhide
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}/\varepsilon^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}/\varepsilon^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].
1 Introduction
The paper improves spectral-norm approximate matrix multiplication by reducing the required sketch dimension from rank- or nuclear-rank-based bounds to stable-rank-based bounds, while applying broadly to subspace embeddings and related linear-algebra tasks.
- Applications: The guarantees improve or support applications to generalized regression, low-rank approximation, k-means clustering, and nonparametric regression.Approximate matrix multiplication is used as a primitive in analyses of these dimensionality-reduction-based algorithms.
- Main contribution: Quadratic dependence on 1/ε is achievable with stable rank, avoiding the weaker nuclear-rank guarantee required by earlier work.This resolves the main open question identified in prior stable-rank and nuclear-rank analyses.
- Main contribution: m = O((k + log(1/δ))/ε^2) rows suffice for (k, ε, δ)-approximate matrix multiplication, and this scaling is optimal for oblivious maps.The result follows from a black-box connection between oblivious subspace embeddings and approximate matrix multiplication.
- Generality: The theorem transfers established subspace-embedding guarantees to approximate matrix multiplication, including SRHT and sparse subspace embeddings.This black-box formulation also permits future subspace-embedding constructions to inherit the approximate multiplication guarantee.
- Deterministic construction: Deterministic polynomial-time row sampling achieves (k, ε)-approximate matrix multiplication with O(k/ε^2) nonzero sampled rows.This modifies the BSS deterministic sampling argument, replacing rank dependence with the paper’s stable-rank formulation.
2 Analysis of matrix multiplication for stable rank
The paper characterizes when oblivious subspace embeddings yield spectral-norm approximate matrix multiplication, obtaining stable-rank-dependent dimension bounds and instantiations for several sketching families.
- Characterization: An (ε, δ, 2k)-OSE with an appropriate moment property provides (k, ε, δ)-AMM through a black-box theorem.The result extends the connection from OSE moments to operator-norm approximate matrix multiplication.
- Subgaussian maps: Subgaussian maps achieve (k, ε, δ)-AMM with m = Ω((k + log(1/δ))/ε^2) rows.Their OSE moment property supplies the hypothesis of the general theorem.
- SRHT: The SRHT supports AMM with m = Ω((k + log(1/(εδ)) log(k/δ))/ε^2) rows while enabling fast matrix multiplication.The construction uses randomized signs, a bounded orthonormal system, and uniform row sampling.
- Sparse subspace embeddings: Sparse embeddings yield AMM bounds ranging from m = Ω(k^2/(ε^2δ)) to m = Ω(Bk log(k/δ)/ε^2), depending on parameters.The sparse constructions multiply ΠA in time O(s·nnz(A)); constant-sparsity optimal-row conjectures remain open.
- Composition: Composition combines fast preliminary sketches with a subgaussian final map to obtain O(k/ε^2) rows and near-input-sparsity computation.The paper describes a three-stage composition using sparse embeddings, SRHT, and subgaussian maps.
3 Applications
The stable-rank AMM guarantees support generalized regression, low-rank approximation, kernelized ridge regression, and k-means applications.
- Overview: Stable-rank spectral AMM immediately applies to generalized regression and low-rank approximation, with further applications to kernelized ridge regression and k-means clustering.These applications use the AMM guarantee together with subspace-embedding conditions.
- Generalized regression: Generalized regression requires AMM for U_A and the residual P̄_A B plus a subspace embedding for A's column space.The resulting error depends on the residual rather than the fitted component P_A B.
- Low-rank approximation: The low-rank approximation procedure computes a rank-k approximation constrained to the sketch's row space and compares it with the optimal truncated-SVD approximation.The constructed candidate inherits the generalized-regression guarantee while remaining rank k.
- Kernelized ridge regression: Kernelized ridge regression can use AMM for a low-stable-rank matrix B to replace a direct norm analysis, extending the sketching analysis to sparse embeddings.The resulting lower-dimensional solve only requires inversion of an m × m matrix after forming the relevant products.
- k-means clustering: For k-means, the relevant matrix has stable rank at most 3k, so (3k, ε/2)-AMM yields m = O((k + log(1/δ))/ε^2) rows for the stated guarantee.A separate JL moment argument provides the accompanying simpler bound.
4 Stable rank and row selection
The paper extends deterministic BSS row selection from rank to stable rank, giving polynomial-time sampling schemes with O(k/ε^2) selected rows for AMM.
- Stable-rank BSS extension: A stable-rank extension of BSS provides a diagonal sampling matrix with O(k/ε^2) nonzero entries, computable in polynomial time.The construction applies to matrices with normalized spectral norm and Frobenius norm at most k.
- Algorithm: The algorithm maintains Z = (SA)^T(SA) between upper and lower barriers while adding weighted rank-one row contributions.At each step it chooses a row and positive weight preserving the barrier invariants.
- Guarantee: After k/ε^2 steps, the maintained invariants yield the required approximation, with all verification and weight computations executable in polynomial time.The proof follows the BSS barrier-potential argument with modified initialization and potentials.
- AMM corollary: The resulting sampling matrix gives (k, ε)-AMM for arbitrary A and B with n rows.The general AMM corollary follows by applying the theorem to a matrix formed from the columns of A and B.
A OSE moment property
The paper analyzes the OSE moment property for concrete sketching families, including subgaussian matrices and the SRHT.
- OSE moment property: The OSE moment property is established for both subgaussian matrices and the SRHT.
A.1 Subgaussian matrices
This section establishes that JL moment guarantees imply oblivious subspace embedding moment guarantees through a finite covering argument, and applies the result to subgaussian matrices.
- A.1 Subgaussian matrices: A covering and packing argument constructs a γ-net of the unit ball with size at most (1 + 2/γ)^d.The net approximation controls the operator norm of the symmetric embedding error matrix.
- A.1 Subgaussian matrices: JL moment guarantees imply OSE moment guarantees with transformed parameters, using a finite set of at most 9^d test points.The reduction bounds the embedding error on an entire d-dimensional subspace from norm preservation on a finite covering set.
- A.1 Subgaussian matrices: For independent subgaussian entries with variance 1/m, m = Ω(log(1/δ)/ε^2) yields the stated JL moment property.Combining this fact with the JL-to-OSE lemma gives an OSE moment guarantee when δ < 2^-d.
A.2 Subsampled Randomized Hadamard Transform (SRHT)
This section analyzes the SRHT directly through moment bounds and shows that it provides an improved subspace embedding guarantee without conditioning on transformed row norms.
- A.2 Subsampled Randomized Hadamard Transform (SRHT): The SRHT is formed from a randomized Hadamard transform followed by row sampling, with both independent-location and Bernoulli-diagonal sampling variants considered.The latter variant is analyzed for cleaner notation, while the argument also applies essentially unchanged to the former.
- A.2 Subsampled Randomized Hadamard Transform (SRHT): The SRHT provides an ε-subspace embedding for d-dimensional subspaces with failure probability δ using m = O(ε^-2(d + log(1/(εδ))) log(d/δ)) rows.The analysis improves prior bounds in relevant settings by removing log n dependence and supporting inverse-polynomial failure probabilities.
- A.2 Subsampled Randomized Hadamard Transform (SRHT): The SRHT analysis establishes the required OSE moment property using moment inequalities rather than conditioning on small row norms.The proof uses tools including noncommutative Khintchine and Hanson–Wright inequalities to bound the transformed operator.
- A.2 Subsampled Randomized Hadamard Transform (SRHT): The proof bounds moments of the sampled transformed matrix by relating its expected Gram matrix to the identity and controlling Schatten-norm quantities.The analysis introduces transformed rows and uses Hölder, Cauchy–Schwarz, triangle, and AM–GM inequalities.
A.3 Composing dimensionality reducing maps supporting AMM
This section shows that dimensionality-reducing maps supporting AMM can be composed, while controlling the intermediate stable rank and operator norm needed for the final guarantee.
- A.3 Composing dimensionality reducing maps supporting AMM: Composing two maps that each support AMM yields a final map that also supports AMM.This enables combining a fast preliminary embedding with a second map having a more favorable row count.
- A.3 Composing dimensionality reducing maps supporting AMM: A fast map Π2 can reduce dimension first, followed by Π1 with m1 = O(k/ε^2) rows, provided the intermediate stable rank remains comparable to the original.The composition is designed so Π2 supplies fast embedding while Π1 supplies the desired number of rows.
- A.3 Composing dimensionality reducing maps supporting AMM: Conditioning on a small intermediate spectral error gives ∥Π2A∥ = Θ(∥A∥), while a Frobenius error bound gives ˜r′ = Θ(˜r).These relations ensure that the two AMM errors combine to O(ε)∥A∥^2.
- A.3 Composing dimensionality reducing maps supporting AMM: When both component distributions satisfy suitable OSE moment properties, their product itself satisfies an OSE moment property.For A = B, the first map only needs the OSE parameter k rather than 2k.