Randomized Sketching for Scalable Matrix Computations

19 concepts19 papers1 proposal

In modern data science, the sheer volume of information often outpaces the capabilities of traditional numerical algorithms. When datasets reach terabyte scales or are distributed across vast clusters, standard operations like Singular Value Decomposition (SVD) or Least-Squares regression become computationally prohibitive due to memory constraints and communication bottlenecks.

Randomized sketching offers a solution to this "Big Data" challenge by compressing massive matrices into smaller, manageable "sketches" that preserve the essential geometric and spectral properties of the original data.

The Core Intuition: Linear Projections

The fundamental mechanism of sketching is the application of a random linear transformation. To compress a large matrix $A$, we multiply it by a random sketching matrix $S$. As David P. Woodruff explains in Sketching as a Tool for Numerical Linear Algebra, this process maps high-dimensional data into a lower-dimensional space while ensuring that the solution to a problem on the compressed data remains a close approximation to the original.

Why does this work? The intuition lies in the fact that high-dimensional data often possesses a lower-dimensional "intrinsic" structure. By using random projections—such as Gaussian or Rademacher matrices—we can capture the dominant spectral properties of a matrix without needing to process every entry. Erichson et al. demonstrate in Randomized Matrix Decompositions Using R that these sketches allow standard deterministic algorithms to run at a fraction of the cost with negligible loss in accuracy.

Accelerating Numerical Linear Algebra

Sketching has revolutionized Numerical Linear Algebra (NLA), turning the "old guard" of scientific computing into a high-speed engine for data science (Stoll, A literature survey of matrix methods for data science).

  1. Low-Rank Approximation: Instead of computing a full SVD, we can sketch the matrix to find a subspace that captures most of its variance. Tropp et al. provide a framework in Practical Sketching Algorithms for Low-Rank Matrix Approximation that is numerically stable and preserves structures like positive-semidefiniteness.
  2. Matrix Factorization: For complex tasks like Nonnegative Matrix Factorization (NMF), Qian et al. show that sketching reduces the cost of each iteration by projecting high-dimensional subproblems into lower-dimensional spaces (Fast and Secure Distributed Nonnegative Matrix Factorization).
  3. Thresholding Operators: In computer vision, Oh et al. utilize sketching to speed up Singular Value Thresholding, a key component of nuclear norm minimization, by orders of magnitude (Fast randomized Singular Value Thresholding for Nuclear Norm Minimization).

Sketching for Optimization

Beyond simple decompositions, sketching is a powerful tool for scaling up convex optimization. In Randomized Sketches of Convex Programs with Sharp Guarantees, Pilanci et al. reveal that the required size of a sketch is not determined by the raw dimensions of the data, but by the Gaussian width (a measure of geometric complexity) of the problem's constraints. This allows for efficient solving of Lasso, SVMs, and other constrained problems.

Sketching can even be used to estimate second-order information. Berglund et al. propose Zeroth-Order Randomized Subspace Newton methods, which use sketching and finite differences to approximate the Hessian, making high-dimensional optimization tractable when only function evaluations are available (Zeroth-Order Randomized Subspace Newton Methods).

The Statistical and Algorithmic Trade-off

While sketching is highly effective for optimization, it introduces a subtle trade-off between computational speed and statistical precision. Raskutti et al. point out in Statistical and Algorithmic Perspectives on Randomized Sketching for Ordinary Least-Squares that while a sketch might quickly minimize an optimization objective, it may require more data than the original problem to achieve the same level of predictive accuracy.

To mitigate these issues, researchers have developed hybrid approaches. For example, Clarkson et al. describe a "sketch-and-sample" framework that combines randomized dimensionality reduction with importance sampling to handle outliers and improve robustness in subspace approximation (Input Sparsity and Hardness for Robust Subspace Approximation).

Distributed Systems and Data Streams

In distributed environments, the bottleneck is often the cost of moving data across a network rather than CPU cycles. Yang et al. argue that sketching is essential for distributed linear algebra because it significantly reduces communication requirements (Implementing Randomized Matrix Algorithms in Parallel and Distributed Environments). By computing summarization matrices in a single pass, massive datasets can be integrated into distributed databases via user-defined aggregations (Li et al., Scalable data summarization on big data).

This efficiency extends to real-time monitoring. Thompson et al. demonstrate that sketching allows for sequential change-point detection in high-dimensional data streams, enabling anomaly detection on compressed signals rather than raw, memory-intensive data (Sketching for sequential change-point detection).

Key Foundational Work

Sketching as a Tool for Numerical Linear Algebra (2014) — contributed 1 concept elements to this direction.
Randomized Sketches of Convex Programs with Sharp Guarantees (2014) — contributed 1 concept elements to this direction.
Distributed Column Subset Selection on MapReduce (2013) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_randomized_sketching_5bbc5fce,
  title = {randomized sketching},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/randomized-sketching/rdr_5bbc5fceedf44d0ca3518953fddcb621},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_randomized_sketching_5bbc5fce_v1,
  title = {randomized sketching},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/randomized-sketching/rdr_5bbc5fceedf44d0ca3518953fddcb621/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake