我们研究具有 Khatri-Rao 结构的随机 sketching 矩阵。设随机矩阵 $A_1\odot\cdots\odot A_d \in \mathbb{R}^{(n_1 \cdots n_d) \times m}$，其中每个 $A_i \in \mathbb{R}^{n_i \times m}$ 的列是各向同性、独立且次高斯的（例如高斯矩阵）。当输入数据具有张量结构且可以快速与 $A_1\odot\cdots\odot A_d$ 相乘时，Khatri-Rao sketching 矩阵被广泛用于线性代数随机算法和数据分析。
然而，现有理论尚未完全解释其在实践中的表现。尤其是对于重要的 oblivious subspace embedding（盲子空间嵌入）属性，已有的上界仍落后于标准无结构矩阵。Bujanović 等人在 $d=2$ 的特殊情形下证明，嵌入维度 $m = O(k^{3/2}/\epsilon^2)$ 已足以保证 $k$ 维子空间的 $(1\pm\epsilon)$ 误差，他们的 $k$ 依赖弱于无结构次高斯 sketching 矩阵已知的紧致界 $O(k/\epsilon^2)$。
本文弥合了这一差距，证明对于任意固定阶数 $d$，只需 $m = \tilde O(k/\epsilon^2)$ 即可实现子空间嵌入。证明思路极其简洁，仅利用 Khatri-Rao sketching 分布的两条基本性质：
- $A_1\odot\cdots\odot A_d$ 的列相互独立且各向同性；
- 每列满足弱 Johnson‑Lindenstrauss 型矩矩性质。
这些性质足以在标准矩阵浓缩技术框架下得到所需的维度上界，从而使 Khatri‑Rao 结构在理论上与无结构矩阵同等高效。
博主点评：该工作将 Khatri‑Rao 结构的子空间嵌入上界提升到与无结构矩阵相同的量级，理论与实践的差距得到显著缩小。