A new mathematical analysis reports that random sketches with Khatri-Rao structure can preserve the geometry of a chosen subspace using a sketch whose dimension is nearly proportional to the subspace size. For any fixed Khatri-Rao order, the stated sufficient bound is , where m is the sketching dimension, k is the dimension of the subspace, epsilon is the allowed relative error, and the tilde notation hides logarithmic factors and constants.
A sketch here is a random compression used to work with a subspace in fewer dimensions. The analysis asks whether a sketch built from factor matrices can still support subspace-embedding guarantees comparable in dimension to unstructured sub-Gaussian sketches. It studies that question at the level of a proof, considering arbitrary subspaces rather than an empirical data set.
A sharper dependence on subspace size
The authors describe the result as closing a previous theoretical gap between Khatri-Rao sketches and unstructured sub-Gaussian sketches when the Khatri-Rao order is fixed. For orders above 2, they say an earlier dependence that was polynomial in k can be replaced by a logarithmic factor in k.
The comparison is easiest to see in the cited special case of order 2. An earlier result gave a sufficient dimension proportional to k raised to the three-halves power, divided by the squared error tolerance. The authors describe that dependence on k as weaker than the linear-in-k dependence reported for unstructured sub-Gaussian sketches. The new statement uses suppressed logarithmic factors, so it should be read as an asymptotic upper bound rather than a plug-in dimension with every constant specified.
The result is a statement about how the required sketch dimension scales as the target subspace grows. It does not measure runtime, memory use, accuracy, or any other downstream outcome. Its contribution is the guarantee supplied by the proof.
What the proof assumes
The theorem applies to suitably scaled Khatri-Rao sketches whose factor matrices have columns that are independent, isotropic, and constant sub-Gaussian. Here, isotropic means balanced across directions on average, while sub-Gaussian refers to random quantities with controlled tail behavior. Independent standard Gaussian factor matrices are included among the stated examples.
To analyze the embedding, the proof fixes an arbitrary k-dimensional subspace and represents it by a matrix U whose columns form an orthonormal basis. The argument then examines how the random sketch acts on that subspace, rather than testing a selected collection of vectors from data.
Two distributional facts drive the argument. First, the columns of the Khatri-Rao sketch are independent and isotropic. Second, each column satisfies a weak Johnson-Lindenstrauss-type moment property. This is a moment bound used to control the norms of projected columns with high probability.
A concentration argument with a safeguard
The proof uses moment bounds for sub-Gaussian chaoses, meaning products of sub-Gaussian random quantities, and then applies Markov's inequality to obtain a tail bound for column norms. A union bound is used to control all columns simultaneously with high probability.
The analysis also deals with an obstacle that appears when projected column outer products can have arbitrarily large spectral radius, or largest eigenvalue. It truncates rare columns with unusually large norms before applying concentration. After the two distributional properties and this control step are in place, the proof applies a standard matrix Chernoff bound to establish the sufficient embedding dimension.
Because the result is a sufficient condition, it does not by itself establish that every smaller sketch must fail. The notation leaves some logarithmic factors and constants implicit, and the analysis does not supply matching lower bounds showing that every part of the dependence is optimal.
A theoretical result, with clear boundaries
The evidence is entirely theoretical. There are no experiments, benchmarks, real data sets, or measured downstream algorithmic results in the analysis. It therefore does not show that the improved bound produces faster tensor algorithms or better accuracy in an application.
The result is limited to fixed order and the specified sub-Gaussian column distributions. The preprint does not establish the same guarantee when the order grows, when the sketch is sparse or otherwise non-sub-Gaussian, or when the dependence on the order and the omitted logarithmic factors are changed. The supplied analysis leaves open how much of that dependence is optimal.
The manuscript is an arXiv preprint, version 1, dated 28 August 2026. The authors also report using AI and interactive large-language-model conversations during the research, as well as for typesetting and proofreading, while retaining responsibility for the work's 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