On a Connection Between Fast and Sparse Oblivious Subspace Embeddings

Rui Wang, Wangli XuAISTATS 2022 · OpenReview

Abstract

Fast Johnson-Lindenstrauss Transform (FJLT) and Sparse Johnson-Lindenstrauss Transform (SJLT) are two important oblivious subspace embeddings. So far, the developments of these two methods are almost orthogonal. In this work, we propose an iterative algorithm for oblivious subspace embedding which makes a connection between these two methods. The proposed method is built upon an iterative implementation of FJLT and is equipped with several theoretically motivated modifications. One important strategy we adopt is the early stopping strategy. On the one hand, the early stopping strategy makes our algorithm fast. On the other hand, it results in a sparse embedding matrix. As a result, the proposed algorithm is not only faster than the FJLT, but also faster than the SJLT with the same degree of sparsity. We present a general theoretical framework to analyze the embedding property of sparse embedding methods, which is used to prove the embedding property of the proposed method. Lastly, we conduct numerical experiments to verify the good performance of the proposed algorithm.

Introduction

In the era of "Big Data," algorithms for tasks like linear regression often struggle with datasets that are too large to process directly. Researchers use Oblivious Subspace Embeddings (OSEs)—random matrices that "sketch" high-dimensional data into a lower-dimensional space while preserving its essential geometric structure, such as distances and angles.

Historically, OSEs have followed two distinct paths:

  1. Fast Transforms (FJLT): These utilize structured matrices (like Walsh-Hadamard) to achieve $O(nd \log n)$ computation time, though the resulting matrices are dense.
  2. Sparse Transforms (SJLT): These use matrices with very few non-zero entries to speed up computation but lack the recursive structure that makes fast transforms efficient.

This work bridges the gap between these two approaches, proposing a unified framework that captures the speed of fast transforms and the memory efficiency of sparse ones.

Methodology: The "NEW" Algorithm

The proposed algorithm, referred to as NEW, is based on three key innovations:

  • Iterative FJLT: The standard recursive FJLT is decomposed into a sequence of $\log n$ iterations, where each step involves a very sparse matrix multiplication.
  • Early Stopping: Instead of running all $\log n$ iterations, the process stops early at $\log s$ iterations. This ensures the final embedding matrix remains sparse, with exactly $s$ non-zero entries per column.
  • Random Permutation ($G$): To prevent structural patterns from ruining embedding properties due to early stopping, a random permutation matrix $G$ is introduced before the transform to "shuffle" the data.

Additionally, a new mathematical framework was developed to analyze sparse OSEs, allowing for dependent columns and different random sign schemes, improving theoretical requirements for the sparsity parameter $s$ by a logarithmic factor.

Experimental Evaluation

The method was evaluated using synthetic data (dense and sparse orthogonal matrices) and the MiniBooNE Particle Identification Dataset from the UCI Machine Learning Repository (130,064 instances, 50 attributes).

Key Results

The "NEW" method demonstrates a superior balance of speed and accuracy compared to traditional OSEs.

Error rates of various embedding methods as a function of sparsity parameter $s$.

As shown in the error analysis, the "NEW" method achieves error rates comparable to FJLT and SJLT. Notably, as the sparsity parameter $s$ increases, its performance consistently improves, eventually matching the accuracy of the dense FJLT while remaining significantly sparser.

Computing time comparison between the proposed method and standard OSEs.

In terms of computational efficiency, the proposed method is significantly faster than both FJLT and SJLT for dense input matrices. Its complexity is approximately $O(nd(\log(1/\epsilon) + \log \log (d/\delta)))$, which is very close to the ideal $O(nd)$ time. On the MiniBooNE dataset, it maintained similar error performance to FJLT and SJLT while being substantially faster.

Conclusion

This research highlights a hidden link between FJLT and SJLT, showing they are points on the same spectrum. By treating FJLT as a sequence of sparse operations and applying early stopping, one naturally arrives at an efficient sparse transform. While theoretical conditions on the number of rows $n$ remain strict, the empirical results confirm that this iterative approach offers a powerful new tool for large-scale data sketching.

Summary updated

Abstract

Fast Johnson-Lindenstrauss Transform (FJLT) and Sparse Johnson-Lindenstrauss Transform (SJLT) are two important oblivious subspace embeddings. So far, the developments of these two methods are almost orthogonal. In this work, we propose an iterative algorithm for oblivious subspace embedding which makes a connection between these two methods. The proposed method is built upon an iterative implementation of FJLT and is equipped with several theoretically motivated modifications. One important strategy we adopt is the early stopping strategy. On the one hand, the early stopping strategy makes our algorithm fast. On the other hand, it results in a sparse embedding matrix. As a result, the proposed algorithm is not only faster than the FJLT, but also faster than the SJLT with the same degree of sparsity. We present a general theoretical framework to analyze the embedding property of sparse embedding methods, which is used to prove the embedding property of the proposed method. This framework is also of independent interest. Lastly, we conduct numerical experiments to verify the good performance of the proposed algorithm.
BibTeX
@inproceedings{wang2022connection,
  author = {Rui Wang and Wangli Xu},
  title = {{On a Connection Between Fast and Sparse Oblivious Subspace Embeddings}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2022},
  url = {https://openreview.net/forum?id=ks3uEyhDCw},
}
Figure