QR DECOMPOSITION OF A MATRIX

Alicia Y. Tsai; Authors: Laurent EI Ghaoui; Contributors: Phan Hoang, Tony Tin, Ha To Tam, Nguyen Van Kep, Le Dinh Nam, Juliette Decugis, Nguyen Quoc Cuong.; Giuseppe C. Calafiore

12 QR DECOMPOSITION OF A MATRIX

12.1 Basic idea

The basic goal of the QR decomposition is to factor a matrix as a product of two matrices (traditionally called $Q, R$ , hence the name of this factorization). Each matrix has a simple structure that 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 $m\times n$ matrix $A=(a_1, \ldots ,a_n)$ , with each $a_i \in R^m$ is a column of $A$ .

12.2 Case being full column rank

Assume first that $a_1, \ldots ,a_n$ (the columns of $A$ ) are linearly independent. Each step of the G-S procedure can be written as

$a_i=\left(a_i^T q_1\right) q_1+\ldots+\left(a_i^T q_{i-1}\right) q_{i-1}+\left\|\tilde{q}_i\right\|_2 q_i, \quad i=1, \ldots, n$

We write this as

$a_i=r_{i 1} q_1+\ldots+r_{i, i-1} q_{i-1}+r_{i i} q_i, \quad i=1, \ldots, n,$

where $r_{ij}=(a_i^Tq_j) (1 \geq j \geq i-1)$ and $r_{ii}=||\tilde{q}_{ii}||_2$ .

Since the $q_i$ ‘s are unit-length and normalized, the matrix $Q=(q_1,\ldots,q_n)$ satisfies $Q^TQ=I_n$ . The QR decomposition of a $m\times n$ matrix $A$ thus allows writing the matrix in factored form:

$A=Q R, \quad Q=\left(\begin{array}{lll} q_1 & \ldots & q_n \end{array}\right), \quad R=\left(\begin{array}{cccc} r_{11} & r_{12} & \cdots & r_{1 n} \\ 0 & r_{22} & & r_{2 n} \\ \vdots & & \ddots & \vdots \\ 0 & & 0 & r_{n n} \end{array}\right)$

where $Q$ is a $m \times n$ matrix with $Q^T Q=I_n$ , and $R$ is $n \times n$ , upper-triangular.

Example: QR decomposition of a 4×6 matrix.

12.3 Case when the columns are not independent

When the columns of $A$ are not independent, at some step of the G-S procedure we encounter a zero vector $\tilde{q}_j$ , which means $a_j$ is a linear combination of $a_{j-1},\ldots,a_i$ . The modified Gram-Schmidt procedure then simply skips to the next vector and continues.

In matrix form, we obtain $A=Q R$ , with $Q \in \mathbb{R}^{m \times r}$ , $r=\mathbf{rank}(A)$ , and $R$ has an upper staircase form, for example:

$R=\left(\begin{array}{cccccc} * & * & * & * & * & *\\ 0 & 0 & * & * & * & * \\ 0 & 0 & 0 & 0 & * & * \end{array}\right).$

(This is simply an upper triangular matrix with some rows deleted. It is still upper triangular.)

We can permute the columns of $R$ to bring forward the first non-zero elements in each row:

$R=\left( R_1 \mid R_2 \right) P^T,\quad \left( R_1 \mid R_2 \right):=\left(\begin{array}{ccc|ccc} * & * & * & * & * & *\\ 0 & * & 0 & * & * & * \\ 0 & 0 & * & 0 & 0 & * \end{array}\right)$

where $P$ is a permutation matrix (that is, its columns are the unit vectors in some order), whose effect is to permute columns. (Since $P$ is orthogonal, $P^{-1}=P^T$ .) Now, $R_1$ is square, upper triangular, and invertible, since none of its diagonal elements is zero.

The QR decomposition can be written

$AP = Q \left( \begin{array}{c|c} R_1 & R_2 \end{array} \right)$

where

$Q \in \mathbb{R}^{m \times r}, Q^T Q=I_r ;$
$r$ is the $\mathbf{rank}$ of $A$ ;
$R_1$ is $r \times r$ upper triangular, invertible matrix;
$R_2$ is a $r \times (n-r)$ matrix;
$P$ is a $m \times m$ permutation matrix.

12.4 Full QR decomposition

The full QR decomposition allows to write $A=QR$ where $Q \in \mathbb{R}^{m \times m}$ is square and orthogonal ( $Q^TQ=QQ^T=I_m$ ). In other words, the columns of $Q$ are an orthonormal basis for the whole output space $R^m$ , not just for the range of $A$ .

We obtain the full decomposition by appending an $m \times m$ identity matrix to the columns of $A$ : $A \to [A,I_m]$ . The QR decomposition of the augmented matrix allows to write

$A P=Q R=\left(\begin{array}{ll} Q_1 & Q_2 \end{array}\right)\left(\begin{array}{cc} R_1 & R_2 \\ 0 & 0 \end{array}\right) .$

where the columns of the $m \times m$ matrix $Q=[Q_1,Q_2]$ are orthogonal and $R_1$ is upper triangular and invertible. (As before, $P$ is a permutation matrix.) In the G-S procedure, the columns of $Q_1$ are obtained from those of $A$ , while the columns of $Q_2$ come from the extra columns added to $A$ .

The full QR decomposition reveals the rank of $A$ : we simply look at the elements on the diagonal of $R$ that are not zero, that is, the size of $R_1$ .

Example: QR decomposition of a 4×6 matrix.

License

Icon for the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License

12.1 Basic idea

12.2 Case being full column rank

12.3 Case when the columns are not independent

12.4 Full QR decomposition

License

Share This Book