PaperlayerView exact revision on arXiv

Source-linked AI summary

Input Sparsity Time Low-Rank Approximation via Ridge Leverage Score Sampling

Michael B. Cohen, Cameron Musco, Christopher Musco

arXiv:1511.07263v2cs.DScs.LG

TL;DR

The paper addresses the difficulty of obtaining fast, representative column samples for low-rank approximation when prior leverage scores are expensive or unstable. It introduces recursive ridge leverage score sampling, achieving input-sparsity-time low-rank approximation while supporting projection-cost preservation, column subset selection, and single-pass streaming. The approach also provides flexibility for sparse, structured, and kernel-matrix settings, though streaming projection-cost preservation requires careful handling of unknown sampling probabilities.

  • Problem

    Prior low-rank leverage scores are as difficult to compute as low-rank approximation and can change drastically under small matrix perturbations, limiting fast sampling algorithms.

  • Method

    The paper introduces ridge leverage score probabilities approximated by a recursive sampling algorithm, using sampled columns to construct low-rank sketches.

  • Results

    Input-sparsity-time methods achieve a (1 + ǫ) Frobenius-norm approximation, while the paper's samples also provide projection-cost preservation and (1 + ǫ) column subset selection guarantees.

  • Takeaways & Limitations

    The sampling approach preserves sparsity and structure and enables the first space-efficient single-pass streaming algorithms for column subset selection and projection-cost preserving sampling.

  • Takeaways & Limitations

    In streaming projection-cost preservation, inverse-probability reweighting is complicated because the true probability used to sample each column is unknown.

Abstract

from arXiv · show

We present a new algorithm for finding a near optimal low-rank approximation of a matrix $A$ in $O(nnz(A))$ time. Our method is based on a recursive sampling scheme for computing a representative subset of $A$'s columns, which is then used to find a low-rank approximation. This approach differs substantially from prior $O(nnz(A))$ time algorithms, which are all based on fast Johnson-Lindenstrauss random projections. It matches the guarantees of these methods while offering a number of advantages. Not only are sampling algorithms faster for sparse and structured data, but they can also be applied in settings where random projections cannot. For example, we give new single-pass streaming algorithms for the column subset selection and projection-cost preserving sample problems. Our method has also been used to give the fastest algorithms for provably approximating kernel matrices [MM16].

1 Introduction

Low-rank approximation seeks a near-best rank-k representation of a matrix, but traditional and projection-based methods can be costly or unsuitable for sparse, structured, streaming, and kernel settings. This paper introduces recursive ridge leverage score sampling to obtain comparable input-sparsity-time guarantees while enabling these broader applications.

  • Motivation: Low-rank approximation seeks a rank-k matrix close to A under spectral or Frobenius error, but SVD requires O(nd^2) time.Iterative methods reduce per-iteration cost to O(nnz(A) · k), while input-sparsity-time methods target O(nnz(A)) plus lower-order terms.
  • Motivation: Prior sparse random projection methods achieve (1 + ǫ) Frobenius error in input sparsity time.Their runtime is O(nnz(A)) + ˜O(n · poly(k, ǫ)).
  • Core approach: The paper replaces random projections with recursive sampling of ˜O(k/ǫ) columns using efficiently approximable ridge leverage scores.Ridge leverage scores address the difficulty that prior low-rank leverage scores are expensive to compute and sensitive to perturbations.
  • Core guarantees: Ridge leverage score sampling produces a projection-cost preserving sketch and, with a smaller sample, a (1 + ǫ) column subset selection guarantee.The paper presents these guarantees through a unified intermediate result, and the projection-cost sketch supports constrained problems including k-means clustering.
  • Applications: Sampling preserves sparsity and structure, potentially improving performance on sparse or structured data where random-projection sketches become dense and unstructured.The methods also extend to space-efficient single-pass streaming algorithms for column subset selection and projection-cost preserving sampling.
  • Applications: Recursive ridge leverage score sampling enables provable kernel approximation with time linear in n without computing the full kernel matrix.The follow-up method evaluates only a small fraction of the dot products required to build the matrix and does not require coherence or regularity assumptions.

2 Technical Background

Low-rank approximation seeks a near-best rank-k representation, while sketching compresses A into a smaller column sample whose span or projection costs preserve the original problem. Ridge leverage scores replace unstable truncation-based scores with a smoother, more stable importance measure.

  • Low-rank approximation: SVD provides the best rank-k approximation by projecting A onto its top k singular-vector span.The approximation goal is measured using the Frobenius norm in the supplied formulation.
  • Sketching: Sketching compresses A into a much smaller matrix C, after which post-processing extracts an approximation to A’s top left singular-vector span.Random sampling constructs C by selecting and possibly reweighting columns, unlike random projection’s linear combinations.
  • Sampling guarantees: Column subset selection requires C’s column span to contain a good rank-k approximation, while projection-cost preservation requires C to approximate every rank-k projection cost.The latter also supports constrained low-rank problems such as k-means clustering of A’s rows.
  • Leverage scores: Traditional low-rank leverage scores are defined from A_k and can change drastically under small perturbations because A_k may be nonunique or unstable.This instability limits efficient approximation from samples or partial matrix information.
  • Ridge leverage scores: Ridge leverage scores regularize AAT by adding λI, smoothly downweighting small singular directions instead of truncating the spectrum.The paper argues that regularization is more natural and stable because it depends on the residual error rather than a specific low-rank approximation.

3 Core Sampling Results

The paper establishes ridge-leverage-score sampling as a unified route to spectral sketch guarantees. The sampled columns spectrally approximate A with an additive error governed by λ = ∥A−A_k∥_F^2/k, yielding the guarantees needed for later sampling results.

  • Unified guarantee: Ridge leverage scores can construct sketches satisfying both column-subset-selection and projection-cost-preservation guarantees.The paper introduces an intermediate additive-multiplicative spectral guarantee to treat these outcomes uniformly.
  • Spectral approximation: The selected columns spectrally approximate A up to additive error determined by λ = ∥A−A_k∥_F^2/k.This resembles a subspace embedding, but the additive component captures the low-rank approximation residual.
  • Spectral approximation: Sampling by ridge leverage scores is equivalent to sampling by standard leverage scores of an augmented matrix [A, √λI].A matrix Chernoff bound gives a subspace embedding for AAT + λI; subtracting the identity yields the mixed bound.
  • Proof strategy: The proof controls the sampled-matrix deviation using a stable-rank matrix Bernstein inequality, bounding each summand’s spectral norm and the variance of the deviation.The argument applies leverage-score bounds and stable-rank concentration to establish the target spectral inequality.
  • Result: With sufficiently accurate ridge-score overestimates, the sampled matrix satisfies the additive-multiplicative spectral approximation with high probability.The construction samples and rescales columns according to probabilities derived from the score overestimates.

3.1 Projection-Cost Preserving Sampling

Ridge-leverage-score sampling yields projection-cost preserving column samples by combining multiplicative control on dominant singular directions with additive control on the tail. The resulting sample supports rank-k projection-cost comparisons with near-preserving error.

  • Projection-cost preservation: Ridge leverage scores provide a basic building block for constructing projection-cost preserving samples in the input-sparsity-time algorithm.Theorem 6 derives this guarantee from the additive-multiplicative spectral approximation of Theorem 5.
  • Projection-cost preservation: When ridge-score estimates are within a constant factor of the true scores, the sample size is t = O(k log(k/δ)/ǫ^2).The guarantee holds with probability 1−δ and applies to every rank-k orthogonal projection.
  • Proof strategy: The proof splits AAT and CCT into top singular directions and remaining tail directions, because the theorem gives different approximation controls in these regions.The head receives multiplicative spectral control, whereas the lower singular directions require a separate additive analysis.
  • Proof strategy: For A, cross terms between head and tail components vanish because the corresponding singular subspaces are orthogonal.The analogous sampled terms generally do not vanish, making the sampled-matrix analysis more difficult.
  • Proof conclusion: The analysis bounds the tail and cross contributions before combining them with the head bound to obtain the final projection-cost guarantee.The proof uses trace comparisons, Cauchy–Schwarz, and the fact that A_k is the best rank-k approximation.

3.2 Column Subset Selection

Ridge leverage score sampling yields strong column subset guarantees, including (1 + ǫ) error and near-optimal subset size. Its analysis connects nonadaptive ridge leverage sampling to adaptive sampling without requiring adaptivity.

  • Guarantees: Ridge leverage sampling produces a (1 + ǫ) error column subset with probability 1 −δ.The sample is formed by drawing columns according to overestimates of their ridge leverage scores.
  • Guarantees: The sampled set contains a subset of O(∑i ˜τi/ǫ) columns satisfying the column subset selection guarantee.When approximate ridge leverage scores sum to O(k), this yields a near-optimally sized subset with O(k/ǫ) columns.
  • Construction: The method first obtains a constant-error subset, then augments it with columns sampled according to residual-based adaptive probabilities.The initial sample uses O(k log(k/δ)) columns, followed by O(k log(1/δ)/ǫ) additional samples.
  • Nonadaptive sampling: Ridge leverage scores approximate the adaptive sampling probabilities, so additional columns can be sampled nonadaptively while retaining (1 + ǫ) error.Sampling O(k log(1/δ)/ǫ) more columns by ridge leverage score suffices.
  • Subset extraction: A polynomial-time deterministic selection procedure can extract a smaller valid subset from the larger sampled set.The resulting subset has O(∑i ˜τi/ǫ) columns, including O(k + ∑i ˜τi/ǫ) before simplification.

4 Monotonicity of Ridge Leverage Scores

Ridge leverage scores have a monotonicity property under column augmentation: adding columns can only decrease the importance score of an existing column. This stability supports both recursive approximation and streaming algorithms.

  • Significance: This monotonicity is unusual among low-rank leverage scores and is central to the paper’s sampling approach.The passage contrasts ridge leverage scores with prior low-rank leverage scores that lack this property.
  • Monotonicity: Ridge leverage scores of existing columns can only decrease when a new column is appended.The property is formalized for A ∪ x, where x is appended as the final column.
  • Generalized scores: Generalized ridge leverage scores estimate a column’s ridge leverage score using a matrix M rather than A itself.They are used to compute overestimates when working with a smaller sampled representation.
  • Generalized bound: A generalized monotonicity theorem applies when MMT ⪯ AAT, providing the matrix-order condition underlying the score comparison.The theorem handles arbitrary A and M satisfying the stated positive-semidefinite relation.

5 Recursive Ridge Leverage Score Approximation

The paper approximates ridge leverage scores in input-sparsity time through recursive sampling. Uniform subsampling produces a smaller proxy, whose scores guide resampling and ultimately yield efficient ridge-leverage-score estimates.

  • Recursive idea: Recursive sampling uses a uniform column subsample to obtain ridge leverage score overestimates for the full matrix.Monotonicity makes the estimates upper bounds, while the paper shows their total remains small enough for efficient resampling.
  • Score bounding: Reweighting columns can bound all ridge leverage scores by a small constant, making uniform sampling effective.The reweighting matrix W satisfies 0 ⪯ W ⪯ I and reduces excessive scores iteratively.
  • Uniform sampling: A uniform sample of O(k log(k/δ)) columns yields constant-factor ridge leverage score approximations with probability 1 −δ.The construction combines uniform sampling, reweighting, and concentration bounds.
  • Algorithm: Repeated Halving recursively reduces the sample while preserving the approximation conditions needed for ridge leverage score estimation.The algorithm recursively processes large uniform samples before computing generalized scores and resampling the original matrix.
  • Runtime: The score-approximation implementation runs in O(nnz(A) log(d/δ)) + ˜O(nk^2) time.Its linear-algebra operations use column subsets of A, preserving input structure such as sparsity.

6 Streaming Ridge Leverage Score Sampling

The ridge leverage score framework extends to single-pass column streams, enabling space-efficient column subset selection and projection-cost preserving sampling. The streaming algorithms maintain fixed-size samples while refining probabilities as new columns arrive.

  • Space usage: The algorithms eliminate stream-length dependence in storage, keeping a fixed number of columns determined by ǫ and k.The stated space bounds do not account for the precision required to store the real numbers.
  • Implementation: Frequent Directions supplies constant-factor score estimates, while the maintained column sample preserves sparsity and input structure.The sketch may be dense, but precise information is retained in the sampled columns.
  • Column subset selection: A single-pass algorithm computes a (1 + ǫ) error column subset with O(k log k + k log(1/δ)/ǫ) columns and O(nk) additional space.It succeeds with probability 1 −δ.
  • Projection-cost preservation: A single-pass projection-cost preserving sampler uses O(k log(k/δ)/ǫ^2) output columns and O(nk) fixed overhead.During execution it may store O(k log(k/δ)/ǫ^3) columns and succeeds with probability 1 −δ.

A Trace Bound for Ridge Leverage Score Sampling

The trace-bound argument samples columns using overestimates of ridge leverage scores and bounds the resulting residual through column-norm decompositions and concentration inequalities.

  • Ridge leverage-score overestimates define sampling probabilities for constructing the sampled matrix C.The construction uses probabilities proportional to the overestimates and scales sampled columns appropriately.
  • The proof rewrites the relevant Frobenius quantity as a sum over sampled column norms.
  • Chernoff bounds control the resulting random sum after the trace expression is decomposed across columns.
  • A union bound combines the failure events to establish the desired trace guarantee.

B Independent Sampling Bounds

The independent-sampling analysis extends the sampling guarantees to columns selected independently by ridge leverage scores, using a matrix-valued concentration argument. It establishes the target bound while controlling the expected sample size.

  • Independent ridge leverage-score sampling selects each column with probability p_i and rescales selected columns by 1/√p_i.
  • Lemmas 21 and 22 formulate independent-sampling bounds from overestimates of the ridge leverage scores.
  • The proof represents the sampling error with centered matrix-valued random variables and analyzes their spectral norm.
  • After adjusting constants, the concentration statement is equivalent to the target bound, completing the lemma.
  • Stable-rank matrix Bernstein inequalities provide the concentration step needed for the spectral-norm bound.
  • The expected number of sampled columns is at most c log(k/δ), with probability exceeding 1 −δ/2 for the corresponding bound.
Loading 1511.07263v2…