PaperlayerView exact revision on arXiv

Source-linked AI summary

Nearly Optimal Strong Coresets for $\ell_p$ Subspace Approximation

Honghao Lin, Vahab Mirrokni, David P. Woodruff

arXiv:2608.26047v1cs.DS

TL;DR

The paper studies dimension-independent strong coresets that preserve every rank-at-most-k subspace cost, enabling reuse across optimization queries. It develops separate sampling and recurrence analyses for the two p-regimes, obtaining improved ε^-2 accuracy dependence and matching the known lower bound for 1 ≤ p < 2 under stated conditions.

  • Problem

    Strong coresets must preserve every rank-at-most-k subspace cost, while useful summaries should remove both the number of points n and ambient dimension d from the optimization instance.

  • Method

    For 1 ≤ p < 2, the construction implements a low-rank-split sampling procedure, while for p > 2 it preserves truncation in sampling probabilities throughout the row-count recurrence.

  • Results

    The results obtain ε^-2 dependence in both regimes; the coreset size is eO_p(kε^-2) for 1 ≤ p < 2 and eO_p(k^(p/2)ε^-2) for p > 2.

  • Takeaways & Limitations

    For 1 ≤ p < 2, the coreset size matches the known sampling lower bound up to logarithmic factors under the stated parameter conditions, while the p > 2 bound leaves a rank-accuracy gap.

  • Takeaways & Limitations

    For p > 2, the upper bound does not match the known lower bound as a joint function of k and ε.

Abstract

from arXiv · show

We study strong coresets for $\ell_p$ subspace approximation. Given $\A\in\R^{n\times d}$, the goal is to sample and rescale a small number of its rows to form $\Smat\A$ such that \[ \norm{\Smat\A(\I-\Pmat_F)}_{p,2}^p =(1\pm\eps)\norm{\A(\I-\Pmat_F)}_{p,2}^p \] simultaneously for every subspace $F\subseteq\R^d$ of dimension at most $k$, where $\Pmat_F$ is the orthogonal projector onto $F$. Woodruff and Yasuda (FOCS 2025)~\cite{WY25} obtained coreset sizes $\wtO_p(k\eps^{-4/p})$ for $1\leq p<2$ and $\wtO_p(k^{p/2}\eps^{-p})$ for $p>2$. We improve these bounds to $\wtO_p(k\eps^{-2})$ and $\wtO_p(k^{p/2}\eps^{-2})$, respectively. For $1\leq p<2$, our algorithm runs in $\wtO_p(\nnz(\A)+d^ω+k\eps^{-2})$ time. The resulting coreset size matches the known sampling lower bound~\cite{LWW21} up to logarithmic factors when $k+1\geq C\log(1/\eps)$ for an absolute constant $C$. For $p>2$, our algorithm runs in $\wtO_p(\nnz(\A)+d^ω)$ time, matching the running time of the Woodruff--Yasuda framework. We use different techniques in the two regimes. For $1\leq p<2$, we combine a bicriteria low-rank split with Lewis-weight sampling and empirical-process bounds independent of the output dimension. For $p>2$, we give a sharper analysis of the Woodruff--Yasuda construction. By retaining the truncation in its sampling probabilities throughout the row-count recurrence, we show that it achieves the improved $\eps^{-2}$ dependence.

1 Introduction

The paper develops dimension-independent strong row coresets for ℓp subspace approximation, improving accuracy dependence to ε^-2 in both regimes p<2 and p>2. It combines a low-rank-split sampling analysis for p<2 with a sharper recursive analysis for p>2, while identifying an unresolved joint k–ε question for p>2.

  • 1 Introduction: Dimension-independent size is consequential because reduced-instance size affects storage and the running time of later optimization routines.The target size depends on k, ε, and fixed p, but not n or d.
  • 1 Introduction: Strong coresets preserve every rank-at-most-k subspace cost using a small weighted subset of the original rows.This uniform guarantee supports reuse for adaptive queries and downstream optimization.
  • 1.2 Our results: ε^-2 dependence is achieved in both regimes, closing the p<2 gap to the sampling lower bound up to logarithmic factors.For p<2, the result improves the prior ε^-4/p dependence; for p>2, it improves the prior ε^-p dependence.
  • 1.2 Our results: For 1 ≤ p < 2, the algorithm outputs a strong row coreset with nearly optimal rank dependence and an input-sparsity-time construction.The construction uses a bicriteria low-rank split, Lewis-weight sampling, and dimension-independent empirical-process bounds.
  • 1.3 Technical overview: For p > 2, retaining truncation in the recursive row-count analysis changes the fixed-point dependence from ε^-p to ε^-2 while preserving k^p/2 dependence.The same Woodruff–Yasuda sampling rule and recursive framework are retained.
  • 1.4 Open problems: The p>2 upper bound does not yet match the known joint lower bound in k and ε, leaving open whether stronger lower bounds or improved algorithms are possible.In contrast, the p<2 upper bound matches the known sampling lower bound under the stated condition k + 1 ≥ C log(1/ε).

2 Preliminaries

The preliminaries define strong row coresets, sampling models, Lewis weights, and oblivious subspace embeddings. They also establish the prior preprocessing and sampling tools used later.

  • A strong row coreset is a reweighted subset of input rows preserving every rank-at-most-k ℓp subspace-approximation cost.
  • Sampling with replacement draws rows independently from a distribution and rescales each retained row; repeated draws can be merged.
  • Woodruff–Yasuda pre-sparsification provides a dimension-independent weighted row subset with nearly optimal rank dependence and eOp(nnz(A) + d^ω) construction time.
  • Strong row coresets compose: two successive (1 ± ε/3) guarantees yield a (1 ± ε) guarantee while retaining original-row support.
  • For 1 ≤ p < 2, Lewis-weight sampling uses eOp(rε^-2) samples for an r-dimensional subspace-embedding guarantee.
  • An oblivious subspace embedding must preserve all vectors in every fixed low-dimensional subspace independently of the embedding draw.

3 Coresets from a Low-Rank Split for 1 ≤p < 2

For 1 ≤ p < 2, the paper splits the input into a low-rank component and residual, then samples rows using balanced Lewis-weight and residual scores. Dimension-independent empirical-process bounds yield a strong coreset with eOp(kε^-2) samples.

  • The goal is one weighted row sample preserving the subspace cost simultaneously for every F in the family of subspaces of dimension at most k.
  • The split A = B + E uses a low-rank component B spanning F0 and residual rows ei = ai − bi.
  • The sampling distribution combines ℓp Lewis weights of bi with normalized residual masses ρi = ∥ei∥p/R.
  • Theorem 3.1 samples eOp((k + r)ε^-2) rows, up to logarithmic factors and the failure-probability parameter, while preserving all subspace queries.
  • The proof decomposes normalized losses into four scalar coordinate classes whose empirical complexities depend on k or r, not the output dimension d.

4 Input-Sparsity-Time Construction for 1 ≤p < 2

The implementation constructs the low-rank split and estimates its residual and Lewis-weight scores using sparse sketches and iterative leverage-score routines. Combined with pre-sparsification, it achieves an efficient strong row coreset construction.

  • The procedure first applies Woodruff–Yasuda pre-sparsification so later logarithmic factors depend on k and ε rather than the original row count n.
  • A sparse right OSE embeds the data, after which sketched least-squares regression constructs the low-rank approximations bi and residuals ei.
  • Lewis weights of the low-rank component are estimated through Cohen–Peng iterations implemented with input-sparsity-time leverage-score routines.
  • The resulting algorithm returns a (1 ± ε) strong row coreset with probability at least 5/6.
  • The lower bound requires eΩp(kε^-2) rows when k + 1 ≥ C log(1/ε), making the worst-case size eΘp(kε^-2) in that range.

5 One-Round Sampling for p > 2

For p > 2, the paper sharpens the analysis of Woodruff–Yasuda’s one-round sampling theorem. Uniform parameter tuning controls multiplicative and additive errors simultaneously over all rank-at-most-k subspaces.

  • The section analyzes root ridge leverage score sampling and its row-count behavior for p > 2.
  • Woodruff–Yasuda’s one-round theorem provides a simultaneous guarantee for every F in the rank-at-most-k subspace family.
  • Uniform tuning selects the internal accuracy ζ so that both multiplicative and additive errors are bounded by a prescribed θ.
  • The tuned sampling threshold is explicitly bounded, allowing the same parameter choice throughout the recursive procedure.

6 Threshold-aware row-count analysis

The p > 2 analysis keeps truncation inside the sampling probabilities, yielding a sharper expected row-count bound and enabling high-probability control for recursive reduction.

  • Threshold summation: The retained row count is controlled by truncated powers of ridge leverage scores, whose sum is bounded using linear ridge leverage score mass.Keeping the full sampling scale inside the truncation is the crucial step.
  • Threshold summation: A threshold-summation lemma bounds sums of min{1, y^v} terms by the corresponding linear mass, with the c^(1/v) factor being tight.Equality occurs at τ_i = c^(-1/v).
  • One-round bound: For p > 2, Corollary 6.2 converts the threshold bound and ridge-leverage mass estimate into an expected one-round row-count bound.The corollary applies to an N-row matrix with parameters k and α.
  • High-probability control: Bernoulli row-count concentration upgrades the expected one-round bound to a high-probability statement needed by the recursive construction.The concentration argument uses Bernstein’s inequality for independent Bernoulli variables.
  • High-probability control: Combining the concentration result with the one-round sampling analysis yields a bounded row count with probability at least 1 − η.The result is assembled from Corollary 6.2 and Lemma 6.3.

7 Recursive Construction for p > 2

For p > 2, the paper recursively applies a one-round sampler to weighted active matrices, controls row counts through a fixed-point recurrence, and composes per-round guarantees into a final strong coreset.

  • Construction: The recursive construction repeatedly samples the current weighted active matrix and stops when its row count falls below a prescribed threshold or after a bounded number of rounds.A final pre-sparsification is applied after the recursive reduction.
  • Construction: Each round computes ridge leverage scores, samples rows independently, and only deletes rows, so the active row count never increases.The procedure executes at most r rounds.
  • Row-count analysis: The fixed-point recurrence and high-probability concentration establish the recursive output’s row bound after at most r rounds.The recurrence is analyzed after a deterministic fixed-point calculation and a union bound over rounds.
  • Row-count analysis: The recursive row-count guarantee holds across all executed rounds with probability at least 1 − rη0, supporting the final high-probability bound.The analysis also handles early stopping and the full-r-round case.
  • Approximation composition: Additive-multiplicative guarantees from individual rounds compose into a multiplicative guarantee when the accumulated round error Tθ is sufficiently small.The proof controls the optimum through the same recurrence used for arbitrary candidate subspaces.
  • Recursive reduction: Theorem 7.4 outputs a weighted row subset with the desired approximation guarantee and a bounded number of rows, with success probability at least 1 − η.The guarantee follows by combining the row bound with per-round approximation events.
  • Implementation: Using approximate ridge leverage scores and an estimated residual scale preserves the bounds up to constants and gives recursive-reduction time eO_p(nnz(A) + d^ω).Exact values of λ_A and the exact scores are unnecessary.
  • Final construction: Applying pre-sparsification followed by recursive reduction yields a weighted original-row subset preserving all rank-at-most-k subspace costs within 1 ± ε.The two stages together fail with total probability at most δ.

A Auxiliary Process Estimates for 1 ≤p < 2

The auxiliary estimates decompose normalized query loss into four coordinates and bound the relevant directional and duality-map classes without dependence on the ambient output dimension.

  • Auxiliary estimates: Theorem 3.1 analyzes normalized query loss through four coordinates, with directional and duality-map estimates controlling separate components.A final Lewis-weight estimate and scalar composition lemma recover the full loss.

A.1 Directional and duality-map classes

The appendix bounds the complexity of directional and duality-map function classes using Gaussian sketches, quotient-space geometry, and sign-pattern counting, including the p = 1 endpoint.

  • Directional and duality-map classes: The directional entropy lemma treats maps from an r-dimensional space into a Hilbert space while controlling complexity through r, support size, and bounded vector norms.Its formulation includes the convention J1(0) = 0.
  • The p = 1 endpoint: The p = 1 proof instead uses zero-inclusive sign counting for Gaussian sketches, yielding a covering bound based on [C(M + r + 2)]^(Lr).The sign count includes zero signs, avoiding a separate continuity argument.
  • Duality-map entropy: For 1 < p ≤ 2, the duality-map class has logarithmic covering dependence on M + r + 2, δ, and the empirical p-energy.At p = 1, the entropy is eO(B r δ^-2) with radius O(B).
  • Gaussian sketching: Gaussian sketching approximates many packed functions simultaneously by reducing the problem to a quotient space whose dimension is at most Lr.The seminorm identifies matrices that act identically on the supported query vectors.
  • Gaussian sketching: The quotient-space packing argument controls covering numbers by constructing a shared sketch and retaining a large separated subset after removing exceptional functions.The retained packing remains separated by the triangle inequality.
  • The p = 1 endpoint: At p = 1, the argument handles zero coordinates and zero images directly, preserving the entropy bound across strata where A y_i = 0.Positive α_i disappear inside J1, while zero α_i contribute fixed zero coordinates.
  • Conditional complexity: For p > 1, conditional duality-map complexity follows by applying a truncated Dudley bound to the entropy and radius estimates.The zero map and negative functions are adjoined at only constant-factor cost.

A.2 Entropy of row-augmented subspace distances

The section develops entropy bounds for distances to row-augmented subspaces, using Gaussian compression and pseudodimension control. The resulting bounds avoid dependence on the ambient dimension and support rank-at-most classes.

  • Rank-at-most classes: The rank-at-most corollary extends the entropy control across dimensions 0 through k and remains independent of the number of rows and ambient dimension.Taking the union over k+1 strata adds only log(k+1) to the entropy.
  • Theorem A.4: Theorem A.4 bounds row-augmented subspace entropy by compressing packings to k+O_p(δ^-2) dimensions and retaining a constant fraction.The compressed class is then analyzed using Grassmann charts and pseudodimension bounds.
  • Row-augmented spaces: Theorem A.4 uses row-dependent augmented spaces F+span{b_i}, whose dimensions are k or k+1 depending on whether b_i belongs to F.The analysis decomposes each unit vector into its projection and orthogonal residual relative to these spaces.
  • Gaussian compression: The Gaussian construction normalizes projected distances to remove deterministic shrinkage caused by the dimension of the orthogonal complement.Without normalization, the squared deviation need not be O(1/s) when k≫s.
  • Pseudodimension: The compressed class has pseudodimension at most C d_ch log(L+2), with d_ch=kℓ, after accounting for Grassmann charts and zero-denominator strata.This bound is obtained through semialgebraic sign-assignment counting.

A.3 A scalar composition lemma

This section establishes a scalar composition lemma for ℓ_p quantities when 1≤p≤2. It handles zero amplitudes, sign changes, and exact cancellation while preserving Lipschitz control.

  • Lemma A.6: Lemma A.6 defines a scalar decoder relating powered amplitudes, signed cross terms, and |a+σb|^p for 1≤p≤2.The p=1 convention sets the cross-term quantity to zero when a=0.
  • Lipschitz control: The decoder is Lipschitz with a constant depending only on p, including sign changes, exact cancellation, and zero amplitudes.The proof treats equal-sign and opposite-sign tuples separately.
  • Proof structure: For 1<p≤2, normalization by S=T+V expresses the quantities through scalar functions of t and σh(t), enabling interval-wise Lipschitz bounds.The endpoint intervals and the middle interval are handled separately.
  • Boundary cases: The argument covers asymmetric zero-amplitude cases directly and uses continuity at the cancellation point.At p=1, reverse-triangle arguments handle positive amplitudes, while zero cases are treated separately.

A.4 Lewis-weight control of the low-rank term

The section derives Lewis-weight empirical-process bounds for low-rank terms in the regime 1≤p<2. It reduces Hilbert-valued sampling to scalar bounds and obtains complexity control independent of output dimension.

  • Empirical-process reduction: The resulting Lewis-weight empirical bound controls normalized low-rank costs through a scalar first-moment estimate and a scalar Rademacher bound.The argument lifts the scalar result to Hilbert-valued linear maps using a Gaussian-mixture representation.
  • First-moment bound: Corollary A.7 supplies the first-moment Cohen–Peng bound under a Lewis-weight sampling condition, with only polylogarithmic dependence on the augmented problem size.Auxiliary rows enforce the target Lewis-weight scale without changing the sampling law.
  • Scalar empirical bound: Lemma A.8 converts the first-moment estimate into a scalar Lewis-weight empirical bound involving the sampling ratio K and logarithmic factors.The proof handles both large- and small-sample regimes before combining them.
  • Low-rank terms: Theorem A.9 extends the scalar result to low-rank Hilbert-valued terms by representing normalized functions as mixtures of scalar functions.Convexity transfers the scalar supremum bound to the Hilbert-valued class.
  • Necessity of K/m: The K/m term is necessary in general: for n=r, uniform sampling, and coordinate vectors, K=r and one-sample absolute complexity is r.This example identifies a concrete boundary on the empirical bound.
Loading 2608.26047v1…