Sparse Sketching Matrices - Randomized Numerical Linear Algebra with Examples

Sparse sketching matrices aim to reduce the generate and apply times by making the sketching matrix sparse.

CountSketch¶

The classical example of a sparse sketching matrix is the CountSketch matrix Clarkson & Woodruff, 2013.

A CountSketch matrix can be applied to $\vec{A}$ in $O(\nnz(\vec{A}))$ operations. However, it does not provide a good subspace embedding.

SparseStack Sketch¶

The poor scaling of embedding dimension in CountSketch can be remedied by increasing the per-column sparsity. There are a number of ways to do this, but one of the most promising is to simply stack a bunch of independent CountSketch matrices on top of one another.

Definition 2.4

We say a matrix $\vec{S}\in\R^{k\times n}$ is a SparseStack matrix* if it has the distribution

\vec{S} = \begin{bmatrix} \rho_{1,1}\vec{e}_{s_{1,1}} & \rho_{1,2}\vec{e}_{s_{1,2}} & \cdots & \rho_{1,n}\vec{e}_{s_{1,n}} \\ \rho_{2,1}\vec{e}_{s_{2,1}} & \rho_{2,2}\vec{e}_{s_{2,2}} & \cdots & \rho_{2,n}\vec{e}_{s_{2,n}} \\ \vdots & \vdots & \ddots & \vdots \\ \rho_{\zeta,1}\vec{e}_{s_{\zeta,1}} & \rho_{\zeta,2}\vec{e}_{s_{\zeta,2}} & \cdots & \rho_{\zeta,n}\vec{e}_{s_{\zeta,n}} \end{bmatrix} ,\qquad \begin{aligned} &\rho_{i,j}\sim \Call{Rademacher}\text{ iid}\\ &s_{i,j} \sim \Call{Unif}(\{1,\ldots,k/\zeta\})\text{ iid}. \end{aligned}

This is equivalent to generating $\zeta$ CountSketch matrices of hight $k/\zeta$ , and stacking them on top of one another. A SparseStack matrix can be applied to $\vec{A}$ in $O(\zeta\nnz(\vec{A}))$ operations.

SparseStack matrices are known to give a subspace embedding with the optimal embedding dimension, even when $\zeta$ is extremely small. The following is due to Chenakkod et al., 2025.

Implementation¶

It’s relatively easy to efficiently generate SparseStack matrices in a high-level langauge like Python.

def sparse_stack_sketch(n,k,zeta,rng):

    k_rem = k%zeta
    k_loc = k//zeta

    C = np.zeros((n,zeta),dtype=int)
    C[:,:k_rem] = np.random.randint(0,k_loc+1,size=(n,k_rem))
    C[:,k_rem:] = np.random.randint(0,k_loc,size=(n,zeta-k_rem))
    offsets = np.cumsum([0]+[k_loc+1]*k_rem + [k_loc]* (zeta-k_rem-1))
    C += offsets

    indices = C.flatten()
    values = np.sqrt(1/zeta)*(2*np.random.randint(2,size=n*zeta)-1)
    indptr = np.arange(0,n+1)*zeta
    S = sp.sparse.csc_matrix ((values,indices,indptr),shape=(k,n))

    return S

Comparison with sparse sign sketches¶

A perhaps more common sparse sketching distribution, typically called SparseSign matrix, does not separate the rows of the sketch into blocks. Instead, each column has exactly $\zeta$ random signs in uniformly random positions. We make the following observations:

The current best theoretical bounds for the embedding dimension and sparsity of SparseStack sketches is better than the corresponding bounds for SparseSign sketches.
It is somewhat more tedious SparseSign sketches than to generate than SparseStack sketches, but it can be done efficiently with a bit of care Chen et al., 2025.
The embedding dimension of SparseStack matrices can easily be adjusted by stacking on more CountSketch matrices. This may be useful in practice, where an algorithm might need to adjust the embedding dimension on the fly.

Thus, we recommend SparseStack sketches as the default sparse sketch.

Footnotes¶

That is, $k = O(d \log(d)^{o(1)})$ and $\zeta = O(\log(d)^{1+o(1)})$ .
↩

References¶

Clarkson, K. L., & Woodruff, D. P. (2013). Low rank approximation and regression in input sparsity time. Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, 81–90. 10.1145/2488608.2488620
Chenakkod, S., Dereziński, M., & Dong, X. (2025). Optimal Subspace Embeddings: Resolving Nelson-Nguyen Conjecture Up to Sub-Polylogarithmic Factors. https://arxiv.org/abs/2508.14234
Chen, T., Niroula, P., Ray, A., Subrahmanya, P., Pistoia, M., & Kumar, N. (2025). GPU-Parallelizable Randomized Sketch-and-Precondition for Linear Regression using Sparse Sign Sketches. https://arxiv.org/abs/2506.03070

Randomized Numerical Linear Algebra with Examples

Gaussian Sketching Matrices

Randomized Numerical Linear Algebra with Examples

Trigonometric Sketching Matrices