Tight Bounds for ℓp Oblivious Subspace Embeddings
Ruosong Wang, David P. Woodruff · Society for Industrial and Applied Mathematics eBooks · 2019
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 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.