  We propose a scalable algorithmic framework for exact Bayesian variable
selection and model averaging in linear models under the assumption that the
Gram matrix is block-diagonal, and as a heuristic for exploring the model space
for general designs. In block-diagonal designs our approach returns the most
probable model of any given size without resorting to numerical integration.
The algorithm also provides a novel and efficient solution to the frequentist
best subset selection problem for block-diagonal designs. Posterior
probabilities for any number of models are obtained by evaluating a single
one-dimensional integral that can be computed upfront, and other quantities of
interest such as variable inclusion probabilities and model averaged regression
estimates by carrying out an adaptive, deterministic one-dimensional numerical
integration. The overall computational cost scales linearly with the number of
blocks, which can be processed in parallel, and exponentially with the block
size, rendering it most adequate in situations where predictors are organized
in many moderately-sized blocks. For general designs, we approximate the Gram
matrix by a block-diagonal using spectral clustering and propose an iterative
algorithm that capitalizes on the block-diagonal algorithms to explore
efficiently the model space. All methods proposed in this article are
implemented in the R library mombf.
