Research map / Learning theory and algorithms / Matrix and tensor methods

Streaming Algorithms For $\ell_p$ Flows and $\ell_p$ Regression

ICLR 2025 · Learning theory and algorithms › Matrix and tensor methods · approach: Low-rank approximation theory

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's abstract only. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Initiates one-pass streaming algorithms for underdetermined ℓp linear regression (min ||x||_p s.t. Ax=b) and related ℓp flow problems.

Problem

One-pass streaming computation of minimum-norm solutions to underdetermined ℓp linear regression, min over Ax=b of ||x||_p with n much smaller than d, which generalizes basis pursuit (p=1) and least-squares minimum-norm solutions (p=2).

Approach

Extends streaming techniques to underdetermined ℓp regression and ℓp flow problems in a single pass over the data; the abstract is truncated so the specific algorithmic construction is not stated.

Closest papers by meaning

• High-Dimensional Geometric Streaming for Nearly Low Rank Data (ICML 2024 · similarity 0.89)
• Optimal bounds for $\ell_p$ sensitivity sampling via $\ell_2$ augmentation (ICML 2024 · similarity 0.86)
• Learning-Augmented Streaming Algorithms for Approximating Boolean Max-CSPs (NeurIPS 2026 · similarity 0.86)
• Turnstile $\ell_p$ leverage score sampling with applications (ICML 2024 · similarity 0.86)
• Improved Sample Complexity for Private Nonsmooth Nonconvex Optimization (ICML 2025 · similarity 0.85)
• Near-optimal Active Regression of Single-Index Models (ICLR 2025 · similarity 0.85)