2015/04/04 by Arturs Backurs, Artūrs Bačkurs, Backurs, Arturs +9 · 1 citation
Computer Science · Engineering · Mathematics · #Algorithm #Cluster analysis #Combinatorics #Complexity and Algorithms in Graphs #Compressed sensing #Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #Dimension (graph theory) #Discrete mathematics #Eigenvalues and eigenvectors #FOS: Computer and information sciences #Information Theory (cs.IT) #Mathematical analysis #Mathematics #Matrix norm #Metric space #Norm (philosophy) #Sparse and Compressive Sensing Techniques #Statistics #Stochastic Gradient Optimization Techniques #Uniform norm #Upper and lower bounds #cs.CG #cs.DS #cs.IT #math.IT
paper · pdf · doi:10.48550/arxiv.1504.01076
published in arXiv (Cornell University) (Cornell University) · 29 pages
arxiv created 2015/04/05 · openalex publication_date 2015/04/05 · arxiv updated 2015/04/07 · openalex created_date 2022/10/03 · openalex updated_date 2026/08/08
We initiate the study of trade-offs between sparsity and the number of measurements in sparse recovery schemes for generic norms. Specifically, for a norm ‖⋅‖, sparsity parameter k, approximation factor K>0, and probability of failure P>0, we ask: what is the minimal value of m so that there is a distribution over m × n matrices A with the property that for any x, given Ax, we can recover a k-sparse approximation to x in the given norm with probability at least 1-P? We give a partial answer to this problem, by showing that for norms that admit efficient linear sketches, the optimal number of measurements m is closely related to the doubling dimension of the metric induced by the norm ‖⋅‖ on the set of all k-sparse vectors. By applying our result to specific norms, we cast known measurement bounds in our general framework (for the ℓp norms, p ∈ [1,2]) as well as provide new, measurement-efficient schemes (for the Earth-Mover Distance norm). The latter result directly implies more succinct linear sketches for the well-studied planar k-median clustering problem. Finally, our lower bound for the doubling dimension of the EMD norm enables us to address the open question of [Frahling-Sohler, STOC'05] about the space complexity of clustering problems in the dynamic streaming model.