Abstract
We prove the Johnson-Lindenstrauss property for matrices $\Phi D_\xi$ where $\Phi$ has the restricted isometry property and $D_\xi$ is a diagonal matrix containing the entries of a Kronecker product $\xi = \xi^{(1)} \otimes \dots \otimes \xi^{(d)}$ of $d$ independent Rademacher vectors. Such embeddings have been proposed in recent works for a number of applications concerning compression of tensor structured data, including the oblivious sketching procedure by Ahle et al. for approximate tensor computations. For preserving the norms of $p$ points simultaneously, our result requires $\Phi$ to have the restricted isometry property for sparsity $C(d) (\log p)^d$. In the case of subsampled Hadamard matrices, this can improve the dependence of the embedding dimension on $p$ to $(\log p)^d$ while the best previously known result required $(\log p)^{d + 1}$. That is, for the case of $d=2$ at the core of the oblivious sketching procedure by Ahle et al., the scaling improves from cubic to quadratic. We provide a counterexample to prove that the scaling established in our result is optimal under mild assumptions.
Introduction
In modern data science, the Johnson-Lindenstrauss (JL) Lemma serves as a cornerstone for dimensionality reduction. It guarantees that a set of high-dimensional points can be projected into a significantly lower-dimensional space while approximately preserving the Euclidean distances between them. This process, known as "sketching," is vital for handling massive datasets where computational costs scale poorly with dimensionality.
However, a significant challenge arises when dealing with tensor-structured data. In these scenarios, data points are represented as multi-dimensional arrays (tensors). Applying a standard JL transform to such data is often computationally prohibitive because it requires forming the full, high-dimensional vector—often a Kronecker product of smaller vectors—before compression. The Kronecker Fast Johnson-Lindenstrauss Transform (KFJLT) was developed to circumvent this by applying the transformation factor-by-factor, leveraging the inherent structure of the data for efficiency.
While the KFJLT has been adopted in practice, its theoretical limits—specifically the minimum dimension $m$ required to maintain accuracy—remained loosely defined. This research bridges that gap, providing a sharper theoretical bound and proving its optimality.
The Kronecker Structure
The authors analyze a specific embedding matrix structure defined as $A = \Phi D_\xi$. In this construction:
- $\Phi$ is a matrix satisfying the Restricted Isometry Property (RIP), such as a randomly subsampled Hadamard matrix.
- $D_\xi$ is a diagonal matrix where the entries are derived from a Kronecker product of $d$ independent Rademacher vectors (random variables taking values $\pm 1$).
This structure is particularly relevant for "oblivious sketching," where the goal is to compress tensor data without knowing the specific distribution of the data beforehand.
Mathematical Methodology
To establish a tighter bound for the KFJLT, the researchers generalized techniques previously reserved for standard (non-tensor) fast JL transforms. The proof relies on three advanced mathematical pillars:
- Higher-order Rademacher Chaos: The error in distance preservation is modeled as a "chaos" expression of order $2d$. Analyzing these higher-order interactions is key to understanding how errors propagate through the Kronecker product.
- Decoupling: The Kronecker structure introduces complex dependencies between matrix entries. The authors utilize decoupling lemmas to separate these variables, making the concentration analysis tractable.
- Higher-dimensional Hanson-Wright Inequality: By applying advanced concentration inequalities, the authors were able to bound the probability of large deviations (errors) more tightly than previous attempts.
Key Results and Insights
The "Logarithmic Gain"
The most significant contribution of this work is the reduction of the exponent in the failure probability scaling. Previous literature suggested that the required embedding dimension $m$ scaled with $(\log p)^{d+1}$, where $p$ is the number of points and $d$ is the number of tensor factors. This paper proves a sharper bound of $O(\epsilon^{-2} (\log p)^d)$.
For the common case of $d=2$ (second-order tensors), this improvement is substantial. It represents a shift from cubic to quadratic scaling in terms of the log-failure probability. In practical terms, this means that to achieve the same level of accuracy, a practitioner might only need 100 dimensions where previous theory suggested 1,000 were necessary.
RIP-JL Equivalence for Tensors
The paper extends the "near-equivalence" between the Restricted Isometry Property (common in compressed sensing) and the Johnson-Lindenstrauss property (common in dimensionality reduction) to the tensor setting. This unification allows tools from both fields to be applied to tensor compression problems more effectively.
Proving Optimality
To ensure this new bound could not be improved further, the authors constructed a counterexample using specific sets of points based on indicator vectors of subspaces in $\mathbb{F}_2^n$. This mathematical construction demonstrates that the $(\log p)^d$ scaling is the best possible under mild assumptions, effectively closing the theoretical gap for this class of transforms.
Conclusion and Future Directions
This research provides the sharpest known bounds for Kronecker-structured JL embeddings, offering a rigorous theoretical foundation for tensor sketching. While the scaling is now optimal, several avenues for future work remain:
- Constant Factors: The constant $C(d)$ in the bound may grow with the number of factors $d$. Investigating the behavior of this constant for very high-dimensional tensors is a logical next step.
- Distributional Extensions: The current proof is tailored to Rademacher distributions. Extending these sharp bounds to Gaussian or sparse distributions would broaden the utility of the KFJLT.
- Empirical Benchmarking: As a theoretical work, the next phase involves translating these bounds into empirical benchmarks to observe how the quadratic scaling performs in real-world machine learning pipelines compared to older, looser estimates.
Summary updated