Leveraging Well-Conditioned Bases: Streaming & Distributed Summaries in Minkowski p-Norms

2018/07/06 by Graham Cormode, Cormode, Graham, Charlie Dickens +3
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.1807.02571

openalex publication_date 2018/07/06 · openalex created_date 2024/04/11 · openalex updated_date 2026/07/28

Abstract

Work on approximate linear algebra has led to efficient distributed and streaming algorithms for problems such as approximate matrix multiplication, low rank approximation, and regression, primarily for the Euclidean norm ℓ₂. We study other ℓ_p norms, which are more robust for p < 2, and can be used to find outliers for p > 2. Unlike previous algorithms for such norms, we give algorithms that are (1) deterministic, (2) work simultaneously for every p ≥ 1, including p = ∞, and (3) can be implemented in both distributed and streaming environments. We apply our results to ℓ_p-regression, entrywise ℓ₁-low rank approximation, and approximate matrix multiplication.

Related

• Streaming and Distributed Algorithms for Robust Column Subset Selection
• Streaming Symmetric Norms via Measure Concentration
• Approximating q → p Norms of Non-Negative Matrices in Nearly-Linear Time
• Low Rank Approximation with Entrywise ℓ₁-Norm Error
• Matrix Norms in Data Streams: Faster, Multi-Pass and Row-Order