A preprint reports a theoretical bound that brings Khatri-Rao sketches close to a linear relationship between sketch size and the dimension of the subspace being preserved. For any fixed tensor order d, it says a sketching dimension m that grows almost linearly with subspace dimension k, and like the inverse square of the allowed error, is sufficient for the embedding guarantee.
The construction uses independent random matrix columns in a tensorized form. The proof establishes that the tensorized columns are isotropic, meaning no direction is favored on average, and that the Khatri-Rao columns remain statistically independent.
The gap the paper targets
The central question is whether Khatri-Rao sketches can achieve tight oblivious-subspace-embedding bounds, or whether their gap with unstructured sketches is inherent. An oblivious subspace embedding, or OSE, is a random sketch that preserves the relevant norm for every vector in a k-dimensional subspace within one plus or minus the allowed error, with probability at least one minus the failure probability δ.
That comparison matters because the paper frames an earlier d = 2 Khatri-Rao bound as growing like k to the three-halves power divided by the squared error, compared with k divided by the squared error for unstructured sub-Gaussian sketches. The fixed-order statement replaces that extra dependence with a nearly linear one, although factors hidden by the paper's order notation are not shown.
A theorem with clear boundaries
To state the theorem, the proof fixes an arbitrary k-dimensional subspace and represents it with a matrix U whose columns form an orthonormal basis. The theorem is stated for error and failure parameters between 0 and 1, factor dimensions n1 through nd of at least 2, and k no larger than the ambient dimension N.
It also assumes independent random matrices, with independent columns that are isotropic and have a constant sub-Gaussian norm. In plain terms, the model requires random inputs with balanced average directions and controlled tails.
That scope matters. The theorem gives a sufficient upper bound under this model, not a proof that the stated dimension is a matching lower bound. The hidden constants and tilde factors in the near-linear expression are also not quantified.
The proof's chain of reasoning
To control rare large projections, the proof uses a moment bound for sub-Gaussian chaoses, product-like random expressions built from independent isotropic sub-Gaussian vectors. It then states an upper-tail bound: when t is at least 1, the chance that a squared projection norm exceeds a constant times k times t is bounded by an exponential term involving d and t raised to the one-over-d power.
Once the columns are controlled, the projected Gram matrix is treated as an average of m statistically independent rank-one matrices. A matrix Chernoff bound is then used to turn those column-level estimates into concentration for the whole subspace embedding.
A probability budget
To manage unusually large columns, the proof truncates any column above a threshold R. Each column exceeds that threshold with probability no greater than the failure probability divided by m, and a union bound gives probability at least one minus the failure probability that no column is truncated.
Combining the truncation and concentration events, the proof reports a total failure probability of at most 2δ. It says constant-factor changes in the error and failure parameters can be absorbed into m, leaving the fixed-order near-linear scaling.
What the structure could save
The proposed structure also changes the multiplication cost. For tensor-product columns, the paper compares a cost proportional to the sum of the factor dimensions, multiplied by d and m, with a dense projection whose cost is proportional to their product, again multiplied by d and m. It describes that difference as an exponential saving.
No runtime experiment is reported, so this remains a theoretical cost comparison rather than a measured performance result.
What the result does not settle
The document identifies itself as an arXiv preprint, version 3 dated 23 September 2026. Its guarantee is stated for fixed tensor order and for the independent, isotropic, constant-sub-Gaussian model described above.
That leaves open whether a matching lower bound would establish exact tightness, how the guarantee behaves when d is not fixed, and whether the theoretical cost advantage translates into measured gains on tensor-structured applications.
The authors also disclose using AI in proof development, typesetting and proofreading, while accepting responsibility for manuscript correctness.
Paper data and sources
Original title: A Tight Analysis of Khatri-Rao Oblivious Subspace Embeddings
Authors: Lorenzo Beretta, Cameron Musco
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-28
DOI: Not available
Original paper · Full text