Summary: Solving an inverse problem means determining the parameters of a model given a set of measurements. In solving many practical inverse problems, accounting for the uncertainty of the solution is very important in aiding decision-making. A standard approach to do this begins by choosing a model parametrization and then using a Bayesian approach to make inferences on the model parameters from measurement data. However, this quantified uncertainty is a function of the model parametrization and for many inverse problems; there are many model parametrizations that account for the data equally well. A well-known approach to accounting for model uncertainty is Bayesian model averaging, where many model parametrizations are considered. Significant computational costs are associated with this method because one must compute the posterior distribution for each model parametrization. We consider a family of model parametrizations given by decimated wavelet bases. By decimated wavelet basis we mean a subset of the model's coordinates in a wavelet basis. For linear inverse problems, we demonstrate new fast algorithms for updating the prior and posterior covariance matrices when wavelet model parameters are added or deleted from the decimated basis. We also introduce algorithms for updating the determinant and Cholesky decomposition of the model's covariance matrices. These algorithms deliver order of magnitude savings over computing these covariance matrices from scratch and make Bayesian model averaging a realistic approach for accounting for uncertainty in inverse problem solutions. In order to clarify the role of our model updates, we show that our wavelet model update algorithms update the model's posterior distribution after modifying the model's local spatial resolution, whereas Kalman filters provide a means of updating a model when assimilating new measurement data. These results show a major advantage to be gained by parametrizing models with wavelets and represent a significant step forward in addressing the challenging computational problem of dealing with large models that account for uncertainty.