  We present algorithms that substantially accelerate partition-based
cross-validation for machine learning models that require matrix products
$\mathbf{X}^\mathbf{T}\mathbf{X}$ and $\mathbf{X}^\mathbf{T}\mathbf{Y}$. Our
algorithms have applications in model selection for, e.g., principal component
analysis (PCA), principal component regression (PCR), ridge regression (RR),
ordinary least squares (OLS), and partial least squares (PLS). Our algorithms
support all combinations of column-wise centering and scaling of $\mathbf{X}$
and $\mathbf{Y}$, and we demonstrate in our accompanying implementation that
this adds only a manageable, practical constant over efficient variants without
preprocessing. We prove the correctness of our algorithms under a fold-based
partitioning scheme and show that the running time is independent of the number
of folds; that is, they have the same time complexity as that of computing
$\mathbf{X}^\mathbf{T}\mathbf{X}$ and $\mathbf{X}^\mathbf{T}\mathbf{Y}$ and
space complexity equivalent to storing $\mathbf{X}$, $\mathbf{Y}$,
$\mathbf{X}^\mathbf{T}\mathbf{X}$, and $\mathbf{X}^\mathbf{T}\mathbf{Y}$.
Importantly, unlike alternatives found in the literature, we avoid data leakage
due to preprocessing. We achieve these results by eliminating redundant
computations in the overlap between training partitions. Concretely, we show
how to manipulate $\mathbf{X}^\mathbf{T}\mathbf{X}$ and
$\mathbf{X}^\mathbf{T}\mathbf{Y}$ using only samples from the validation
partition to obtain the preprocessed training partition-wise
$\mathbf{X}^\mathbf{T}\mathbf{X}$ and $\mathbf{X}^\mathbf{T}\mathbf{Y}$. To our
knowledge, we are the first to derive correct and efficient cross-validation
algorithms for any of the $16$ combinations of column-wise centering and
scaling, for which we also prove only $12$ give distinct matrix products.
