Metraipolis › archive › dc_bdb2987bf572

A Tight Analysis of Khatri-Rao Oblivious Subspace Embeddings — arXiv:2608.28094

Source: arXiv (en)
Original: https://arxiv.org/abs/2608.28094
License (as archived): CC0-1.0
Archived: 2026-10-17T11:52:26.684Z
SHA-256 of the archived text: c38de920776f8a4b8192c8e6e8e8a5afabc1d482fdcd57da02f50f2cda8de416
Stable URL of this page: https://metraipolis.com/documento/dc_bdb2987bf572

How to cite

A Tight Analysis of Khatri-Rao Oblivious Subspace Embeddings — arXiv:2608.28094 — arXiv (en), https://arxiv.org/abs/2608.28094 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_bdb2987bf572 (Metraipolis archive dc_bdb2987bf572, sha256 c38de920776f8a4b8192c8e6e8e8a5afabc1d482fdcd57da02f50f2cda8de416)

BibTeX

@misc{dcbdb2987bf572,
  title = {A Tight Analysis of Khatri-Rao Oblivious Subspace Embeddings — arXiv:2608.28094},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.28094},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_bdb2987bf572; sha256 c38de920776f8a4b8192c8e6e8e8a5afabc1d482fdcd57da02f50f2cda8de416},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.28094. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-31 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2608.28094 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-17T11:23:11.258Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-08-31?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).