# Accumulation of Sub-Sampling Matrices with Applications to Statistical Computation

arXiv: https://arxiv.org/abs/2103.04031 · HTML: https://mlsanity.com/paper/2103.04031/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 55 references that are in the map.
- First posted on arXiv 6 Mar 2021.

## Builds on (most cited first, 9 of 9)

- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [On the Equivalence between Kernel Quadrature Rules and Random Feature Expansions](https://mlsanity.com/paper/1502.06800/) (2015)
- [Sub-sampled Cubic Regularization for Non-convex Optimization](https://mlsanity.com/paper/1705.05933/) (2017)
- [On Fast Leverage Score Sampling and Optimal Learning](https://mlsanity.com/paper/1810.13258/) (2018)
- [Optimal approximate matrix product in terms of stable rank](https://mlsanity.com/paper/1507.02268/) (2015)
- [Randomized sketches for kernels: Fast and optimal non-parametric regression](https://mlsanity.com/paper/1501.06195/) (2015)
- [Sparse sketches with small inversion bias](https://mlsanity.com/paper/2011.10695/) (2020)
- [Explaining Aggregates for Exploratory Analytics](https://mlsanity.com/paper/1812.11346/) (2018)

## Built on by (most cited first, 10 of 10)

- [Skyformer: Remodel Self-Attention with Gaussian Kernel and Nystr"om Method](https://mlsanity.com/paper/2111.00035/) (2021)
- [Efficient SGD Neural Network Training via Sublinear Activated Neuron Identification](https://mlsanity.com/paper/2307.06565/) (2023)
- [Is Solving Graph Neural Tangent Kernel Equivalent to Training Graph Neural Network?](https://mlsanity.com/paper/2309.07452/) (2023)
- [Sketching as a Tool for Understanding and Accelerating Self-attention for Long Sequences](https://mlsanity.com/paper/2112.05359/) (2021)
- [Calibrate and Debias Layer-wise Sampling for Graph Convolutional Networks](https://mlsanity.com/paper/2206.00583/) (2022)
- [Fast Kernel Methods for Generic Lipschitz Losses via p-Sparsified Sketches](https://mlsanity.com/paper/2206.03827/) (2022)
- [Sketch In, Sketch Out: Accelerating both Learning and Inference for Structured Prediction with Kernels](https://mlsanity.com/paper/2302.10128/) (2023)
- [Kernel Learning for Mean-Variance Trading Strategies](https://mlsanity.com/paper/2507.10701/) (2025)
- [Online Adaptive Mahalanobis Distance Estimation](https://mlsanity.com/paper/2309.01030/) (2023)
- [Fast Heavy Inner Product Identification Between Weights and Inputs in Neural Network Training](https://mlsanity.com/paper/2311.11429/) (2023)

## Abstract (arXiv)

With appropriately chosen sampling probabilities, sampling-based random projection can be used to implement large-scale statistical methods, substantially reducing computational cost while maintaining low statistical error. However, computing optimal sampling probabilities is often itself expensive, and in practice one typically resorts to suboptimal schemes. This generally leads to increased time and space costs, as more subsamples are required and the resulting projection matrices become larger, thereby making the inference procedure more computationally demanding. In this paper, we extend the framework of sampling-based random projection and propose a new projection method, accumulative sub-sampling. By carefully accumulating multiple such projections, accumulative sub-sampling improves statistical efficiency while controlling the effective matrix size throughout the statistical computation. On the theoretical side, we quantify how the quality of the subsampling scheme affects the error in approximating matrix products and positive semidefinite matrices, and show how the proposed accumulation strategy mitigates this effect. Moreover, we apply our method to statistical models involving intensive matrix operations, such as eigendecomposition in spectral clustering and matrix inversion in kernel ridge regression, and demonstrate that reducing the effective matrix size leads to substantial computational savings. Numerical experiments across a range of problems further show that our approach consistently improves computational efficiency compared to existing random projection baselines under suboptimal sampling schemes.