An even faster algorithm for ridge regression of reduced rank data

Hawkins and Yin (Comput. Statist. Data Anal. 40 (2002) 253) describe an algorithm for ridge regression of reduced rank data, i.e. data where pp, the number of variables, is larger than nn, the number of observations. Whereas a direct implementation of ridge regression in this setting requires calculations of order O(np2+p3)O(np2+p3), their algorithm uses only calculations of order O(np2)O(np2). In this paper, we describe an alternative algorithm based on a factorization of the (transposed) design matrix. This approach is numerically more stable, further reduces the amount of calculations and needs less memory. In particular, we show that the factorization can be calculated in O(n2p)O(n2p) operations. Once the factorization is obtained, for any value of the ridge parameter the ridge regression estimator can be calculated in O(np)O(np) operations and the generalized cross-validation score in O(n)O(n) operations.