2021/04/27 by Yi Li, David P. Woodruff, Li, Yi +3 · 1 citation
Computer Science · Engineering · Mathematics · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #Tensor decomposition and applications
paper · pdf · doi:10.48550/arxiv.2104.12946
openalex publication_date 2021/04/27 · openalex created_date 2021/05/10 · openalex updated_date 2026/07/28
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 = 2 O(d/(ε δ)), such that given any matrix A ∈ ℝn × 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^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 ∈ ℝk × n, where k = 2O(q2)(ε-1 q log d)O(q), such that given any q-mode tensor A ∈ (ℝd)⊗ q, one can estimate the entrywise ℓ1-norm ‖A‖1 from S(A). Moreover, S = S1 ⊗ S2 ⊗ ⋯ ⊗ Sq and so given vectors u1, …, uq ∈ ℝd, one can compute S(u1 ⊗ u2 ⊗ ⋯ ⊗ uq) in time 2O(q2)(ε-1 q log d)O(q), which is much faster than the dq time required to form u1 ⊗ u2 ⊗ ⋯ ⊗ uq. Our linear map gives a streaming algorithm for independence testing using space 2O(q2)(ε-1 q log d)O(q), improving the previous doubly exponential (ε-1 log d)^qO(q) space bound of Braverman and Ostrovsky (STOC, 2010).