Tight Bounds for ℓp Oblivious Subspace Embeddings

An ℓp oblivious subspace embedding is a distribution over r × n matrices Pi such that for any fixed n × d matrix A, PrPi[textrmfor all x, |Ax|p ≤ |Pi Ax|p ≤ kappa |Ax|p] ≥ 9/10, where r is the dimension of the embedding, kappa is the distortion of the embedding, and for an n-dimensional vector y, |y|p is the ℓp-norm. Another important property is the sparsity of Pi, that is, the maximum number of non-zero entries per column, as this determines the running time of computing Pi · A. While for p = 2 there are nearly optimal tradeoffs in terms of the dimension, distortion, and sparisty, 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. We show for every 1 ≤ p < 2, any oblivious subspace embedding with dimension r has distortion kappa = Omega left(frac1left(frac1dright)1 / p · log2 / pr + left(fracrnright)1 / p - 1 / 2right). When r = poly(d) in applications, this gives a kappa = Omega(d1/plog-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. We also give sparse oblivious subspace embeddings for every 1 ≤ p < 2 which are optimal in dimension and distortion, up to poly(log d) factors. 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.