Randomized Linear Algebra in Input-Sparsity Time

41 concepts31 papers1 proposal

In modern data science, we frequently encounter matrices that are massive but mostly empty. Whether dealing with user-item recommendation logs, high-resolution genomic interaction matrices, or text-term corpora, the vast majority of entries are zero.

To process these datasets, researchers traditionally rely on Randomized Numerical Linear Algebra (RandNLA). As surveyed by David P. Woodruff in Sketching as a Tool for Numerical Linear Algebra, the core idea of RandNLA is to multiply a massive input matrix $A$ by a random projection matrix $S$ to create a much smaller "sketch" that preserves the essential geometric properties of the original data.

However, classical random projections—such as Gaussian or Subsampled Randomized Hadamard Transforms—are dense. Multiplying a sparse matrix $A$ by a dense matrix $S$ destroys the data's inherent sparsity, forcing the algorithm to spend time and memory computing operations on thousands of zero-value entries. This creates a severe computational bottleneck where the runtime scales with the total dimensions of the matrix ($n \times d$) rather than its actual information content.

To solve this, a powerful paradigm has emerged: input-sparsity time algorithms. These methods compute near-optimal matrix approximations and regressions in time proportional only to the number of non-zero entries, denoted as $O(\text{nnz}(A))$.


The Core Mechanism: Sparse Subspace Embeddings

The breakthrough that enabled input-sparsity time computations was the development of sparse embedding matrices. Independently proposed in foundational papers by Kenneth L. Clarkson et al. in Low Rank Approximation and Regression in Input Sparsity Time and Michael W. Mahoney et al. in Low-distortion Subspace Embeddings in Input-sparsity Time and Applications to Robust Linear Regression, this approach replaces dense random projections with a structure inspired by the CountSketch data structure.

Imagine we want to compress an $n \times d$ matrix $A$ down to a smaller $k \times d$ sketch matrix $B$, where $k \ll n$. Instead of using a dense matrix $S$, we construct a sparse embedding matrix $S \in \mathbb{R}^{k \times n}$ using the following rules:

  1. For each column $j$ of $S$ (which corresponds to a row of $A$), we pick exactly one row index $h(j) \in \{1, \dots, k\}$ uniformly at random.
  2. We place a random sign $g(j) \in \{-1, +1\}$ at that position, leaving all other entries in the column as zero.
Dense Projection (Slow):
[ x  x  x ]   [ A11  0   A13 ]   Each zero entry is multiplied
[ x  x  x ] * [  0  A22   0  ] = by a dense random weight,
[ x  x  x ]   [ A31  0    0  ]   wasting computation.

Sparse Projection (Input-Sparsity Time):
[ +1  0   0 ]   [ A11  0   A13 ]   Each row of A is directly
[  0  0  -1 ] * [  0  A22   0  ] = hashed and accumulated.
[  0  +1  0 ]   [ A31  0    0  ]   Zeros are skipped entirely.

When we compute the sketch $B = S \cdot A$, the multiplication behaves like a stream of row routing operations. For every non-zero entry $A_{ji}$ in the input matrix, we simply look up its row's assigned bucket $h(j)$ and add or subtract $A_{ji}$ from the corresponding slot in the sketch matrix:

$$B_{h(j), i} \leftarrow B_{h(j), i} + g(j) \cdot A_{ji}$$

Because the algorithm only touches the non-zero entries of $A$, the time required to construct the sketch is strictly bounded by $O(\text{nnz}(A))$.

Why Does This Preserve Geometry?

It is intuitive that this hashing process is fast, but why does it preserve the underlying linear structure of the data?

When rows of $A$ are mapped to the same bucket in the sketch, their vectors collide and mix. However, because each row is multiplied by an independent random sign $g(j)$, the cross-terms between different rows cancel out in expectation. For any two distinct rows $j$ and $j'$, the expected value of their product in the sketch is zero:

$$\mathbb{E}[g(j) \cdot g(j')] = 0$$

By scaling the sketch size $k$ appropriately, the variance of these collisions remains tightly bounded. This ensures that $S$ acts as a subspace embedding: it preserves the lengths of all vectors within a given subspace with high probability, meaning $\|SAx\|_2 \approx \|Ax\|_2$ for all $x$.


Speeding Up Regression and Low-Rank Approximations

Once a sparse subspace embedding is computed, it can be used to accelerate fundamental linear algebra tasks.

Least-Squares and Robust Regression

In a standard least-squares regression problem, we want to find a vector $x$ that minimizes $\|Ax - b\|_2$. Instead of solving this directly on the massive matrix $A$, we can apply our sparse embedding matrix $S$ to both sides, reducing the problem to minimizing $\|SAx - Sb\|_2$. Because $S$ preserves the geometry of the column space of $A$, the solution to this sketched problem is a highly accurate approximation of the original problem, solvable in a fraction of the time.

The authors have extended this core intuition to more complex regression variants. For instance, Huaian Diao et al. in Total Least Squares Regression in Input Sparsity Time demonstrated that sketching and leverage score sampling can be combined to solve Total Least Squares (TLS) regression—where both the features and targets contain noise—in input-sparsity time.

Low-Rank Approximation

For low-rank approximation (finding a rank-$k$ matrix that closely approximates $A$), input-sparsity sketching provides a rapid way to find a subspace that captures most of the matrix's "energy."

While early sparse embedding methods suffered from a slight loss in accuracy compared to deterministic methods, recent algorithmic variants bridge this gap. For example, Chenhao Wang et al. in An Improved Frequent Directions Algorithm for Low-Rank Approximation via Block Krylov Iteration combined the "Frequent Directions" streaming sketch with Block Krylov Iteration. This hybrid approach achieves the high accuracy of deterministic methods while maintaining the $O(\text{nnz}(A))$ runtime scaling of sparse projections.


Scaling Beyond Standard Matrices

The principles of input-sparsity time algorithms have expanded beyond simple matrix operations into complex database architectures, tensor algebra, and combinatorial optimization.

In-Database Analytics Without Materialization

A major bottleneck in relational databases occurs when training machine learning models on data spread across multiple tables. Standard approaches require performing a JOIN operation to materialize a massive combined table before running regression algorithms. This materialization causes an exponential explosion in data volume.

To circumvent this, Rajesh Jayaram et al. in In-Database Regression in Input Sparsity Time developed algorithms that compute sketches directly from the underlying source tables. By restructuring the sketching operation to distribute over the join structure, they solve linear and ridge regressions in time proportional to the non-zero entries of the input tables, completely avoiding the cost of materializing the massive join output.

This aligns with broader database optimization frameworks, such as the InsideOut algorithm proposed by Mahmoud Abo Khamis et al. in Juggling Functions Inside a Database, which uses variable elimination to prevent the generation of dense intermediate results during complex relational queries.

High-Dimensional Tensors and Optimization

The same mathematical insights apply to high-dimensional spaces where matrices are formed implicitly, such as kernel methods and tensor products. David Woodruff et al. in Leverage Score Sampling for Tensor Product Matrices in Input Sparsity Time showed how to perform implicit leverage score sampling on matrices formed by tensoring multiple vectors together, achieving input-sparsity bounds relative to the unexpanded data.

Furthermore, this paradigm has broken long-standing theoretical barriers in optimization. For example, the work on Discrepancy Minimization in Input-Sparsity Time broke the traditional cubic time barrier ($n^3$) for matrix discrepancy problems by pairing implicit leverage-score sampling with lazy data structures, proving that combinatorial optimization can scale linearly with non-zero entries.

Summary of Downstream Applications

Domain Application Key Mechanism
Clustering Sparse Embedded k-Means Clustering (Weiwei Liu et al.) Uses sparse random projections to achieve a $(1+\epsilon)$ approximation in $O(\text{nnz}(X))$ time.
Matrix Preconditioning Matrix Balancing via Random Osborne (Jason M. Altschuler et al.) Proves near-linear convergence relative to non-zero entries for eigenvalue preconditioning.
Streaming Sketches Near Optimal Frequent Directions (Zengfeng Huang) Optimizes matrix covariance sketches to run in input-sparsity time without losing structural guarantees.

By shifting the computational focus from the static dimensions of a data container ($n \times d$) to the actual volume of information ($\text{nnz}(A)$), input-sparsity time algorithms provide the mathematical foundation required to scale numerical linear algebra to massive, sparse datasets.

Key Foundational Work

Fast Learning from Sparse Data (1999) — contributed 2 concept elements to this direction.
Better size estimation for sparse matrix products (2010) — 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_input_sparsity_time_complexity_cd2f81b0,
  title = {input-sparsity time complexity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/input-sparsity-time-complexity/rdr_cd2f81b028fa4d6c9774c523b6401313},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_input_sparsity_time_complexity_cd2f81b0_v1,
  title = {input-sparsity time complexity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/input-sparsity-time-complexity/rdr_cd2f81b028fa4d6c9774c523b6401313/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake