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 ∈ Rr×n, where r = 2, such that given any matrix A ∈ Rn×d, with probability at least 1 − δ, simultaneously for all x, ‖SAx‖1 = (1 ± ε)‖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 Ω(d) , even for constant ε and δ. Our bound is optimal, up to a polynomial factor in the exponent, given a known 2 √ d lower bound for constant ε and δ. 2. We design a distribution over matrices S ∈ Rk×n, where k = 2 2)(ε−1q log d), such that given any q-mode tensor A ∈ (Rd)⊗q, one can estimate the entrywise `1-norm ‖A‖1 from S(A). Moreover, S = S ⊗ S ⊗ · · · ⊗ S and so given vectors u1, . . . ,uq ∈ R, one can compute S(u1 ⊗ u2⊗· · ·⊗uq) in time 2 2)(ε−1q log d), which is much faster than the d time required to form u1⊗u2⊗· · ·⊗uq. Our linear map gives a streaming algorithm for independence testing using space 2 2)(ε−1q log d), improving the previous doubly exponential (ε−1 log d) O(q) space bound of Braverman and Ostrovsky (STOC, 2010). For subspace embeddings, we also study the setting when A is itself drawn from distributions with independent entries, and obtain a polynomial embedding dimension. For independence testing, we also give algorithms for any distance measure with a polylogarithmic-sized sketch and satisfying an approximate triangle inequality. ar X iv :2 10 4. 12 94 6v 1 [ cs .D S] 2 7 A pr 2 02 1