2022/11/14 by Yi Li, Honghao Lin, Li, Yi +3
Computer Science · #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2211.07132
openalex publication_date 2022/11/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In the ℓp-subspace sketch problem, we are given an n× d matrix A with n>d, and asked to build a small memory data structure Q(A,ε) so that, for any query vector x∈ℝd, we can output a number in (1±ε)‖Ax‖pp given only Q(A,ε). This problem is known to require Ω(dε-2) bits of memory for d=Ω(log(1/ε)). However, for d=o(log(1/ε)), no data structure lower bounds were known. We resolve the memory required to solve the ℓp-subspace sketch problem for any constant d and integer p, showing that it is Ω(ε-2(d-1)/(d+2p)) bits and O (ε-2(d-1)/(d+2p)) words. This shows that one can beat the Ω(ε-2) lower bound, which holds for d = Ω(log(1/ε)), for any constant d. We also show how to implement the upper bound in a single pass stream, with an additional multiplicative poly(log log n) factor and an additive poly(log n) cost in the memory. Our bounds can be applied to point queries for SVMs with additive error, yielding an optimal bound of Θ(ε-2d/(d+3)) for every constant d. This is a near-quadratic improvement over the Ω(ε-(d+1)/(d+3)) lower bound of (Andoni et al. 2020). Our techniques rely on a novel connection to low dimensional techniques from geometric functional analysis.