Barriers for Faster Dimensionality Reduction

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

Abstract

The Johnson-Lindenstrauss (JL) transform allows one to embed a dataset of $n$ points in $\mathbb{R}^d$ into $\mathbb{R}^m$, while preserving the pairwise distance between any pair of points up to a factor $(1 \pm \varepsilon)$, provided that $m = \Omega(\varepsilon^{-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 focuses on developing fast embedding algorithms, with the classic example being the Fast JL transform (FJLT) by Ailon and Chazelle. All known such algorithms have an embedding time of $\Omega(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 $\Omega(m \lg m)$) for a large class of embedding algorithms, including in particular most known upper bounds.

Introduction

Dimensionality reduction is a cornerstone of modern data science and computational geometry. The Johnson-Lindenstrauss Lemma provides the theoretical guarantee that high-dimensional data can be projected into a significantly lower-dimensional space while maintaining the relative distances between points. While the target dimension $m$ is well-understood, the computational efficiency of the transformation itself has remained a subject of intense scrutiny.

A naive projection via a dense matrix requires $O(md)$ time. The development of the Fast Johnson-Lindenstrauss Transform (FJLT) utilized structured matrices to reduce this complexity to $O(d \log d)$ or $O(d \log m)$. However, the "holy grail" of this field—a linear-time $O(d)$ embedding—has remained elusive. This research addresses the fundamental question: Is a linear-time JL transform actually possible, or is there an inherent mathematical speed limit?

The ScaledJL Framework

To analyze the limits of these algorithms, the authors formalize a broad class of linear transformations termed ScaledJL. This class encompasses the vast majority of existing fast dimensionality reduction techniques. The ScaledJL model assumes a two-step process:

  1. Linear Computation: The algorithm performs a sequence of linear operations (additions and multiplications) using coefficients of bounded magnitude.
  2. Scaling: The resulting vector is scaled by a factor $s$ to ensure the preservation of norms.

By defining this class, the researchers created a rigorous framework to apply tools from arithmetic circuit complexity, specifically targeting the structured matrices that characterize "fast" transforms.

Methodology: Bypassing Matrix Rigidity

Proving lower bounds for general linear circuits is one of the most difficult challenges in computational complexity, often stalled by the problem of "matrix rigidity." The authors bypass these traditional hurdles by focusing specifically on the requirements of the JL Lemma—the preservation of Euclidean norms.

The proof relies on Morgenstern’s Lemma, which relates the complexity of a linear circuit to the maximum determinant of its submatrices. The core of the paper’s technical contribution is demonstrating that any matrix capable of satisfying the JL property must necessarily contain square submatrices with large determinants. This geometric requirement forces a minimum number of operations, establishing a lower bound on the algorithm's complexity.

Key Insights

  • The Role of Eigenvalues: The research establishes a critical link between a matrix's ability to preserve distances and the distribution of its eigenvalues. A successful JL matrix must possess many large eigenvalues, which mathematically necessitates the existence of the large-determinant submatrices required for the Morgenstern-based proof.
  • The Scaling Barrier: The authors identified that the "scaling parameter" used in structured transforms is a double-edged sword. While it allows for efficient computation, it also provides the mathematical handle needed to prove the $\Omega(m \log m)$ lower bound.
  • Hard Instances: To test these limits, the authors utilized a "hard instance" of vectors—a combination of standard basis vectors and Gaussian random vectors—to demonstrate that no ScaledJL algorithm can maintain accuracy below the established time threshold.

Results and Implications

The primary result is a lower bound of $\Omega(m \log m)$ operations for any ScaledJL embedding. This is the first non-trivial lower bound for this class of algorithms and suggests that current state-of-the-art methods, such as the FJLT, are essentially optimal within the realm of linear, bounded-coefficient transformations.

This finding shifts the focus of the field. If $O(d)$ is to be achieved, researchers must look outside the ScaledJL class, potentially exploring non-linear transformations or algorithms that utilize coefficients of unbounded magnitude.

Limitations and Future Directions

While significant, the bound is subject to specific constraints:

  • Bounded Coefficients: The proof assumes constant-magnitude coefficients. While standard in practical implementations, a theoretical loophole exists for algorithms using extremely large coefficients.
  • Linearity: The bound applies only to linear dimensionality reduction. The potential for non-linear techniques to surpass this limit remains an open question.
  • The Kac Random Walk: The authors identify the "Kac random walk" as a rare example of an embedding that does not strictly fit the ScaledJL definition, marking it as a primary candidate for future investigation into faster-than-logarithmic embeddings.

Summary updated

Abstract

The Johnson-Lindenstrauss transform allows one to embed a dataset of $n$ points in $\mathbb{R}^d$ into $\mathbb{R}^m,$ while preserving the pairwise distance between any pair of points up to a factor $(1 \pm \varepsilon)$, provided that $m = \Omega(\varepsilon^{-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 $\Omega(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 $\Omega(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},
}
Figure