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

High-Dimensional Geometric Streaming for Nearly Low Rank Data

ICML 2024 · Learning theory and algorithms › Matrix and tensor methods · approach: Randomized sketching for matrices · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

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

Gives a deterministic single-pass streaming strong coreset for l_infinity subspace approximation via online rank-k ridge leverage scores, extends to l_p via exponential-variable scaling, and improves Woodruff–Yasuda geometric streaming (width, convex hull, volume) for nearly low-rank data.

Problem

Streaming l_p subspace approximation (including l_infinity) and high-dimensional geometric streaming problems such as width and John ellipsoid estimation, especially when data is nearly rank-k, where prior streaming methods need Omega(d^2) space.

Approach

A deterministic online algorithm that keeps a row if its rank-k online ridge leverage score with respect to the currently selected rows is at least 1/(1+1/k); this yields a strong coreset of size O(k log^2(n kappa)) with distortion O(sqrt(k) log(n kappa)). For l_p, rows are scaled by inverse-exponential random variables and the l_infinity coreset is applied.

Key results

• On a synthetic 40,000x10,000 matrix with k=20, the coreset has 28 rows with max distortion at most 1.3433 on the interesting subspaces.
• On a 1836x3264 grayscale image with k=150, the coreset has 312 rows with distortion at most 1.09.
• Lower bound: distortion O(sqrt(k/log n)) for strong coresets requires Omega(n) bits of space for k=Omega(log n).

Limitations

• Coreset size and distortion depend on the condition number kappa, which may be n^{O(k)} in the worst case.
• l_p result only gives poly(k, log n kappa) approximation, not 1+epsilon.
• Alternating minimization refinement has no known solution-quality bounds.

Experimental setup

Datasets: synthetic low-rank plus noise matrix grayscale images (1836x3264, 4690x6000)

Metrics: max distortion of l_infinity cost coreset size width estimation ratio

Baselines: Woodruff and Yasuda (FOCS 2022) SDP-based outer radius rounding l_infinity coreset of size k^{3k}

Builds on: Woodruff and Yasuda (FOCS 2022) l_infinity subspace embedding online ridge leverage scores min-stability of exponential random variables

Closest papers by meaning

• Streaming Algorithms For $\ell_p$ Flows and $\ell_p$ Regression (ICLR 2025 · similarity 0.89)
• Clustering High Dimensional Dynamic Data Streams (ICML 2017 · similarity 0.89)
• Space-Optimal Streaming Algorithms via Efficient Encodings (NeurIPS 2026 · similarity 0.89)
• Leveraging Well-Conditioned Bases: Streaming and Distributed Summaries in Minkowski $p$-Norms (ICML 2018 · similarity 0.87)
• Faster Approximation Algorithms for k-Center via Data Reduction (ICML 2025 · similarity 0.84)
• Coresets for Multiple $\ell_p$ Regression (ICML 2024 · similarity 0.83)