{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,28]],"date-time":"2026-08-28T09:12:02Z","timestamp":1787908322329,"version":"build-2784847793"},"reference-count":34,"publisher":"Oxford University Press (OUP)","issue":"2","license":[{"start":{"date-parts":[[2020,7,30]],"date-time":"2020-07-30T00:00:00Z","timestamp":1596067200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021,5,15]]},"abstract":"<jats:title>Summary<\/jats:title><jats:p>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\u2013Woodruff 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.<\/jats:p>","DOI":"10.1093\/biomet\/asaa062","type":"journal-article","created":{"date-parts":[[2020,7,22]],"date-time":"2020-07-22T19:21:34Z","timestamp":1595445694000},"page":"283-297","source":"Crossref","is-referenced-by-count":18,"title":["Statistical properties of sketching algorithms"],"prefix":"10.1093","volume":"108","author":[{"given":"D C","family":"Ahfock","sequence":"first","affiliation":[{"name":"MRC Biostatistics Unit, University of Cambridge, Robinson Way, Cambridge CB2 0SR, U.K"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"W J","family":"Astle","sequence":"additional","affiliation":[{"name":"MRC Biostatistics Unit, University of Cambridge, Robinson Way, Cambridge CB2 0SR, U.K"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"S","family":"Richardson","sequence":"additional","affiliation":[{"name":"MRC Biostatistics Unit, University of Cambridge, Robinson Way, Cambridge CB2 0SR, U.K"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2020,7,30]]},"reference":[{"key":"2021051519490459200_B1","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1137\/060673096","article-title":"The fast Johnson Lindenstrauss transform and approximate nearest neighbors","volume":"39","author":"Ailon,","year":"2009","journal-title":"SIAM J. Comp."},{"key":"2021051519490459200_B2","doi-asserted-by":"crossref","first-page":"1415","DOI":"10.1016\/j.cell.2016.10.042","article-title":"The allelic landscape of human blood cell trait variation and links to common complex disease","volume":"167","author":"Astle,","year":"2016","journal-title":"Cell"},{"key":"2021051519490459200_B3","first-page":"2258","article-title":"Subspace embeddings for the polynomial kernel","volume-title":"Proc. 27th Int. Conf. Neural Information Processing Systems (NIPS\u201914)","author":"Avron,","year":"2014"},{"key":"2021051519490459200_B4","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1093\/biomet\/ass068","article-title":"Efficient Gaussian process regression for large datasets","volume":"100","author":"Banerjee,","year":"2013","journal-title":"Biometrika"},{"key":"2021051519490459200_B5","first-page":"01248841","article-title":"A note on replacing uniform subsampling by random projections in MCMC for linear regression of tall datasets","author":"Bardenet,","year":"2015","journal-title":"HAL"},{"key":"2021051519490459200_B6","article-title":"Robust partially-compressed least-squares","author":"Becker,","year":"2015"},{"key":"2021051519490459200_B7","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1038\/s41586-018-0579-z","article-title":"The UK Biobank resource with deep phenotyping and genomic data","volume":"562","author":"Bycroft,","year":"2018","journal-title":"Nature"},{"key":"2021051519490459200_B8","doi-asserted-by":"crossref","first-page":"959","DOI":"10.1111\/rssb.12228","article-title":"Random-projection ensemble classification","volume":"B 79","author":"Cannings,","year":"2017","journal-title":"J. R. Statist. Soc."},{"key":"2021051519490459200_B9","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1145\/2488608.2488620","article-title":"Low rank approximation and regression in input sparsity time","volume-title":"Proc. 45th Annual ACM Sympos. Theory of Computing (STOC\u201913)","author":"Clarkson,","year":"2013"},{"key":"2021051519490459200_B10","article-title":"Sketch techniques for approximate query processing","volume-title":"Foundations and Trends in Databases","author":"Cormode,","year":"2011"},{"key":"2021051519490459200_B11","first-page":"360","article-title":"New subsampling algorithms for fast least squares regression","volume-title":"Proc. 26th Int. Conf. Neural Information Processing Systems (NIPS\u201913)","author":"Dhillon,","year":"2013"},{"key":"2021051519490459200_B12","doi-asserted-by":"crossref","first-page":"793","DOI":"10.1214\/aos\/1176346703","article-title":"Asymptotics of graphical projection pursuit","volume":"12","author":"Diaconis,","year":"1984","journal-title":"Ann. Statist."},{"key":"2021051519490459200_B13","first-page":"3675","article-title":"Asymptotics for sketching in least squares regression","volume-title":"Advances in Neural Information Processing Systems 32 (Proc. NeurIPS 2019)","author":"Dobriban,","year":"2019"},{"key":"2021051519490459200_B14","first-page":"1127","article-title":"Sampling algorithms for $\\ell_{2}$ regression and applications","volume-title":"Proc. 17th Annual ACM-SIAM Sympos. Discrete Algorithm (SODA \u201906)","author":"Drineas,","year":"2006"},{"key":"2021051519490459200_B15","doi-asserted-by":"crossref","DOI":"10.1214\/lnms\/1196285102","volume-title":"Multivariate Statistics: A Vector Space Approach","author":"Eaton,","year":"2007"},{"key":"2021051519490459200_B16","volume-title":"Bayesian Data Analysis","author":"Gelman,","year":"2014","edition":"3rd ed"},{"key":"2021051519490459200_B17","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1007\/s11222-015-9608-z","article-title":"Random projections for Bayesian regression","volume":"27","author":"Geppert,","year":"2017","journal-title":"Statist. Comp."},{"key":"2021051519490459200_B18","doi-asserted-by":"crossref","first-page":"1500","DOI":"10.1080\/01621459.2014.969425","article-title":"Bayesian compressed regression","volume":"110","author":"Guhaniyogi,","year":"2015","journal-title":"J. Am. Statist. Assoc."},{"key":"2021051519490459200_B19","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1137\/090771806","article-title":"Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions","volume":"53","author":"Halko,","year":"2011","journal-title":"SIAM Rev."},{"key":"2021051519490459200_B20","doi-asserted-by":"crossref","first-page":"e1000529","DOI":"10.1371\/journal.pgen.1000529","article-title":"A flexible and accurate genotype imputation method for the next generation of genome-wide association studies","volume":"5","author":"Howie,","year":"2009","journal-title":"PLoS Genet."},{"key":"2021051519490459200_B21","first-page":"287","article-title":"Very sparse random projections","volume-title":"Proc. 12th ACM-SIGKDD Int. Conf. Knowledge Discovery and Data Mining","author":"Li,","year":"2006"},{"key":"2021051519490459200_B22","first-page":"3217","volume-title":"Proc. 35th Int. Conf. Machine Learning","author":"Lopes,","year":"2018"},{"key":"2021051519490459200_B23","first-page":"861","article-title":"A statistical perspective on algorithmic leveraging","volume":"16","author":"Ma,","year":"2015","journal-title":"J. Mach. Learn. Res."},{"key":"2021051519490459200_B24","doi-asserted-by":"crossref","first-page":"70","DOI":"10.1002\/wics.1324","article-title":"Leveraging for big data regression","volume":"7","author":"Ma,","year":"2015","journal-title":"WIREs Comp. Statist."},{"key":"2021051519490459200_B25","first-page":"123","article-title":"Randomized algorithms for matrices and data","volume-title":"Foundations and Trends in Machine Learning","author":"Mahoney,","year":"2011"},{"key":"2021051519490459200_B26","first-page":"137","volume-title":"Handbook of Big Data","author":"Mahoney,","year":"2016"},{"key":"2021051519490459200_B27","first-page":"1842","article-title":"Iterative Hessian sketch: Fast and accurate solution approximation for constrained least-squares","volume":"17","author":"Pilanci,","year":"2016","journal-title":"J. Mach. Learn. Res."},{"key":"2021051519490459200_B28","volume-title":"R: A Language and Environment for Statistical Computing","year":"2021"},{"key":"2021051519490459200_B29","first-page":"7508","article-title":"A statistical perspective on randomized sketching for ordinary least-squares","volume":"17","author":"Raskutti,","year":"2016","journal-title":"J. Mach. Learn. Res."},{"key":"2021051519490459200_B30","first-page":"143","article-title":"Improved approximation algorithms for large matrices via random projections","volume-title":"47th Annual IEEE Sympos. Foundations of Computer Science (FOCS\u201906)","author":"Sarlos,","year":"2006"},{"key":"2021051519490459200_B31","doi-asserted-by":"crossref","DOI":"10.1002\/9781118491782","volume-title":"Linear Models","author":"Searle,","year":"1997"},{"key":"2021051519490459200_B32","article-title":"Min-wise hashing for large-scale regression and classification with sparse data","author":"Shah,","year":"2018"},{"key":"2021051519490459200_B33","author":"Wickham,","year":"2014","journal-title":"nycflights13: Flights that Departed NYC in 2013"},{"key":"2021051519490459200_B34","first-page":"1","article-title":"Sketching as a tool for numerical linear algebra","volume-title":"Foundations and Trends in Theoretical Computer Science","author":"Woodruff,","year":"2014"}],"container-title":["Biometrika"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/biomet\/advance-article-pdf\/doi\/10.1093\/biomet\/asaa062\/33862803\/asaa062.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"http:\/\/academic.oup.com\/biomet\/article-pdf\/108\/2\/283\/37938896\/asaa062.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/academic.oup.com\/biomet\/article-pdf\/108\/2\/283\/37938896\/asaa062.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,4]],"date-time":"2023-10-04T17:44:40Z","timestamp":1696441480000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/biomet\/article\/108\/2\/283\/5878938"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,30]]},"references-count":34,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2020,7,30]]},"published-print":{"date-parts":[[2021,5,15]]}},"URL":"https:\/\/doi.org\/10.1093\/biomet\/asaa062","relation":{},"ISSN":["0006-3444","1464-3510"],"issn-type":[{"value":"0006-3444","type":"print"},{"value":"1464-3510","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2021,6,1]]},"published":{"date-parts":[[2020,7,30]]}}}