  Bayesian computation of high dimensional linear regression models with a
popular Gaussian scale mixture prior distribution using Markov Chain Monte
Carlo (MCMC) or its variants can be extremely slow or completely prohibitive
due to the heavy computational cost that grows in the cubic order of p, with p
as the number of features. Although a few recently developed algorithms make
the computation efficient in presence of a small to moderately large sample
size (with the complexity growing in the cubic order of n), the computation
becomes intractable when sample size n is also large. In this article we adopt
the data sketching approach to compress the n original samples by a random
linear transformation to m<<n samples in p dimensions, and compute Bayesian
regression with Gaussian scale mixture prior distributions with the randomly
compressed response vector and feature matrix. Our proposed approach yields
computational complexity growing in the cubic order of m. Another important
motivation for this compression procedure is that it anonymizes the data by
revealing little information about the original data in the course of analysis.
Our detailed empirical investigation with the Horseshoe prior from the class of
Gaussian scale mixture priors shows closely similar inference and a massive
reduction in per iteration computation time of the proposed approach compared
to the regression with the full sample. One notable contribution of this
article is to derive posterior contraction rate for high dimensional predictor
coefficient with a general class of shrinkage priors on them under data
compression/sketching. In particular, we characterize the dimension of the
compressed response vector m as a function of the sample size, number of
predictors and sparsity in the regression to guarantee accurate estimation of
predictor coefficients asymptotically, even after data compression.
