Cargando…
Statistical properties of sketching algorithms
Sketching is a probabilistic data compression technique that has been largely developed by the computer science community. Numerical operations on big datasets can be intolerably slow; sketching algorithms address this issue by generating a smaller surrogate dataset. Typically, inference proceeds on...
Autores principales: | , , |
---|---|
Formato: | Online Artículo Texto |
Lenguaje: | English |
Publicado: |
2021
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7612324/ https://www.ncbi.nlm.nih.gov/pubmed/35125502 http://dx.doi.org/10.1093/biomet/asaa062 |
_version_ | 1783605356690145280 |
---|---|
author | Ahfock, D. C. Astle, W. J. Richardson, S. |
author_facet | Ahfock, D. C. Astle, W. J. Richardson, S. |
author_sort | Ahfock, D. C. |
collection | PubMed |
description | Sketching is a probabilistic data compression technique that has been largely developed by the computer science community. Numerical operations on big datasets can be intolerably slow; sketching algorithms address this issue by generating a smaller surrogate dataset. Typically, inference proceeds on the compressed dataset. Sketching algorithms generally use random projections to compress the original dataset, and this stochastic generation process makes them amenable to statistical analysis. We argue that the sketched data can be modelled as a random sample, thus placing this family of data compression methods firmly within an inferential framework. In particular, we focus on the Gaussian, Hadamard and Clarkson–Woodruff sketches and their use in single-pass sketching algorithms for linear regression with huge samples. We explore the statistical properties of sketched regression algorithms and derive new distributional results for a large class of sketching estimators. A key result is a conditional central limit theorem for data-oblivious sketches. An important finding is that the best choice of sketching algorithm in terms of mean squared error is related to the signal-to-noise ratio in the source dataset. Finally, we demonstrate the theory and the limits of its applicability on two datasets. |
format | Online Article Text |
id | pubmed-7612324 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2021 |
record_format | MEDLINE/PubMed |
spelling | pubmed-76123242022-02-04 Statistical properties of sketching algorithms Ahfock, D. C. Astle, W. J. Richardson, S. Biometrika Article Sketching is a probabilistic data compression technique that has been largely developed by the computer science community. Numerical operations on big datasets can be intolerably slow; sketching algorithms address this issue by generating a smaller surrogate dataset. Typically, inference proceeds on the compressed dataset. Sketching algorithms generally use random projections to compress the original dataset, and this stochastic generation process makes them amenable to statistical analysis. We argue that the sketched data can be modelled as a random sample, thus placing this family of data compression methods firmly within an inferential framework. In particular, we focus on the Gaussian, Hadamard and Clarkson–Woodruff sketches and their use in single-pass sketching algorithms for linear regression with huge samples. We explore the statistical properties of sketched regression algorithms and derive new distributional results for a large class of sketching estimators. A key result is a conditional central limit theorem for data-oblivious sketches. An important finding is that the best choice of sketching algorithm in terms of mean squared error is related to the signal-to-noise ratio in the source dataset. Finally, we demonstrate the theory and the limits of its applicability on two datasets. 2021-06 2020-07-30 /pmc/articles/PMC7612324/ /pubmed/35125502 http://dx.doi.org/10.1093/biomet/asaa062 Text en https://creativecommons.org/licenses/by/4.0/This is an Open Access article distributed under the terms of the Creative CommonsAttribution License (http://creativecommons.org/licenses/by/4.0/ (https://creativecommons.org/licenses/by/4.0/) ), which permits unrestricted reuse, distribution, and reproduction in any medium, provided the original work is properly cited. |
spellingShingle | Article Ahfock, D. C. Astle, W. J. Richardson, S. Statistical properties of sketching algorithms |
title | Statistical properties of sketching algorithms |
title_full | Statistical properties of sketching algorithms |
title_fullStr | Statistical properties of sketching algorithms |
title_full_unstemmed | Statistical properties of sketching algorithms |
title_short | Statistical properties of sketching algorithms |
title_sort | statistical properties of sketching algorithms |
topic | Article |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7612324/ https://www.ncbi.nlm.nih.gov/pubmed/35125502 http://dx.doi.org/10.1093/biomet/asaa062 |
work_keys_str_mv | AT ahfockdc statisticalpropertiesofsketchingalgorithms AT astlewj statisticalpropertiesofsketchingalgorithms AT richardsons statisticalpropertiesofsketchingalgorithms |