We investigate random sketching matrices that possess a Khatri‑Rao structure. Consider the Khatri‑Rao product (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). When the input data has a tensor form that allows fast multiplication with $A_1\odot\cdots\odot A_d$, such sketching matrices are widely used in randomized linear‑algebra algorithms and data analysis.
Existing theory, however, does not fully explain their empirical performance. In particular, for the crucial oblivious subspace embedding property, the best known bounds for Khatri‑Rao matrices lag behind those for standard unstructured matrices. Bujanović et al. \cite{bujanovic2025subspace} showed that for the special case $d=2$ a sketching dimension $m = O(k^{3/2}/\epsilon^2)$ suffices to embed a $k$‑dimensional subspace with $(1\pm\epsilon)$ error, which is weaker than the tight $O(k/\epsilon^2)$ bound achievable with unstructured sub‑Gaussian sketches.
In this paper we close the gap by proving that for any fixed order $d$ a dimension $m = \tilde O(k/\epsilon^2)$ is enough for a subspace embedding. The proof is remarkably simple: it relies only on two elementary properties of the Khatri‑Rao sketching distribution:
- The columns of $A_1\odot\cdots\odot A_d$ are independent and isotropic;
- Each column satisfies a weak Johnson‑Lindenstrauss‑type moment condition.
These properties allow us to apply standard matrix concentration arguments and obtain the optimal dimension bound, showing that Khatri‑Rao sketches are theoretically as efficient as their unstructured counterparts.
Blogger's Review: The result lifts the embedding guarantee for Khatri‑Rao sketches to the optimal $\tilde O(k/\epsilon^2)$ regime, narrowing the gap between theory and practice.