Statistical inference for sketching algorithms
Authors:
Open Access
- 1 July 2024
- journal article
- research article
- Published by Oxford University Press (OUP) in Information and Inference: A Journal of the IMA
- Vol. 13 (3)
Abstract
Sketching algorithms use random projections to generate a smaller sketched data set, often for the purposes of modelling. Complete and partial sketch regression estimates can be constructed using information from only the sketched data set or a combination of the full and sketched data sets. Previous work has obtained the distribution of these estimators under repeated sketching, along with the first two moments for both estimators. Using an alternative approach, we derive the distribution of the complete sketch estimator and additionally consider the error term under both repeated sketching and repeated sampling. Importantly, we obtain pivotal quantities which are based solely on the sketched data set—specifically not requiring information from the full data model fit. These pivotal quantities can be used for inference on the full data set regression estimates or the model parameters. For partial sketching, we derive pivotal quantities for a marginal test and an approximate distribution for the partial sketch under repeated sketching or repeated sampling—again avoiding reliance on a full data model fit. We extend these results to include the Hadamard and Clarkson–Woodruff sketches then compare them in a simulation study.Keywords
Funding Information
- Natural Sciences and Engineering Research Council of Canada (RGPIN-2018-04444, RGPIN-2020-04646)
This publication has 9 references indexed in Scilit:
- Generalized linear models for massive data via doubly-sketchingStatistics and Computing, 2023
- Statistical properties of sketching algorithmsBiometrika, 2020
- Matrix Differential Calculus with Applications in Statistics and Econometrics2019
- Low-Rank Approximation and Regression in Input Sparsity TimeJournal of the ACM, 2017
- Newton Sketch: A Near Linear-Time Optimization Algorithm with Linear-Quadratic ConvergenceSIAM Journal on Optimization, 2017
- The Fast Johnson–Lindenstrauss Transform and Approximate Nearest NeighborsSIAM Journal on Computing, 2009
- A test for the weights of the global minimum variance portfolio in an elliptical modelMetrika, 2007
- On the matrix-variate generalized hyperbolic distribution and its Bayesian applicationsStatistics, 2004
- Bessel Functions of Matrix ArgumentAnnals of Mathematics, 1955