2020/07/21 by Swarnadip Ghosh, Trevor Hastie, Ghosh, Swarnadip +3 · 2 citations
Mathematics · Physics and Astronomy · #Computation (stat.CO) #FOS: Computer and information sciences #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Methodology (stat.ME) #Random Matrices and Applications #Statistical Mechanics and Entropy #Statistics Theory (math.ST) #math.ST #stat.CO #stat.ME #stat.TH
paper · pdf · doi:10.48550/arxiv.2007.10612
openalex publication_date 2020/07/21 · arxiv created 2021/03/18 · arxiv updated 2021/03/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
Regression models with crossed random effect errors can be very expensive to compute. The cost of both generalized least squares and Gibbs sampling can easily grow as N3/2 (or worse) for N observations. Papaspiliopoulos et al. (2020) present a collapsed Gibbs sampler that costs O(N), but under an extremely stringent sampling model. We propose a backfitting algorithm to compute a generalized least squares estimate and prove that it costs O(N). A critical part of the proof is in ensuring that the number of iterations required is O(1) which follows from keeping a certain matrix norm below 1-δ for some δ>0. Our conditions are greatly relaxed compared to those for the collapsed Gibbs sampler, though still strict. Empirically, the backfitting algorithm has a norm below 1-δ under conditions that are less strict than those in our assumptions. We illustrate the new algorithm on a ratings data set from Stitch Fix.