PaperlayerView exact revision on arXiv

Source-linked AI summary

Sketching as a Tool for Numerical Linear Algebra

David P. Woodruff

arXiv:1411.4357v3cs.DS

TL;DR

Numerical linear algebra problems become difficult at large scale because direct regression and related computations can be expensive or lack simple solutions. The survey synthesizes linear-sketching methods that compress matrices before computation, covering regression, low-rank approximation, and graph sparsification. It reports faster least-squares algorithms, including input-sparsity running time, while also identifying limitations such as sensitivity to conditioning and failures for adaptive queries.

  • Problem

    Large-scale numerical linear algebra requires methods that avoid expensive computation on the original matrix, while robust regression also lacks a general closed-form solution.

  • Method

    The survey studies linear sketching, which multiplies a matrix by a usually random matrix to create a much smaller matrix on which computation is performed.

  • Results

    The survey reports advances across least squares, robust regression, low-rank approximation, and graph sparsification, including optimal input-sparsity algorithms for approximate least squares.

  • Takeaways & Limitations

    Sketching provides a framework for accelerating several numerical linear algebra tasks by reducing computation to smaller representations.

  • Takeaways & Limitations

    Sketching methods remain limited by problem-specific constraints, including dependence on the unknown condition number and strong impossibility results for adaptively chosen query vectors.

Abstract

from arXiv · show

This survey highlights the recent advances in algorithms for numerical linear algebra that have come from the technique of linear sketching, whereby given a matrix, one first compresses it to a much smaller matrix by multiplying it by a (usually) random matrix with certain properties. Much of the expensive computation can then be performed on the smaller matrix, thereby accelerating the solution for the original problem. In this survey we consider least squares as well as robust regression problems, low rank approximation, and graph sparsification. We also discuss a number of variants of these problems. Finally, we discuss the limitations of sketching methods.

1 Introduction

Linear sketching accelerates numerical linear algebra by replacing a large regression problem with a smaller randomized one, trading exactness for controlled approximation. The survey traces this idea from least squares to robust regression and broader applications, while addressing the cost of sketch construction.

  • Motivation: Least absolute deviation regression is less sensitive to outliers than least squares because it uses absolute residuals instead of squared residuals.Unlike least squares, it generally lacks a closed-form solution, though it can be solved to machine precision through linear programming.
  • Motivation: Massive least squares and least absolute deviation problems can be polynomial-time yet impractical because their costs grow with the number of observations.Naive normal-equation solving takes at least n·d^2 time, while generic linear-programming approaches for ℓ1-regression take at least cubic polynomial time in n.
  • Linear sketching: Sketching compresses A and b with a random r × n matrix S, then solves the smaller regression problem min_x ∥(SA)x − (Sb)∥_2.The procedure samples S, computes SA and Sb, and returns the exact solution to the sketched least squares problem.
  • Linear sketching: For r = Θ(d/ε^2), Gaussian sketches preserve the relevant singular values and yield a (1+ε)-approximation with probability 1 − exp(−d).The guarantee follows from preserving the geometry of the column space used by the regression problem.
  • Algorithmic advances: Dense sketches can make the reduced solve cheap but leave sketch formation as a bottleneck, requiring Θ(nrd) time for computing SA.Structured fast Johnson–Lindenstrauss transforms reduce this cost, and later input-sparsity algorithms achieve O(nnz(A)) + poly(d/ε) time.
  • Scope: The survey extends sketching advances to robust ℓ1-regression, low-rank approximation, graph sparsification, and variants of these problems.It also discusses reducing ε-dependence to polylogarithmic factors, including O(nnz(A) log(1/ε)) + poly(d) for least squares.

2 Subspace Embeddings and Least Squares Regression

Subspace embeddings preserve the geometry of a matrix’s column space after sketching, enabling faster least-squares regression and related algorithms. The survey develops Gaussian, fast, sparse, and leverage-score constructions, along with their dimensionality, runtime, and probability guarantees.

  • Oblivious embeddings: A Gaussian sketch with k = Θ((d + log(1/δ))ε−2) rows is a (1 ± ε) ℓ2-subspace embedding with probability 1−δ.The guarantee holds simultaneously for all x ∈ R^d.
  • Fast transforms: Johnson–Lindenstrauss transforms can be applied to a vector in O(nnz(x) · ε−1 log(f/δ)) time, while fast variants are significantly faster in many numerical linear algebra settings.The fast transform was used for relative-error regression and low-rank approximation.
  • Sparse embeddings: An oblivious embedding can be computed in O(nd log(d(log n)/ε)) time, which is optimal in the matrix dimensions up to a logarithmic factor.Sparse embeddings avoid the corresponding dense-application cost and can compute S·A in input-sparsity time.
  • Sparse embeddings: Sparse embeddings achieve O(nnz(A)) sketching time with polynomially many rows, and later constructions retain this time with r = O(d2/(δε2)) rows and failure probability δ.The stated guarantees include probability .99 for one construction and probability 1−δ for another.
  • Leverage-score sampling: Leverage-score sampling provides a non-oblivious embedding and can produce a representative subset of rows, while leverage-score distributions can be approximated in O(nnz(A) log n) + poly(k) time.The sampling-based construction is also described as a coreset.
  • Regression applications: Subspace embeddings yield least-squares regression in O(nnz(A)) + poly(d/ε) time with probability .99.The survey states a direct relationship between the time needed to compute an embedding and the time needed to approximately solve ℓ2 regression.

3 Least Absolute Deviation Regression

Least absolute deviation (ℓ1) regression is more robust to outliers than least squares but lacks a general closed-form solution. The survey develops sampling and sketching methods that reduce the problem while preserving ℓ1 geometry and yield polynomial-time approximate algorithms, including input-sparsity-time guarantees.

  • Unlike least squares, ℓ1-regression is not rotation-invariant, is not everywhere differentiable, and generally has no closed-form solution.
  • ℓ1-regression is less sensitive to outliers and is the maximum likelihood estimator for i.i.d. zero-median Laplacian noise.
  • Sampling-based algorithms: Sampling augments A with b, independently samples and rescales rows, and can reduce the regression solve to a smaller linear program.
  • Sampling-based algorithms: With probability at least 1 −2^-d, the sampling algorithm preserves ℓ1 norms for all x within 1 ± ε using an expected at most r = ε^-2poly(d)/ζ nonzero rows.
  • Subspace embeddings: An ℓ1-subspace embedding followed by QR factorization produces a well-conditioned basis, enabling faster sampling computations.
  • Cauchy sketches: An r = O(d log d)-row Cauchy sketch gives a constant-probability ℓ1-subspace embedding and an O(nd2 + nd log(dε^-1 log n)) + poly(d/ε) regression algorithm.
  • Input-sparsity-time sketches: CountSketch combined with reciprocal-exponential diagonal scaling yields an O(nnz(A) log n) + poly(d/ε) algorithm for (1 + ε)-approximate ℓ1-regression.
  • Hyperplane fitting: The same sketching framework gives an O(nnz(A) log n) + poly(d/ε) algorithm for ℓ1-hyperplane approximation with constant probability.

4 Low Rank Approximation

The survey develops sketching-based low-rank approximation methods with Frobenius- and spectral-norm guarantees, including CUR decompositions and distributed variants. These methods reduce computation to input-sparsity-scale time plus polynomial dependence on k/ε, while exposing rank, representation, and determinism trade-offs.

  • 4 Low Rank Approximation: Sketching yields low-rank approximations whose error is compared with the best rank-k approximation of A.The target approximation has rank k and is evaluated under a chosen matrix norm.
  • 4.2 CUR decomposition: CUR decompositions obtain near-optimal low-rank error using actual subsets of columns and rows, with adaptive sampling refining an initial constant-factor approximation.The procedure can find columns in O(nnz(A) log n) + (m + n)poly(k/ε) time, and related row-and-column procedures have the same near-input-sparsity form.
  • 4.1 Frobenius norm error: A subspace embedding lets the best rank-k approximation within a sketched row space achieve a (1 + ε) Frobenius-norm approximation.The construction uses the best rank-k approximation to a projected matrix and lifts it back through the prescribed subspace.
  • 4.1 Frobenius norm error: O(nnz(A)) + (n + d)poly(k/ε) time suffices to compute low-rank factors without materializing a potentially dense n × d approximation.The dominant costs are sketching products such as AR and SA; the output is naturally represented in factored form.
  • 4.2.3 CUR wrapup: Deterministic CUR achieves O(k/ε) columns and rows with a rank-k middle matrix, but its n × n running time is n^4 · poly(k/ε).The deterministic construction derandomizes sampling through discretization and pairwise-independent samples.
  • 4.3 Spectral norm error: Spectral-norm approximation can be achieved with a true rank-k projection satisfying ∥A − ZZT A∥2 ≤ (1 + ε)∥A − Ak∥2.The SubspacePowerMethod attains this guarantee in O(nnz(A)k log(mn)/ε) time, while distributed Frobenius approximation uses O(sdk/ε + sk2/ε4) communicated real numbers.

5 Graph Sparsification

This section develops sketching-based spectral sparsification for graphs, using leverage-score sampling and recursive approximations to compress graph Laplacians while preserving spectral information. The linear-sketch formulation additionally supports streaming updates, including edge deletions.

  • Problem: Spectral sparsification seeks a weighted subgraph H whose Laplacian approximates the original graph Laplacian for all vectors in the relevant space.The approximation is expressed through positive-semidefinite inequalities between the two Laplacians.
  • Leverage-score sampling: Leverage-score sampling obtains a sparsifier by sampling and reweighting O(nε−2 log n) edges with high probability.The sampling guarantee applies simultaneously across the required rows or edges.
  • Linear sketches: The linear-sketch approach stores S·B for a random oblivious map and constructs the sparsifier using only this compressed representation.Because the sketch is linear, it can be updated when graph edges are inserted or deleted.
  • Recursive sparsification: Recursive sparsification repeatedly approximates intermediate positive-semidefinite matrices, with errors that do not compound across levels.At the final level, sampling according to approximate leverage scores yields a (1 + ε)-approximate spectral sparsifier.
  • Streaming construction: A streaming construction samples edges at multiple rates and maintains independent sketches to traverse the leverage-score sampling hierarchy.This process uses O(log n) independent repetitions and ultimately produces a (1 + ε)-approximate sparsifier.

6 Sketching Lower Bounds for Linear Algebra

The survey reviews limitations of sketching methods, including lower bounds on sketch dimension and failures of adaptive reuse. These results delimit when compressed representations can support accurate numerical linear algebra.

  • Scope: The limitations section studies Schatten-norm approximation, sketching lower bounds, subspace-embedding dimension, and adaptive-query failures.The survey treats both algorithmic trade-offs and impossibility results.
  • Lower bounds: The section also examines lower bounds showing that some numerical linear algebra tasks require large sketches or multiple passes over the data.These boundaries are presented alongside positive sketching results.
  • Adaptive querying: Adaptive queries to a sketch can prevent correctness even for basic properties such as estimating an input vector’s Euclidean norm.Algorithms using sketches should avoid adaptive queries or establish correctness under them.

6.1 Schatten norms

This section introduces Schatten norms and gives a randomized multi-pass method for estimating them. The method achieves input-sparsity running time but trades single-pass linear sketching for repeated data access.

  • Definitions: The Schatten p-norm is defined from the singular values of a rank-ρ matrix, with the Schatten-∞ norm equal to its largest singular value.The Schatten-2 norm is the Frobenius norm, while the Schatten-∞ norm is the operator norm.
  • Definitions: Schatten norms are rotationally invariant, so multiplying a matrix on either side by orthonormal matrices preserves the norm.This follows because such transformations preserve the matrix’s singular values.
  • Motivation: Estimating an approximation error in a Schatten norm can be difficult when direct computation would require an SVD, especially for p not in {2, ∞}.The difficulty is particularly relevant when fast time, small space, or few passes are required.
  • Algorithm: O(p · nnz(A)/ε−2) time and ⌈p/2⌉ passes yield a (1 + ε)-approximation to ∥A∥p with probability at least 9/10.The algorithm uses repeated Gaussian-vector matrix products across multiple passes.
  • Trade-off: The method is efficient in running time but is not a linear sketch because it requires multiple passes over the data.The section presents this as a trade-off motivating later lower-bound analysis for single oblivious sketches.

6.2 Sketching the operator norm

The section asks whether the operator norm can be recovered efficiently from a linear sketch. It shows a sharp quadratic lower bound for general square matrices, contrasting with efficient sketching of the Frobenius norm and subspace-embedded singular values.

  • Linear-sketch model: A linear sketch treats an n×d matrix as an nd-dimensional vector and applies a random linear operator L to produce a k-dimensional representation.This general formulation includes, but is broader than, sketches formed by left and right matrix multiplication.
  • Problem: The operator norm is a central target because, unlike the Frobenius norm, its efficient sketchability is not immediate.The section compares efficient Frobenius-norm sketches with lower bounds for operator-norm sketches.
  • Lower bound: Ω(min(n, d)^2) sketch dimensions are necessary for a fixed constant-factor approximation in the stated lower-bound setting.The bound is described as tight up to a constant, and the square-matrix case gives Ω(n^2).
  • Positive result: A (1 ± ε) ℓ2-subspace embedding preserves every singular value of A within the same multiplicative factor after sketching.The result follows from the min-max principle applied to subspaces in the range of A.
  • Lower bound: For square n×n matrices, any linear sketch that estimates the operator norm within a constant factor C with 1 ≤ C < 2 must have k = Ω(n^2).The proof distinguishes Gaussian matrix distributions whose operator norms differ by a constant factor while their sketches remain difficult to distinguish.

6.3 Streaming lower bounds

This section defines the turnstile streaming model for linear algebra, where an initially zero matrix receives additive coordinate updates with bounded integer entries.

  • Lower-bound framework: The section uses communication complexity to prove bit-space lower bounds for linear algebra problems in streaming computation.The stated results follow work by Clarkson and the author.
  • Streaming model: The turnstile model initializes A ∈ R^n×d to zero and updates coordinates through additive tuples (i, j, δ).At every point, entries are integers bounded by M ≤ poly(nd).

6.4 Communication complexity

This section introduces one-way communication complexity and reduces augmented indexing to streaming matrix problems, yielding space lower bounds for matrix products, regression, and low-rank approximation.

  • Communication complexity: In one-way randomized communication, Alice sends one message to Bob, who must compute f with error at most δ.The communication cost is the maximum message length over inputs and random coins.
  • Communication problems: In augmented indexing, Alice holds x ∈ {0,1}^n while Bob receives i and the suffix x_i+1, …, x_n, and must output x_i.Under the uniform input distribution, its randomized one-way complexity is Ω(n).
  • Matrix product: The matrix product reduction simulates a streaming algorithm across Alice’s and Bob’s inputs, allowing them to solve augmented indexing from its output.The reduction succeeds with probability at least 4/5 − 25/198 > 2/3.
  • Matrix product: Ω(cε^-2 log(nc)) bits are necessary for one-pass randomized Matrix Product algorithms under the stated dimension and precision conditions.The bound applies to algorithms succeeding with probability at least 4/5.
  • Regression: Ω(d^2ε^-1 log(nd)) bits are required for one-pass ℓ2 regression with success probability at least 7/9 under the stated condition on n and d.The theorem assumes sufficiently large d.
  • Low-rank approximation: For rank-k approximation, row-order streams require Ω(nk/ε) space, whereas column-order streams require Ω(dk/ε) space under their respective dimension conditions.Both bounds assume randomized one-pass success probability at least 5/6.

6.5 Subspace embeddings

This section studies the minimum dimension of oblivious ℓ2-subspace embeddings, showing that Gaussian sketches achieve O(d/ε^2) rows and that this dependence is optimal up to constants.

  • Dimension question: The central question is how few rows an oblivious sketch can use while preserving all norms in the column space of every fixed matrix A.The distribution over sketches must succeed with constant probability for each fixed A.
  • Upper bound: Gaussian sketches with r = O(d/ε^2) rows provide a (1 ± ε) ℓ2-subspace embedding with probability 1 − exp(−d).This preserves ∥SAx∥_2 within a (1 ± ε) factor of ∥Ax∥_2 simultaneously for all x.
  • Lower bound: The Gaussian row count is optimal up to constants even when only constant success probability is required.The lower bound applies to any distribution achieving the subspace-embedding guarantee.
  • Application-specific bounds: Specific applications can improve the dependence on 1/ε because they may require only constant-ε subspace preservation plus additional properties of the sketch.The section identifies ℓ2 regression as an example with linear dependence on 1/ε.

6.6 Adaptive algorithms

This section warns that linear sketches supporting fixed queries need not remain accurate under adaptive reuse: carefully chosen queries can expose their low-dimensional structure.

  • Adaptive reuse: Sketch-reuse guarantees for fixed vectors do not directly extend when each query may depend on earlier sketch outputs.The section frames adaptive reuse as a distinct problem.
  • ℓ2-sketches: An ℓ2-sketch is a pair (S, f) that approximately recovers ∥x∥_2 from the sketch output f(Sx) for fixed x.An ℓ2-subspace embedding provides this property for suitable ε and δ.
  • Johnson–Lindenstrauss failure: For a Johnson–Lindenstrauss transform with k < n rows, an adaptive algorithm can find a query on which norm estimation fails with probability 1.The procedure uses r queries, with the first r − 1 non-adaptive, and runs in O(k^3) time.
  • Attack mechanism: The attack learns information about S through unit-vector and pairwise-sum queries, reconstructing a low-rank Gram submatrix before selecting a kernel vector.The resulting vector v satisfies Sv = 0, defeating relative norm approximation.
  • General impossibility: More generally, an efficient adaptive algorithm can defeat any ℓ2 sketch using at most r = n − O(log(nB)) rows with constant probability.It uses at most poly(rB) queries and r rounds of adaptivity.
  • General impossibility: The intuition is that adaptive queries learn most of the sketch’s row space, enabling queries near its kernel where norm estimation becomes unreliable.The proof uses a game in which Bob observes only Sx and progressively learns the row space.

7 Open Problems

The survey closes with open questions spanning low-rank approximation, distributed computation, and Schatten-norm sketching. These questions ask whether existing guarantees and communication bounds can be strengthened, and what sketch size is optimal.

  • Scope: The survey covers several sketching applications but explicitly omits additional material and directs readers to other surveys for topics not treated.This closing scope statement qualifies the survey’s coverage rather than identifying a technical open problem.
  • Spectral Low Rank Approximation: Can spectral-norm low-rank approximation achieve O(nnz(A)) + n · poly(k/ε) time with the stronger spectral-error guarantee?The survey contrasts this target with efficient Frobenius-norm algorithms and existing spectral-norm projection results.
  • Robust Low Rank Approximation: Can robust low-rank approximation be solved in polynomial time for entry-wise 1-norm error, or is the problem NP-hard?Existing work gives polynomial-time algorithms for fixed k and ε under the weaker V-norm error measure.
  • Distributed Low Rank Approximation: Can distributed low-rank approximation require an Ω(sdk/ε) communication lower bound matching the leading term of the O(sdk/ε) + poly(sk/ε) protocol?The problem uses s players holding local matrices and asks them to output the same rank-k projection matrix.
  • Sketching the Schatten-1 Norm: What is the optimal sketching dimension for approximating the Schatten-1 norm within a constant factor?For Schatten-1 norm, known lower bounds range from Ω(n^1/2) to Ω(n^(1−γ)) for particular matrix-sketch forms, while no nontrivial better-than-O(n^2) upper bound is known.
Loading 1411.4357v3…