The QR decomposition of a matrixMatrices > Basics | Matrix products | Special matrices | QR | Matrix inverses | Linear maps | Matrix norms | Applications
Basic ideaThe basic goal of the QR decomposition is to factor a matrix as a product of two matrices (traditionally called , hence the name of this factorization). Each matrix has a simple structure which can be further exploited in dealing with, say, linear equations. The QR decomposition is nothing else than the Gram-Schmidt procedure applied to the columns of the matrix, and with the result expressed in matrix form. Consider a matrix , with each a column of . Case when is full column rankAssume first that the 's (the columns of ) are linearly independent. Each step of the G-S procedure can be written as We write this as where () and . Since the 's are unit-length and normalized, the matrix satisfies . The QR decomposition of a matrix thus allows to write the matrix in factored form: where is a matrix with , and is ,upper-triangular. Matlab syntax
>> [Q,R] = qr(A,0); % A is a mxn matrix, Q is mxn orthogonal, R is nxn upper triangular Example: QR decomposition of a 4x6 matrix. Case when the columns are not independentWhen the columns of are not independent, at some step of the G-S procedure we encounter a zero vector , which means is a linear combination of . The modified Gram-Schmidt procedure then simply skips to the next vector and continues. In matrix form, we obtain , with , , and has an upper staircase form, for example: (This is simply an upper triangular matrix with some rows deleted. It is still upper triangular.) We can permute the columns of to bring forward the first non-zero elements in each row: where is a permutation matrix (that is, its columns are the unit vectors in some order), whose effect is to permute columns. (Since is orthogonal, .) Now, is square, upper triangular, and invertible, since none of its diagonal elements is zero. The QR decomposition can be written where
Matlab syntax
>> [Q,R,inds] = qr(A,0); % here inds is a permutation vector such that A(:,inds) = Q*R Full QR decompositionThe full QR decomposition allows to write where is square and orthogonal (). In other words, the columns of are an orthonormal basis for the whole output space , not just for the range of . We obtain the full decomposition by appending an identity matrix to the columns of : . The QR decomposition of the augmented matrix allows to write where the columns of the matrix are orthogonal, and is upper triangular and invertible. (As before, is a permutation matrix.) In the G-S procedure, the columns of are obtained from those of , while the columns of come from the extra columns added to . The full QR decomposition reveals the rank of : we simply look at the elements on the diagonal of that are not zero, that is, the size of . Matlab syntax
>> [Q,R] = qr(A); % A is a mxn matrix, Q is mxm orthogonal, R is mxn upper triangular Example: QR decomposition of a 4x6 matrix. |