A Tight Analysis of Khatri-Rao Oblivious Subspace Embeddings

Abstract

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 \epsilon )$ error, Bujanović et al. \cite{bujanovic2025subspace} prove that sketching dimension $m=O(k^{3/2}/{\epsilon }^2)$ suffices in the special case of $d=2$. Their dependence on $k$ is weaker than the tight bound of $O(k/{\epsilon }^2)$ known for unstructured sub-Gaussian sketching matrices. In this work, we close this gap, showing that $m=\tilde{O}(k/{\epsilon }^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.