38.6.2 Tall Skinny QR (TSQR) Approach

An algorithm which has better numerical stability for ill-conditioned problems is known as the Tall Skinny QR (TSQR) method. This method is based on computing the thin QR decomposition of the least squares matrix X = Q R, where Q is an n-by-p matrix with orthogonal columns, and R is a p-by-p upper triangular matrix. Once these factors are calculated, the residual becomes

\chi^2 = || Q^T y - R c ||^2 + \lambda^2 || c ||^2

which can be written as the matrix equation

[ R ; \lambda I ] c = [ Q^T b ; 0 ]

The matrix on the left hand side is now a much smaller 2p-by-p matrix which can be solved with a standard SVD approach. The Q matrix is just as large as the original matrix X, however it does not need to be explicitly constructed. The TSQR algorithm computes only the p-by-p matrix R and the p-by-1 vector Q^T y, and updates these quantities as new blocks are added to the system. Each time a new block of rows (X_i,y_i) is added, the algorithm performs a QR decomposition of the matrix

[ R_(i-1) ; X_i ]

where R_{i-1} is the upper triangular R factor for the matrix

[ X_1 ; ... ; X_(i-1) ]

This QR decomposition is done efficiently taking into account the sparse structure of R_{i-1}. See Demmel et al, 2008 for more details on how this is accomplished. The number of operations for this method is O(2np^2 - {2 \over 3}p^3).