Tight Bounds for ℓp Oblivious Subspace Embeddings

Ruosong Wang, David P. WoodruffSODA 2018 · DOI · OpenReview

Abstract

An $\ell_p$ oblivious subspace embedding (OSE) is a distribution over $r \times n$ matrices $\Pi$ such that for any fixed $n \times d$ matrix $A$, the $\ell_p$ norm of all vectors in the subspace spanned by $A$ is preserved within a distortion factor $\kappa$ with high probability. While the case for $p=2$ is well-understood, the range $1 \leq p < 2$—critical for robust statistics—has lacked tight bounds. This paper establishes nearly optimal tradeoffs between the embedding dimension $r$, distortion $\kappa$, and sparsity $s$. We prove a lower bound of $\kappa = \Omega(d^{1/p} \log^{-2/p} d)$ for $r = \text{poly}(d)$, showing that previous constructions were near-optimal. Furthermore, we provide new sparse OSEs that achieve these limits, significantly improving algorithms for distributed regression and low-rank approximation.

Introduction

In large-scale data analysis, we frequently encounter the problem of solving linear regression $\min_x \|Ax - b\|_p$ where the matrix $A$ is massive ($n \times d$, with $n \gg d$). A powerful technique to handle such data is the use of an Oblivious Subspace Embedding (OSE). An OSE is a random matrix $\Pi$ that "sketches" the data into a much smaller space ($r \times n$) while preserving the lengths of all vectors in the subspace spanned by $A$. Specifically, we require: $$\Pr_\Pi[\forall x, \ \|Ax\|_p \leq \|\Pi Ax\|_p \leq \kappa\|Ax\|_p] \geq 9/10$$

While the Euclidean case ($p=2$) is well-characterized by the Johnson-Lindenstrauss lemma and its variants, the case for $1 \leq p < 2$ is vital for robust statistics because these norms are less sensitive to outliers. Prior to this work, a significant gap existed in our understanding of the optimal distortion and sparsity for these norms. This paper closes that gap by providing tight lower and upper bounds.

Establishing Fundamental Limits: Lower Bounds

To determine the best possible performance of any OSE, the authors employ Yao’s minimax principle. They construct a "hard" distribution of matrices $A$ designed to expose the limitations of any sketching matrix $\Pi$. This hard distribution consists of three distinct components:

  1. Dense Gaussian columns to test general subspace preservation.
  2. Sparse "M-columns" and "S-columns" to force the sketch to lose information unless its dimension $r$ is sufficiently large.

The resulting lower bound reveals a surprising dependence on the ratio of the sketch dimension $r$ to the original dimension $n$. For the standard case where $r = \text{poly}(d)$, the authors prove that the distortion must be at least: $$\kappa = \Omega\left(\frac{1}{(1/d)^{1/p} \cdot \log^{2/p} r + (r/n)^{1/p - 1/2}}\right)$$

This result confirms that earlier constructions by Sohler and Woodruff ($p=1$) and Meng and Mahoney ($1 < p < 2$) were already near-optimal up to polylogarithmic factors.

Algorithmic Breakthroughs: Sparse Upper Bounds

Beyond proving what is impossible, the paper introduces new, highly efficient sketching matrices. A primary goal in OSE design is sparsity ($s$), which refers to the number of non-zero entries per column of $\Pi$. High sparsity ensures that the sketch $\Pi A$ can be computed in time nearly linear in the number of non-zeros in $A$.

The Heavy vs. Light Strategy

The authors utilize a hybrid sketching strategy based on the observation that the $\ell_p$ norm of a vector is often dominated by a few "heavy" coordinates or a large number of "light" coordinates.

  • Heavy Coordinates: For vectors where a few coordinates contribute most of the norm, the authors show that standard $\ell_2$ embeddings (like CountSketch) are actually sufficient for $\ell_p$ preservation.
  • Light Coordinates: For vectors with many small entries, they employ a sparse Cauchy-based sketch.

Truncation and Sparsity

To achieve the sparsest possible results, the authors introduce a "truncation" argument for $p$-stable random variables. By capping the minimum value of random entries, they improve the "contraction" bound of the sketch without negatively impacting its "dilation" properties.

One of the most significant results is the demonstration that nearly optimal distortion can be achieved with only two non-zero entries per column ($s=2$). This means computing the sketch is computationally inexpensive, requiring only a few additions or subtractions per entry of the original matrix.

Key Results and Applications

  1. Tight Lower Bound: For $r = \text{poly}(d)$, the distortion $\kappa = \Omega(d^{1/p} \log^{-2/p} d)$ is inevitable.
  2. Optimal Sparse Sketches: The authors provide a sketch with $r = O(d^2)$ rows and $s=2$ non-zeros per column that achieves $\kappa = O(d)$ for $p=1$.
  3. Constant Distortion: They prove that if the sketch dimension $r$ is allowed to be doubly exponential in $d$ (though still independent of $n$), one can achieve constant distortion ($\kappa = O(1)$).
  4. Distributed and Streaming Gains: These new OSEs lead to immediate improvements in communication complexity for distributed $\ell_p$ regression, reducing the communication cost by factors of $(d \log d)^{p/2}$ compared to previous state-of-the-art methods.

Limitations and Future Directions

While this work provides a comprehensive look at the $1 \leq p < 2$ range, several questions remain:

  • The $s=1$ Gap: The paper achieves $r = O(d^2)$ with $s=2$, but their $s=1$ construction requires $r = O(d^4)$. Whether $r = O(d^2)$ is possible with only one non-zero per column remains an open question.
  • Practical Constant Distortion: The constant-distortion embedding requires $r = \exp(\exp(O(d)))$, which is impractical for large $d$. Finding a more compact constant-distortion sketch is a major challenge.
  • The $p > 2$ Frontier: The behavior of OSEs for $p > 2$ is fundamentally different and was not the focus of this study, representing a distinct area for future research.

Summary updated

Abstract

An ℓp oblivious subspace embedding is a distribution over r × n matrices n such that for any fixed n × d matrix A, where r is the dimension of the embedding, κ is the distortion of the embedding, and for an n-dimensional vector y, ‖y‖p = (∑i=1n |yi|)1/p is the ℓp-norm. Another important property is the sparsity of Π, that is, the maximum number of nonzero entries per column, as this determines the running time of computing Π · A. While for p = 2 there are nearly optimal tradeoffs in terms of the dimension, distortion, and sparsity, for the important case of 1 ≤ p < 2, much less was known. In this paper we obtain nearly optimal tradeoffs for ℓp oblivious subspace embeddings for every 1 ≤ p < 2. Our main results are as follows: 1. We show for every 1 ≤ p < 2, any oblivious subspace embedding with dimension r has distortion . When r = poly(d) ≪ n in applications, this gives a κ = Ω(d1/p log−2/p d) lower bound, and shows the oblivious subspace embedding of Sohler and Woodruff (STOC, 2011) for p = 1 and the oblivious subspace embedding of Meng and Mahoney (STOC, 2013) for 1 < p < 2 are optimal up to poly(log(d)) factors. 2. We give sparse oblivious subspace embeddings for every 1 ≤ p < 2 which are optimal in dimension and distortion, up to poly(log d) factors. Importantly for p = 1, we achieve r = O(d log d), κ = O(d log d) and s = O(log d) non-zero entries per column. The best previous construction with s ≤ poly(log d) is due to Woodruff and Zhang (COLT, 2013), giving κ = Ω(d2 poly(log d)) or κ = Ω(d3/2 · poly(log d)) and r ≥ d · poly(log d); in contrast our r = O(d log d) and κ = O(d log d) are optimal up to poly(log(d)) factors even for dense matrices. We also give (1) nearly-optimal ℓp oblivious subspace embeddings with an expected 1 + ε number of non-zero entries per column for arbitrarily small ε > 0, and (2) the first oblivious subspace embeddings for 1 ≤ p < 2 with O(1)-distortion and dimension independent of n. Oblivious subspace embeddings are crucial for distributed and streaming environments, as well as entrywise ℓp low rank approximation. Our results give improved algorithms for these applications.
BibTeX
@inproceedings{wang2018tight,
  author = {Ruosong Wang and David P. Woodruff},
  title = {{Tight Bounds for ℓp Oblivious Subspace Embeddings}},
  booktitle = {SODA},
  year = {2018},
  doi = {10.1137/1.9781611975482.110},
}
Figure