## File: Large-Dense-Linear-Systems-TSQR.html

package info (click to toggle)
gsl-ref-html 2.3-1
• area: non-free
• in suites: bullseye, buster, sid
• size: 6,876 kB
• ctags: 4,574
• sloc: makefile: 35
 file content (122 lines) | stat: -rw-r--r-- 6,472 bytes parent folder | download
 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122  GNU Scientific Library – Reference Manual: Large Dense Linear Systems TSQR

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).