PaperlayerView exact revision on arXiv

Source-linked AI summary

Iterative Row Sampling

Mu Li, Gary L. Miller, Richard Peng

arXiv:1211.2713v2cs.DS

TL;DR

For tall, thin regression matrices, existing general-purpose methods can take more than quadratic time and space, while input-sparsity algorithms have practical performance benefits from iterative use. The paper iteratively refines row-sampling probabilities, using approximate leverage scores and short matrix estimates to reduce problem size. If τ̃ ≥ τ, the sampling lemma returns O(log d ∥τ̃∥1 ϵ−2) rows; the ℓ2 row bound improves on O(d2) and matches the best known oblivious-projection bound.

  • Problem

    For tall, thin regression matrices, existing general-purpose methods can take more than quadratic time and space, while input-sparsity algorithms have practical performance benefits from iterative use.

    Source: §1 · pp. 1–2, §2 · p. 4

  • Method

    The paper iteratively refines row-sampling probabilities, using approximate leverage scores and short matrix estimates to reduce problem size.

    Source: §1 · p. 2, §4 · p. 7, §4.1 · p. 7

  • Results

    If τ̃ ≥ τ, the sampling lemma returns O(log d ∥τ̃∥1 ϵ−2) rows; the ℓ2 row bound improves on O(d2) and matches the best known oblivious-projection bound.

    Source: §2 · p. 4, §4 · p. 7

  • Takeaways & Limitations

    The approaches show that ℓ2-based sampling can support row reduction under ℓp objectives, with the paper presenting the ℓ1 extension for simplicity.

    Source: §2 · p. 5, §5.1 · p. 14

    The ℓ2 algorithm does not immediately extend to low-rank approximation, and the ℓp analysis uses concentration bounds as a black box.

    Source: §2 · p. 5

Abstract

from arXiv · show

There has been significant interest and progress recently in algorithms that solve regression problems involving tall and thin matrices in input sparsity time. These algorithms find shorter equivalent of a n*d matrix where n >> d, which allows one to solve a poly(d) sized problem instead. In practice, the best performances are often obtained by invoking these routines in an iterative fashion. We show these iterative methods can be adapted to give theoretical guarantees comparable and better than the current state of the art. Our approaches are based on computing the importances of the rows, known as leverage scores, in an iterative manner. We show that alternating between computing a short matrix estimate and finding more accurate approximate leverage scores leads to a series of geometrically smaller instances. This gives an algorithm that runs in $O(nnz(A) + d^{\omega + \theta} \epsilon^{-2})$ time for any $\theta > 0$, where the $d^{\omega + \theta}$ term is comparable to the cost of solving a regression problem on the small approximation. Our results are built upon the close connection between randomized matrix algorithms, iterative methods, and graph sparsification.

1 Introduction

Tall, thin regression problems motivate faster algorithms because existing general-purpose methods can require more than quadratic time and space. The paper adapts practical iterative approaches to reduce problem size while retaining theoretical guarantees.

1 Introduction

  • More than quadratic time and space make general-purpose regression methods unsuitable for data with nnz(A) often reaching 10^9.The cited bounds are O((n+d)^3/2 d) generally and O(nd^(ω−1)) for ℓ2 regression.Source: §1 · p. 1
  • Tall, thin matrices arise when many data points occupy fewer dimensions or when much data are collected about a few objects.For ℓ2 regression, solving is equivalent to a linear-system solve involving A^T A; when n≫d, inverting this d×d matrix costs less than examining A’s nonzeros.Source: §1 · pp. 1–2
  • Input-sparsity regression algorithms reduce a tall matrix to a poly(d)-sized approximation in one transformation, but practice often favors iterative use of higher-error variants.The paper designs algorithms motivated by these practical adaptations.Source: §1 · p. 2
  • The proposed algorithms construct B with poly(d) rows and run in O(nnz(A)+d^(ω+θ)) time, with the final term covering inverses and change-of-basis matrices.The paper says this term is lower order because regression on d×d matrices takes at least d^ω time.Source: §1 · p. 2
  • A constant-factor size reduction can suffice for a linear-time algorithm, allowing weaker statistical-projection guarantees than direct reduction to poly(d)-sized instances.The paper distinguishes its ℓ2 and ℓp approaches and notes that ℓ2 projections need not preserve A’s column space to yield adequate sampling probabilities.Source: §1 · pp. 2–3

2 Overview

The overview presents iterative reduction and recovery as a way to shrink regression instances, with distinct ℓ2 and ℓp approaches and input-sparsity-time guarantees.

  • Each iteration reduces A to a smaller instance, recovers a higher-quality approximation, and uses it to estimate row-sampling probabilities for the original matrix.The sequence of shrinking matrices and propagated probabilities forms a tail-recursive process that can also be viewed iteratively.Source: §2 · pp. 3–4, Figure 1 · p. 4
  • For ℓ2, a simple random projection may distort the matrix and fail to preserve its null space, but one-sided bounds suffice for recovery without accumulating reduction error.The reduction distortion can be set to κ = d^θ for arbitrarily small θ > 0; the sampling process absorbs the resulting factor.Source: §2 · p. 4
  • O(nnz(A) + d^(ω+θ)ε^-2) time produces O(d log d ε^-2) rescaled rows, improving [CW12] and matching [NN12] in row count.The comparison notes that the leading nnz(A) term avoids an ε^-1 factor, at the cost of worse dependence on θ than [NN12].Source: §2 · p. 4
  • For ℓp norms, choosing an appropriate intermediate ℓp′ norm for sampling probabilities gives A(i + 1) O(n(i)c_p poly(d)) rows, with c_p < 1, reducing rows doubly exponentially to O(poly(d)).To the authors’ knowledge, this is the first result using ℓ2 row sampling as the primary routine, yielding the first algorithms for p ≠ 1, 2 that do not use ellipsoidal rounding.Source: §2 · p. 4
  • The ℓp extension is constrained by a discontinuity between ℓ2 and ℓp sampling bounds, so the paper presents the corresponding algorithm only for ℓ1.The method is also stated to yield poly(d) rows for p ≥ 4 and fewer rows than its stated bound for 1 ≤ p < 4.Source: §2 · p. 5
  • The overview identifies high-probability routines, preservation of original row structure, and the sufficiency of good ℓ2 approximations for iterative ℓp reductions as further strengths.The ℓp analysis also relies on concentration bounds as a black box; the ℓ2 method does not immediately extend to low-rank approximation.Source: §2 · p. 5

3 Preliminaries

The preliminaries define the paper’s vector and matrix notation, describe row sampling and leverage scores, and state an assumption used to control the number of iterations.

  • The paper uses ∥x∥p for a vector’s ℓp norm, with p = 1 and p = 2, and defines row, column, and entrywise matrix-norm notation.The entrywise matrix p-norm treats all matrix entries as one vector; for p = 2 it is the Frobenius norm.Source: §3 · p. 5
  • For ℓ2, AT A is positive semidefinite, and AT A ⪯ BT B is equivalent to ∥Ax∥2 ≤ ∥Bx∥2.The text also defines pseudoinverses and orthogonal projectors for use with these matrix relations.Source: §3 · pp. 5–6
  • Sample(A, p) keeps row i with probability min{1, pi}, rescales it to preserve its expected value, and returns at most O(|p|1) rows.Source: §3 · p. 6
  • Leverage scores are associated with row-sampling probabilities, and the paper treats sampling and estimation algorithms as robust routines suitable for iterative use.The general p-norm definition uses row norms of a basis for A’s column space; the text notes simplifications for p = 2.Source: §3 · p. 6
  • The analysis assumes n = poly(d); when n is much larger, padding sampling probabilities can reduce the problem to poly(d)-scale steps.The text states that this yields a matrix with O(nnz(A)/poly(d)) rows that can be handled in O(nnz(A)) time using suitable routines.Source: §3 · p. 6

4 Iterative Row Sampling for ℓ2

The section develops iterative ℓ2 row sampling using generalized stretch to estimate leverage scores and projections to shrink the matrix. Its algorithm propagates score estimates backward through progressively smaller instances to obtain a high-probability row-sampling result.

4 Iterative Row Sampling for ℓ2

  • Rather than directly approximating A^T A, the method uses robust concentration bounds so even crude leverage-score estimates can support sampling.Directly obtaining high-quality leverage scores would itself require a high-quality approximation of A^T A.Source: §4 · p. 7

4.1 Generalized Stretch and its Estimation

  • Generalized stretch computes row scores against a reference matrix B; when reference matrices are sufficiently close, stretch can upper-bound leverage scores for sampling.The original statistical leverage score is recovered when the reference is A.Source: §4.1 · p. 7

4.2 Reductions and Recovery

  • Gaussian (R, k)-projections preserve block stretch with high probability, and scaled projected stretch upper-bounds original-block leverage scores.The reduction combines each block into fewer rows before these estimates are used for recovery.Source: §4.2 · pp. 9–10

4.3 Iterative Algorithm

  • Each round projects row blocks to smaller matrices, then propagates approximate leverage-score bounds backward to sample progressively smaller instances.The algorithm maintains a small approximation at each level and applies the final sampling step to B(0).Source: §4.3 · pp. 10–12
  • O(nnz(A) + d^(ω+4θ)ϵ^-2) time yields B with O(d log d ϵ^-2) scaled input rows, with failure probability at most d^-c.The final sampling step is stated to achieve the row-count bound.Source: §4.3 · pp. 12–13

5 Algorithm for Preserving ℓp-norm

The section develops iterative row sampling to preserve ℓp norms, using approximate bases and sampling probabilities to reduce large matrices to smaller ones. It extends the reduction through repeated iterations and, for selected p ranges, tighter leverage-score estimates.

5 Algorithm for Preserving ℓp-norm

  • For 1 ≤ p ≤ 2, O(1) approximations use p-stable distributions; for p ≥ 2, the 2-norm is a surrogate at the cost of more rows, and leverage-score estimation and sampling form one black box.Source: §5 · p. 14

5.1 Sampling Using ℓ2-leverage scores

  • The algorithm uses a nearly orthonormal ℓ2 basis to sample under ℓp, with each reduction geometrically shrinking the row count when p < 4.A single application may not suffice because the bound depends on n; the reduction is therefore iterated.Source: §5.1 · pp. 14, 16
  • Bucketing rows by nonzero count ensures geometric size reduction across iterations, at the cost of an extra log d factor in the final row count.This addresses cases where most nonzeros are concentrated in a few rows.Source: §5.1 · p. 17
  • Sampling each iteration using the latest approximation on a reduced matrix addresses error buildup while retaining O(nnz(A))-scale work.The procedure limits calls to ReduceP to O(log d).Source: §5.1 · pp. 17–18
  • For p < 4, repeated row reduction yields a poly(d)-row sample in O(nnz(A) + d^ω log d) time when rows have comparable sparsity.The iteration reaches the target row count in O(log log(n/d)) steps; bucketing rows by sparsity adds a log d factor to the final row count.Source: §5.1 · pp. 17–18

5.2 Fewer Rows by Iterating Again

  • A p′-norm approximation for leverage-score computation can further reduce the row count; the improvement is shown for 1 ≤ p ≤ p′ ≤ 2, and the method applies for all 1 ≤ p ≤ 2.Source: §5.2 · pp. 19–20
  • For p ≥ 4, multiple iterations can produce poly(d)-sized samples, but the paper omits this extension because it yields significantly more rows.Three or more steps do not significantly improve the bound when p = 2, where the method can obtain samples of about d rows.Source: §5.2 · p. 20

A.1 Properties of Generalized Stretch

The appendix begins proofs of facts about generalized stretch, including row-wise behavior and a null-space consequence.

A.1 Properties of Generalized Stretch

  • The proof of Fact 4.4 reduces the argument to a single row because stretch and Frobenius norm act independently on rows.Source: §A.1 · p. 22
  • The condition in Lemma 4.3 implies that the two matrices have identical null spaces.The proof then applies this fact to a vector.Source: §A.1 · pp. 22–23

A.2 Estimation of Generalized Stretch

The appendix describes estimating upper bounds on row stretch using randomized projections and an approximation matrix. It also gives an alternative factorization that avoids computing a matrix square root.

A.2 Estimation of Generalized Stretch

  • With probability at least 1 − d^-c, ApproxStr returns upper bounds on row stretches using a Gaussian projection and an approximation B satisfying κA^T A ⪯ B^T B ⪯ A^T A.The input parameter R controls the allowed estimation error.Source: §A.2 · p. 23
  • The factor (B^T B)^† 1/2 can be replaced by a matrix whose product with its transpose is B^T B, avoiding the square-root computation.The paper notes both approaches take O(md^(ω−1)) time theoretically.Source: §A.2 · p. 23
  • The estimates have total running time O(k(nnz(A) + d^2) + (nb + d)d^(ω−1)).Source: §A.2 · p. 24

A.3 Estimation of p-Norm Leverage Scores

The appendix estimates p-norm leverage scores with dimensionality reduction, using p-stable projections below p = 2 and an ℓ2 surrogate for p ≥ 2.

A.3 Estimation of p-Norm Leverage Scores

  • For 0 < p < 2, p-stable projections estimate row norms with O(log_R d) projection dimensions and failure probability d^-c.The method applies the projection to AC and computes the resulting rows in O(nnz(A) log_R d) time.Source: §A.3 · p. 24
  • For p ≥ 2, the method uses the ℓ2 norm as a surrogate, accounting for the resulting distortion in the number of sampled rows.The stated distortion factor is O(d^(p/2−1)).Source: §A.3 · p. 24

B Deferred Proofs from Section 4

The deferred proofs in Section 4 develop block-matrix comparisons and Gaussian bounds for transformed matrices. They also use an extended range-space basis to establish a claim about C and C + D.

Loading 1211.2713v2…