Barriers for Faster Dimensionality Reduction

Ora Nova Fandina, Mikael Møller Høgsgaard, Kasper Green Larsen

TL;DR

Can we perform Johnson-Lindenstrauss (JL) dimensionality reduction in strictly linear time $O(d)$? This paper proves the first non-trivial lower bound of $\Omega(m \lg m)$ operations for a broad class of structured linear embedding algorithms (specifically, linear circuits with bounded coefficients and an output scaling factor), explaining why decades of Fast JL constructions have been stuck at the $\Omega(d \lg d)$ barrier.

What Problem Does This Paper Address?

The Johnson-Lindenstrauss lemma is a cornerstone of randomized algorithms and machine learning. It guarantees that any $n$ points in Euclidean space $\mathbb{R}^d$ can be mapped into a lower-dimensional space $\mathbb{R}^m$ (with optimal target dimension $m = \Theta(\varepsilon^{-2} \lg n)$) while preserving pairwise Euclidean distances up to a $(1 \pm \varepsilon)$ factor.

While dense Gaussian projections take $O(md)$ time, researchers have long sought faster methods:

  1. Sparse embeddings (e.g., Kane–Nelson), which reduce per-column non-zeros but have provable sparsity limits.
  2. Structured embeddings (e.g., Ailon–Chazelle's Fast JL, Toeplitz/circulant matrices, and Kac random walks), which exploit FFT or Hadamard structures to achieve runtimes like $O(d \lg d + m \lg^2 n)$.

Despite these advances, an elusive open question remained: Is $O(d)$ embedding time fundamentally impossible, or are our algorithms just not clever enough?

Proving unconditional super-linear lower bounds for general linear circuits is a notoriously hard open problem in computational complexity (linked to Valiant’s matrix rigidity). This paper circumvents the barrier by formalizing the architectural template shared by almost all existing fast constructions and proving lower bounds within that model.

Methods

The authors analyze embedding algorithms modeled as linear circuits (where each step computes a linear combination of two previous values with coefficients $\lambda, \mu$). To make lower bounds tractable without resolving circuit complexity open problems, they enforce two structural properties present in nearly all known fast embeddings:

  1. Bounded Coefficients: The linear combination weights satisfy $|\lambda|, |\mu| \le r$ for a constant $r$ (e.g., $\pm 1$ in FFT/Hadamard recursions).
  2. Output Scaling: The embedding is computed as $s^{-1/2} A x$, where $A$ is generated by the circuit and $s$ is an explicit scaling parameter (termed a $\text{ScaledJL}(\varepsilon, \delta, s)$-matrix). In standard Fast JL, circulant JL, and sparse JL, $s = \Theta(m)$ or $\lg s = \Omega(\lg m)$.

The proof proceeds through three main technical steps:

  • Morgenstern’s Determinant Bound: By a classical result of Morgenstern, any linear circuit with bounded coefficients computing matrix $B$ requires at least $\Omega(\lg \Delta(B))$ operations, where $\Delta(B)$ is the maximum determinant of any square submatrix of $B$.
  • Spectral Connection to Subdeterminants: The authors apply a lemma by Larsen relating the eigenvalues of $B^T B$ to the subdeterminants of $B$.
  • Eigenvalue Concentration via Gaussian Probes: To lower-bound the eigenvalues of $B^T B$, the authors feed two "hard" inputs to the embedding: standard basis vectors $e_i$ (which lower-bound the trace $\text{Tr}(B^T B)$) and a random Gaussian vector $g$ (which, via anti-concentration inequalities, upper-bounds the Frobenius norm $\|B^T B\|_F^2$). Combining these shows that $B^T B$ must have $\Omega(m)$ eigenvalues of magnitude at least $\Omega(ds/m)$.

Datasets

Not discussed in the paper (purely theoretical paper; no experimental evaluations or datasets were used).

Key Insights and Ideas

  • Why Previous Lower-Bound Techniques Failed on JL: Standard bounded-coefficient circuit lower bounds yield bounds of the form $\Omega(\ell \lg \gamma_\ell)$, where $\gamma_\ell$ is the $\ell$-th eigenvalue of $A^T A$. However, because an embedding matrix must preserve unit vector norms, the trace $\text{Tr}(A^T A)$ is $O(d)$. When $d = \Theta(m)$, the average eigenvalue is at most a constant, leading only to trivial $\Omega(m)$ bounds.
  • The Power of the Scaling Factor $s$: Factoring out $s^{-1/2}$ boosts the effective eigenvalues of the computed circuit matrix $A$ by a factor of $s$. This allows the determinant to scale up to $s^{\Omega(m)}$, enabling Morgenstern's technique to finally yield a super-linear bound.
  • Spectrum Anti-Concentration: Simply knowing that $A$ has full rank isn't enough; the authors prove that $A^T A$ must contain $\Omega(m)$ simultaneously large eigenvalues. They achieve this using two-sided tail bounds on sums of independent $\chi^2$-like random variables.

Key Results

  • General Lower Bound (Theorem 4): For any stochastic matrix $A \in \mathbb{R}^{m \times d}$ satisfying the $\text{ScaledJL}(\varepsilon, \delta, s)$ property with $m = t \varepsilon^{-2} \lg(1/\delta)$, $t \ge 1$, and $d \ge m$, any linear circuit computing $A$ with gate weights bounded by $r > 1/2$ requires an expected: $$\Omega\left(\frac{m \lg(s/t^2)}{t \lg(2r)}\right) \text{ operations.}$$
  • Main Implication for Optimal JL (Theorem 3): When $d = \Theta(m)$, $r = O(1)$, $t = \Theta(1)$, and the scaling satisfies $\lg s = \Omega(\lg m)$ (which matches Fast JL, Toeplitz/circulant methods, and Kane–Nelson sparse JL), the circuit must perform: $$\Omega(m \lg m) \text{ operations.}$$ This matches known upper bounds and rules out strictly linear $O(d)$ time for this entire algorithmic regime.

Limitations and Future Work

  • Reliance on the Scaling Factor $s$: The lower bound does not rule out $O(d)$ embeddings if an algorithm operates with $s = O(1)$ or absorbs the scaling directly into unbounded gate coefficients.
  • Non-Linear Transformations: The lower bound only covers linear algorithms. It leaves open the possibility that a fast non-linear preprocessing step could bypass the $\Omega(m \lg m)$ barrier.
  • Kac's Random Walk: The Kac JL construction (which rotates random pairs of coordinates) avoids explicit output scaling in the same manner and is not directly ruled out by this theorem (though coupon-collector arguments separately prevent it from running in $o(d \lg d)$ time).
  • Roadmap for Future Upper Bounds: The authors point out that anyone hoping to achieve true $O(d)$ dimensionality reduction now knows precisely where to look: algorithms must use non-constant coefficients, non-linear operations, or avoid large scaling factors $s$.

Summary updated

Abstract

The Johnson-Lindenstrauss transform allows one to embed a dataset of n points in ℝ^d into ℝ^m, while preserving the pairwise distance between any pair of points up to a factor (1 ± ε), provided that m = Ω(ε^{-2} lg n). The transform has found an overwhelming number of algorithmic applications, allowing to speed up algorithms and reducing memory consumption at the price of a small loss in accuracy. A central line of research on such transforms, focus on developing fast embedding algorithms, with the classic example being the Fast JL transform by Ailon and Chazelle. All known such algorithms have an embedding time of Ω(d lg d), but no lower bounds rule out a clean O(d) embedding time. In this work, we establish the first non-trivial lower bounds (of magnitude Ω(m lg m)) for a large class of embedding algorithms, including in particular most known upper bounds.
BibTeX
@inproceedings{fandina2023barriers,
  author = {Ora Nova Fandina and Mikael Møller Høgsgaard and Kasper Green Larsen},
  title = {{Barriers for Faster Dimensionality Reduction}},
  booktitle = {STACS},
  year = {2023},
  url = {https://openreview.net/forum?id=0leMQbujPZ},
}

Loading related content...

Figure