Exponentially Improved Dimensionality Reduction for ℓ1: Subspace Embeddings and Independence Testing

Despite many applications, dimensionality reduction in the ℓ1-norm is much less understood than in the Euclidean norm. We give two new oblivious dimensionality reduction techniques for the ℓ1-norm which improve exponentially over prior ones: 1. We design a distribution over random matrices S ∈ ℝr × n, where r = 2tilde O(d/(varepsilon δ)), such that given any matrix A ∈ ℝn × d, with probability at least 1-δ, simultaneously for all x, |SAx|1 = (1 ± varepsilon)|Ax|1. Note that S is linear, does not depend on A, and maps ℓ1 into ℓ1. Our distribution provides an exponential improvement on the previous best known map of Wang and Woodruff (SODA, 2019), which required r = 2^2Omega(d), even for constant varepsilon and δ. Our bound is optimal, up to a polynomial factor in the exponent, given a known 2√ d lower bound for constant varepsilon and δ. 2. We design a distribution over matrices S ∈ ℝk × n, where k = 2O(q2)(varepsilon-1 q log d)O(q), such that given any q-mode tensor A ∈ (ℝd)otimes q, one can estimate the entrywise ℓ1-norm |A|1 from S(A). Moreover, S = S1 otimes S2 otimes cdots otimes Sq and so given vectors u1, ldots, uq ∈ ℝd, one can compute S(u1 otimes u2 otimes cdots otimes uq) in time 2O(q2)(varepsilon-1 q log d)O(q), which is much faster than the dq time required to form u1 otimes u2 otimes cdots otimes uq. Our linear map gives a streaming algorithm for independence testing using space 2O(q2)(varepsilon-1 q log d)O(q), improving the previous doubly exponential (varepsilon-1 log d)^qO(q) space bound of Braverman and Ostrovsky (STOC, 2010).