Source-linked AI summary
Uniform Sampling for Matrix Approximation
Michael B. Cohen, Yin Tat Lee, Cameron Musco, Christopher Musco, Richard Peng, Aaron Sidford
TL;DR
Leverage scores enable small spectral approximations but are expensive to compute, while uniform sampling can lose critical row information. The paper shows that uniform samples still provide aggregate leverage information sufficient for iterative improvement, yielding fast row-sampling algorithms and a low-coherence reweighting result.
Problem
Leverage-score sampling gives spectral approximations, but leverage scores are difficult to compute and uniform sampling can discard rows carrying unique directions.
Method
The paper uses uniform samples to form leverage-score estimates, then iteratively resamples rows according to those estimates without projection.
Results
The iterative process quickly converges to a spectral approximation with O(d log d) rows.
Takeaways & Limitations
The algorithms match state-of-the-art runtimes while preserving row structure and sparsity at every intermediate step.
Takeaways & Limitations
Runtime analysis assumes n = O(poly(d)) and uses d^ω for solving d×d systems, though alternative solvers may yield different trade-offs.
Abstract
from arXiv · showhide
Random sampling has become a critical tool in solving massive matrix problems. For linear regression, a small, manageable set of data rows can be randomly selected to approximate a tall, skinny data matrix, improving processing time significantly. For theoretical performance guarantees, each row must be sampled with probability proportional to its statistical leverage score. Unfortunately, leverage scores are difficult to compute. A simple alternative is to sample rows uniformly at random. While this often works, uniform sampling will eliminate critical row information for many natural instances. We take a fresh look at uniform sampling by examining what information it does preserve. Specifically, we show that uniform sampling yields a matrix that, in some sense, well approximates a large fraction of the original. While this weak form of approximation is not enough for solving linear regression directly, it is enough to compute a better approximation. This observation leads to simple iterative row sampling algorithms for matrix approximation that run in input-sparsity time and preserve row structure and sparsity at all intermediate steps. In addition to an improved understanding of uniform sampling, our main proof introduces a structural result of independent interest: we show that every matrix can be made to have low coherence by reweighting a small subset of its rows.
1 Introduction
The paper revisits uniform row sampling, showing that although it may miss information needed for a full spectral approximation, its estimates can still drive iterative improvement. The resulting algorithms avoid projections while preserving row structure and sparsity.
- Results: The methods avoid projections and preserve row structure and sparsity in all matrix operations while matching state-of-the-art runtimes.This addresses prior approaches that mixed rows or had convergence depending on the condition number.
- Motivation: Leverage-score sampling provides spectral approximations, but computing leverage scores requires a pseudoinverse and is as difficult as solving regression.Uniform sampling is attractive but can discard a row that uniquely contributes an orthogonal direction, reducing matrix rank.
- Our Approach: The iterative routine uniformly samples rows, estimates leverage scores using the smaller matrix, resamples according to those estimates, and repeats.Each iteration reduces the matrix before the next estimation-and-resampling step.
- Results: The process quickly converges to a small spectral approximation with O(d log d) rows.Theorem 1 supports progressively reducing the matrix, including halving it when the initial uniform sample has size O(d log d).
- Our Approach: Uniform sampling does not preserve all singular-value information, yet its output can produce leverage-score estimates sufficient for increasingly better approximations.The estimates need not approximate every score multiplicatively; controlling their total sum is enough for the iterative scheme.
- Additional Structural Result: Every matrix can be made low-coherence by reweighting only a small subset of rows, yielding a spectral approximation for a large submatrix.The reweighting result uses a diagonal matrix with only (d/α) entries different from 1.
2 Background
Randomized matrix reduction compresses large problems before deterministic processing. Sampling preserves original rows and their structure, whereas projections can mix rows; the paper focuses on making sampling effective when row importance is difficult to compute.
- Randomized Matrix Reduction: Randomized linear algebra reduces large matrices to smaller approximations that are processed with standard deterministic methods.Reduction methods broadly include random projections and sampling.
- Reduction Methods: Random projections recombine rows or columns, while sampling selects and reweights a smaller set of original rows or columns.Sampling is simpler and faster, but requires an efficiently computable importance measure.
- Approximate Linear Regression: Linear regression requires a spectral approximation, commonly formed with O(d log d/ε^2) rows or with constant-factor approximations used in iterative regression.The latter uses O(d log d) rows.
- Row Sampling: Importance sampling selects O(d log d/ε^2) rows according to leverage scores, but general leverage-score computation requires evaluating (A^⊤A)+.For graph incidence matrices, leverage scores correspond to weighted effective resistances.
- Row Sampling: Sampling preserves row structure and sparsity, whereas prior iterative methods either mix rows through projections or have convergence depending on A’s condition number.Preserving structure can reduce memory requirements and accelerate matrix operations.
3 Notation and Preliminaries
The preliminaries define the spectral and leverage-score quantities used throughout the paper. They connect spectral approximation to preservation of matrix-vector products and singular values, and formalize leverage-score-based sampling.
- Singular Value Decomposition and Pseudoinverse: The reduced singular value decomposition writes A = UΣV⊤, with Σ containing the nonzero singular values and (A⊤A)+ = V(Σ^-1)^2V⊤.This gives A⊤A = VΣ^2V⊤.
- Spectral Approximation: A λ-spectral approximation satisfies λ^-1A⊤A ⪯ ˜A⊤˜A ⪯ A⊤A.The relation preserves the quadratic form and therefore controls matrix-vector-product magnitudes and singular values.
- Leverage Scores: Leverage scores measure row importance in composing the row space, with τ_i(A) ≤ 1 and total leverage score equal to the matrix rank.Rows with unique orthogonal components have leverage score 1, while identical rows have score d/n.
- Leverage Scores: Generalized leverage scores estimate A’s row scores using another matrix B, assigning infinity when a row has a component in ker(B).This prevents sampling from removing a direction that B does not represent.
- Leverage-Score Sampling: If B is a spectral approximation of A, generalized leverage scores provide multiplicative approximations to the corresponding true scores.Leverage-score overestimates can then be used for sampling with high-probability spectral-approximation guarantees.
- Leverage-Score Sampling: With sampling rate α = ε^-2, leverage-score sampling uses at most αc log d∥u∥1 nonzero sampled rows.The sampling probabilities are independently defined from leverage-score upper bounds.
4 Leverage Score Estimation via Uniform Sampling
The uniform-sampling analysis constructs valid leverage-score upper bounds from a uniformly sampled matrix and bounds their expected total. This establishes the estimates needed for iterative row reduction.
- Theorem and Setup: Theorem 1 analyzes a uniformly sampled subset S of m rows and leverage-score estimates computed from the sampled matrix augmented with each queried row.The proof uses S(i), formed by adjoining row i to S.
- Upper-Bound Validity: The constructed estimates satisfy ˜τ_i ≥ τ_i(A) for every row.Rows outside the sample are handled according to whether they are orthogonal to the sampled matrix’s nullspace.
- Expectation Argument: The expected contribution of a row outside the sample is bounded by the average leverage score of a uniformly selected set of m + 1 rows.That average is at most d/(m + 1) because leverage scores sum to rank at most d.
- Consequence: The expectation argument bounds the total estimated leverage scores, enabling the estimates to be used for subsequent spectral-approximation sampling.The resulting upper bounds support the iterative reduction strategy.
5 Coherence Reducing Reweighting
The paper proves that diagonal reweighting can reduce a matrix’s coherence while controlling leverage scores, and that only a small total amount of row weight need be altered. The proof uses an iterative reweighting process whose limit satisfies the theorem’s bounds.
- Theorem 2: Theorem 2 guarantees a diagonal reweighting W with 0 ⪯ W ⪯ I that controls the leverage scores of WA for any positive target vector u.The theorem establishes existence for every matrix A and every vector u with ui > 0.
- Theorem 2: The main result bounds the total reweighted row mass, rather than merely proving that a feasible W exists.The trivial choice W = 0 satisfies one condition, so the substantive claim concerns the limited total weight changed.
- Coherence reduction: Setting ui = α for every row yields a reweighting that reduces coherence to α.Thus, coherence reduction is obtained as a special case of the general leverage-score theorem.
- Proof strategy: The proof repeatedly decreases individual row weights until their leverage scores meet prescribed bounds, using monotonicity and continuity properties.Decreasing one row’s weight lowers that row’s leverage score and raises the scores of other rows; lower semi-continuity supports the limiting argument.
- Proof strategy: The reweighting algorithm maintains nonnegative, monotonically decreasing weights and converges to a limiting matrix W.Rows whose weights reach zero can have leverage score zero, while rank arguments control the remaining active rows.
- Proof strategy: When rows are removed by setting their weights to zero, each such row can reduce the rank, yielding the rank bound rank(W(k)A) ≤ d − |S|.This rank accounting is used to bound the total leverage-score estimates.
6 Leverage Score Approximation via Undersampling
The paper shows that undersampling can improve leverage-score estimates even when uniform sampling is not a full spectral approximation. This supports iterative approximation schemes, including a high-probability uniform-sampling result that uses O(d log d) sampled rows.
- Theorem 3: Theorem 3 strengthens iterative spectral approximation by improving runtime bounds, covering alternative sampling schemes, and explaining why undersampling can produce leverage-score estimates with low total sum.Its intuition is that uniform sampling captures a large low-coherence portion, while only a few rows require loose upper bounds.
- Uniform sampling: Uniform sampling is the special case u = 1, where every leverage score is bounded above by 1.This reframes uniform sampling as undersampling under the weakest available leverage-score upper bounds.
- Uniform sampling: The high-probability guarantee initially costs a factor of log d in the sampling rate, but the paper removes that factor for uniform sampling.Theorem 3’s bound is high probability, whereas Theorem 1’s corresponding bound is in expectation.
- Theorem 3: Theorem 3 gives high-probability leverage-score approximation from undersampling according to any vector of leverage-score upper bounds.The resulting sample S′ has O(α ∥u∥1 log d) nonzeros.
- Iterative improvement: Iterative undersampling repeatedly reduces the sum of leverage-score estimates, halving it at each iteration until it reaches O(d).Starting from estimates with sum s1, the process obtains O(d log d) samples and produces new estimates with sum 3d/2 before repeating.
- Iterative improvement: The method maintains a sample of O(d log d) rows while iteratively improving it.This provides a compact intermediate representation for subsequent approximation steps.
- Improved uniform-sampling bound: Theorem 4 shows that uniform independent sampling at rate m/n, followed by resampling using estimated leverage scores, returns a 1+ε spectral approximation with high probability.The estimates are computed from the smaller sampled matrix without reweighting.
- Improved uniform-sampling bound: Choosing m = O(d log d) yields a spectral approximation of size n/2 when O(d log d) < n.This high-probability result matches the stated O(d log d) sampling bound.
7 Applications to Row Sampling Algorithms
The paper develops two iterative row-sampling algorithms that use approximate leverage scores while preserving row structure and sparsity. Both produce O(d log d)-row spectral approximations, with input-sparsity-time variants and stated runtime guarantees.
- Algorithms: The algorithms yield spectral approximations with O(d log d) rescaled rows while relying solely on row sampling.This preserves matrix sparsity and structure throughout matrix operations.
- Repeated Halving: Repeated Halving recursively samples half the rows, approximates the resulting sample, and uses generalized leverage scores to refine the approximation.The recursion reduces the matrix size before leverage-score estimation.
- Refinement Sampling: Refinement Sampling starts with leverage-score upper bounds equal to 1 and repeatedly undersamples according to them to improve the estimates.The procedure uses generalized leverage-score estimates before its final row sample.
- Repeated Halving: Within log(n) rounds, Repeated Halving reduces the estimated leverage-score sum to O(d), enabling an O(d log d)-row spectral approximation.Each iteration cuts the estimated leverage-score sum by a constant fraction.
- Runtime Analysis: The runtime analysis assumes n = O(poly(d)) and treats dω as the cost of the fastest available d×d system solver.Alternative solvers, including iterative methods for sparse rows, can change the runtime trade-offs.
- Leverage-score estimation: Lemma 7 computes constant-factor generalized leverage-score estimates in O(dω log d + nnz(A) log d) time using a smaller Johnson–Lindenstrauss projection.The projection avoids the naive nnz(A)d cost of multiplying every row by (B⊤B)+.
- Runtime Analysis: A final refinement can produce a (1 + ǫ) approximation with O(d log dǫ−2) rows in O(nnz(A) log d + dω log d) time.The constant-factor approximation is used to estimate leverage scores before final sampling.
- Runtime Analysis: Repeated Halving runs in O(nnz(A) log d + dω log(n/d) log d) time, while Refinement Sampling has a corresponding O(nnz(A) log(n/d) log d) bound.Both output O(d log d)-row matrices satisfying ˜A⊤˜A ≈2 A⊤A.
A.1 Spectral Approximation via Leverage Score Sampling
This section establishes spectral approximation from independent row sampling using leverage-score overestimates. The proof combines matrix concentration with bounds on each sampled row’s contribution and controls the resulting sample size.
- Sampling guarantee: Sampling independently with probabilities proportional to leverage-score overestimates yields a spectral approximation to A.The sampling probability is pi = min{1, α·ui/(c log d)} for overestimates ui.
- Proof: The expected sampled matrix preserves A⊤A because each row contribution is scaled by its sampling probability.The proof sets Yi = aia⊤i for each row and applies matrix concentration.
- Proof: For pi < 1, the leverage-score bound controls each sampled positive semidefinite matrix relative to the expectation, enabling concentration.The argument derives the required inequality for all vectors x in the column space.
- Proof: The pi = 1 case is handled separately by decomposing the deterministic contribution into c log dǫ−2 random variables.This replacement preserves the expectation while enabling the concentration argument.
- Guarantee: With high probability, the sampled matrix is a (1−ǫ)-spectral approximation and has at most αc log d∥u∥1 nonzero entries.The row-count bound follows from a standard Chernoff argument.
A.2 Rank 1 Updates
The section analyzes how leverage scores change when one row is downweighted. It uses the Sherman–Morrison formula for the Moore–Penrose pseudoinverse to derive the rank-1 update behavior.
- Proof: The proof relies on the Sherman–Morrison formula for the Moore–Penrose pseudoinverse.This formula provides the algebraic tool for analyzing the modified leverage scores.
- Rank-1 update: Lemma 5 characterizes leverage-score changes after multiplying one row by √(1−γ) while leaving all other rows unchanged.The update is a rank-1 modification of the weighted matrix.
A.3 Lower Semi-continuity of Leverage Scores
This section proves that leverage scores are lower semi-continuous under convergence of nonnegative diagonal row-weight matrices. The argument compares leverage scores under different weights and takes a limit.
- Comparison inequality: Lemma 12 supplies a general inequality relating leverage scores under two different sets of row weights.This comparison inequality is the main ingredient used in the limiting argument.
- Lower semi-continuity: Lemma 6 states that τ(WA) is lower semi-continuous in the diagonal weight matrix W.The result concerns sequences of weights converging to a limiting nonnegative diagonal matrix.
- Proof: The proof applies the comparison inequality to W(k) and takes the lim inf as k approaches infinity.The zero-weight case follows from nonnegativity, while positive limiting weights are handled for sufficiently large k.