Source-linked AI summary
A Tight Analysis of Khatri-Rao Oblivious Subspace Embeddings
Lorenzo Beretta, Cameron Musco
TL;DR
Khatri-Rao sketches enable fast tensor-structured computation, but existing oblivious subspace embedding bounds have weaker dependence on subspace dimension than unstructured sketches. This work uses independence, isotropy, a weak Johnson-Lindenstrauss moment property, and matrix Chernoff bounds to obtain nearly linear dependence on k for any fixed order d.
Problem
Existing Khatri-Rao oblivious subspace embedding bounds lag behind unstructured sketches, despite their computational advantages for tensor-structured inputs.
Method
The proof combines independent isotropic Khatri-Rao columns, a weak Johnson-Lindenstrauss moment property, and a standard matrix Chernoff bound.
Results
For any fixed order d, Khatri-Rao sketches achieve oblivious subspace embeddings with nearly linear dependence on the subspace dimension k.
Takeaways & Limitations
Khatri-Rao sketches nearly match unstructured sketches in subspace-dimension dependence while retaining fast computation for tensor-structured inputs.
Takeaways & Limitations
The proof requires a truncation argument because its bound depends on a uniform bound on the spectral radius of all z_i z_i^T terms.
Abstract
from arXiv · showhide
We study random sketching matrices with Khatri-Rao structure. In particular, we consider the Khatri-Rao product (i.e., column-wise tensor product) $A_1\odot\cdots\odot A_d \in \mathbb R^{(n_1 \cdots n_d) \times m}$ of random matrices $A_i \in \mathbb R^{n_i \times m}$ whose columns are isotropic, independent and sub-Gaussian (e.g., Gaussian matrices). Khatri-Rao sketching matrices are widely applied in randomized algorithms for linear algebraic computation and data analysis, when the input data has tensor structure that allows for fast multiplication with $A_1\odot\cdots\odot A_d$. However, existing theory is not able to fully explain their performance in practice. In particular, despite significant attention, our best bounds for the important \emph{oblivious subspace embedding} property with Khatri-Rao matrices lag behind what is achievable with standard unstructured matrices. For embedding a $k$-dimensional subspace to $(1\pm ε)$ error, Bujanović et al. \cite{bujanovic2025subspace} prove that sketching dimension $m = O(k^{3/2}/ε^2)$ suffices in the special case of $d = 2$. Their dependence on $k$ is weaker than the tight bound of $O(k/ε^2)$ known for unstructured sub-Gaussian sketching matrices. In this work, we close this gap, showing that $m = \tilde O(k/ε^2)$ suffices for subspace embedding with a Khatri-Rao sketching matrix with any fixed order $d$. Our proof is simple, leveraging just two basic properties of the Khatri-Rao sketching distribution: 1) the columns of $A_1\odot\cdots\odot A_d \in \mathbb R^{(n_1 \cdots n_d) \times m}$ are independent and isotropic, and 2) each column of $A_1\odot\cdots\odot A_d \in \mathbb R^{(n_1 \cdots n_d) \times m}$ satisfies a weak Johnson-Lindenstrauss type moment property.
1 Introduction
The paper shows that Khatri-Rao sketches achieve nearly linear dependence on subspace dimension for oblivious subspace embeddings, nearly matching unstructured sketches. The proof combines independent isotropic columns, a weak Johnson-Lindenstrauss moment property, and matrix Chernoff concentration.
- 1 Introduction: The sketch is formed as Ψ = 1/√m A_1 ⊙···⊙ A_d from matrices with independent sub-Gaussian columns, including independent standard Gaussian matrices.The columns are assumed independent, isotropic, and have constant sub-Gaussian norm.
- 1 Introduction: Khatri-Rao sketches support fast tensor-structured multiplication, reducing cost to O((n_1+···+n_d)·dm) versus O(n_1···n_d)·dm for dense projections.This represents an exponential savings in cost.
- 1 Introduction: The main result achieves oblivious subspace embeddings with nearly linear dependence on the subspace dimension k, resolving the prior gap with unstructured sketches.The paper states that m = tilde O(k/ε^2) suffices for fixed order d.
- 1 Introduction: For d = 2, the bound replaces a k factor with log(k)^3, while for d > 2 it replaces k^d with k log(k)^(d+1).These improvements are stated for fixed ε and δ.
- 1 Introduction: The proof uses independent isotropic Khatri-Rao columns, a weak Johnson-Lindenstrauss moment bound, and a standard matrix Chernoff inequality.The moment bound controls column norms, enabling concentration of the averaged outer products.
2 Proof of the Main Theorem
The proof establishes the main embedding theorem by combining independent isotropic Khatri–Rao columns, a moment-based tail bound, truncation, and matrix Chernoff concentration. This yields the desired subspace embedding after controlling both truncation and concentration failures.
- 2.1 Isotropy and independence: Independent isotropic columns reduce the Khatri–Rao sketch analysis to rank-one matrix concentration.Lemma 2.1 proves isotropy for Kronecker products of independent isotropic vectors, while Observation 2.2 gives statistical independence of the columns.
- 2.3 Truncation and concentration: 1−δ probability ensures no projected column is truncated after imposing the Proposition 2.3 tail threshold at failure probability δ/m.The truncation makes each rank-one matrix bounded by R^2I_k, enabling matrix Chernoff concentration.
- 2.3 Truncation and concentration: 2δ is the combined failure-probability bound obtained by union bounding the no-truncation and matrix-concentration events.When both events hold, the desired embedding inequalities follow up to constant factors in ε and δ, absorbed into m.