[TOC]

`qr`

QR decomposition

Introduction

Let $A$ be an $m\times n$ matrix. It can be factorised such that $A=QR$ , where $Q$ is an $m\times m$ orthogonal matrix and $R$ is $m\times n$ such that

𝟘

In the above equation,

$R_1$ is an $n\times n$ upper triangular matrix,
$\mathbb{0}$ is an $(m-n)\times n$ matrix of zeros,
$R_2$ is an $m\times m$ upper triangular matrix,
and $R_3$ is $m\times(n-m)$ .

Permutation

The error in $Q$ and $R$ can be improved by permuting columns of $A$ before factorisation. The permutation is done by multiplying $A$ with a given matrix $P$ , i.e.,

where the permuted matrix $\bar{R}$ is defined as $RP$ . The matrix $P$ is given such that diagonal elements of $\bar{R}$ are arranged in decreasing order of their absolute values (or moduli if A is complex).

The matrix $P$ can also be constructed from a given permutation vector $e=\begin{bmatrix}e_1,e_2,\ldots,e_n\end{bmatrix}$ such that

for all $i$ and $j$ .

Thin Factorisation

Suppose that $m>n$ . Let $Q=\begin{bmatrix}Q_1&|&Q_2\end{bmatrix}$ , where $Q_1$ is $m\times n$ . We can perform the thin QR factorisation:

𝟘

Note that $Q_1$ and $R_1$ are sub-matrices of $Q$ and $R$ , respectively. Hence, the thin factorisation is potentially more economical in terms of computation.

The error in $Q_1$ and $R_1$ can be improved by permuting columns of $A$ before factorisation:

𝟘

The matrix $P$ is constructed by

for all $i$ and $j$ , where $e=\begin{bmatrix}e_1,e_2,\ldots,e_n\end{bmatrix}$ is a given permutation vector.

Usages

`R = qr(A)`

`R = qr(A, 0)`

`R = qr(A, 'vector')`

`R = qr(A, 'matrix')`

A is an $m\times n$ matrix, which can be real or complex.
When one output argument is assumed, it returns the $m\times n$ matrix R such that $R$ in Equation (1) is given by triu(R).
All of the above give the same result regardless of the second input argument.

`[Q,R] = qr(A)`

`[Q,Rp,P] = qr(A)`

`[Q,Rp,e] = qr(A, 'vector')`

`[Q,Rp,P] = qr(A, 'matrix')`

`[Q1,R1] = qr(A, 0)`

`[Q1,Rp1,e] = qr(A, 0)`

A is an $m\times n$ matrix, which can be real or complex.
Correspondences between the output arguments and the variables in the above equations can be seen from the table below:

Output arguments	Variables in the equations	Sizes	Meaning
`Q`	$Q$	$m\times m$	$Q$
`Q1` if $m> n$	$Q_1$	$m\times n$	Thin $Q$
`Q1` if $m\leq n$	$Q$	$m\times m$	$Q$
`R`	$R$	$m\times n$	$R$
`Rp`	$\bar{R}$	$m\times n$	Permuted $R$
`R1` if $m> n$	$R_1$	$n\times n$	Thin $R$
`R1` if $m\leq n$ (no thinning possible)	$R$	$m\times n$	$R$
`Rp1` if $m> n$	$\bar{R}_1$	$n\times n$	Permuted thin $R$
`Rp1` if $m\leq n$ (no thinning possible)	$\bar{R}$	$m\times n$	Permuted $R$
`P`	$P$	$n\times n$	Permutation matrix
`e`	$e$	$1\times n$	Permutation vector

Examples

Factorising matrices of different sizes give different forms of R.

Input

A = rand(3,5);
[Q,R] = qr(A);
% m < n. Therefore, R has the form [R2 R3]
% where R2 is upper triangular
R
% Q*R and A are the same
% (ignoring rounding errors)
Q*R-A

B = rand(5,3);
[Q,R] = qr(B);
% m > n. Therefore, R has the form [R1;0] 
% where R1 is upper triangular
R
% Q*R and B are the same
% (ignoring rounding errors)
Q*R-B

Output

R = 
-1.2683  -0.2718  -0.7296  -0.4461  -0.9179
 0.0000  -0.7927  -0.0660   0.0097  -0.6946
 0.0000   0.0000   0.4922   0.3550   0.2499

ans = 1e-16 × 
 0.0000   0.1388   0.5551   0.5551   2.7756
-0.2776   0.0000  -0.2776   0.1388   0.0000
 0.0000  -0.1388   0.0000   0.0000   2.2204

R = 
-1.4719  -0.5101  -1.2602
 0.0000  -0.2651  -0.6190
 0.0000   0.0000  -0.3916
 0.0000   0.0000   0.0000
 0.0000   0.0000   0.0000

ans = 1e-16 × 
 0.0000   0.0000   2.7756
-1.1102   0.0000  -1.1102
 0.0000   0.0000   1.1102
 0.0000   0.5551  -1.1102
 0.0000   0.5551   1.1102

Performing factorization without returning the zero matrix.

Input

A = rand(5,3);
[Q,R] = qr(A);
% R has the form [R1;0]
% where R1 is upper triangular
R

% With the second input argument being 0,
% qr() returns the upper triangular matrix
% without giving the zero matrix
[Q,R1] = qr(A,0);
R1

Output

R = 
-1.5226  -0.4083  -0.8611
 0.0000   0.7716   0.7349
 0.0000   0.0000  -0.4714
 0.0000   0.0000   0.0000
 0.0000   0.0000   0.0000

R1 = 
-1.5226  -0.4083  -0.8611
 0.0000   0.7716   0.7349
 0.0000   0.0000  -0.4714

Decomposition with permutation.

Input

A = rand(3,5);
[Q,R,P] = qr(A,'matrix');
% A*E and Q*R are the same
% (ignoring rounding errors)
A*P-Q*R

Output

ans = 1e-16 × 
 1.1102   1.1102   0.8327   0.5551   0.0000
 0.0000   1.1102   0.9714   0.0000   0.6939
 0.0000   3.3307   0.5551  -0.1388   0.0000

Obtaining a permutation matrix from the vector e.

Input

% Randomly generated matrix.
a = randi(10,4,5);

% Vector e contains permutation information.
[Q,R,e] = qr(a,'vector');

% Construct a permuation matrix P using e.
P = zeros(size(a,2));
for r = 1:size(a,2)
    P(e(r),r) = 1;
end

% Permutation matrix P2 given by qr()
% with second input argument being 'matrix'
[Q,R,P2] = qr(a,'matrix');

% Permutation matrices P and P2 are the same.
P
P2

Output

P = 
 0.0000   0.0000   0.0000   1.0000   0.0000
 0.0000   1.0000   0.0000   0.0000   0.0000
 0.0000   0.0000   0.0000   0.0000   1.0000
 1.0000   0.0000   0.0000   0.0000   0.0000
 0.0000   0.0000   1.0000   0.0000   0.0000

P2 = 
 0.0000   0.0000   0.0000   1.0000   0.0000
 0.0000   1.0000   0.0000   0.0000   0.0000
 0.0000   0.0000   0.0000   0.0000   1.0000
 1.0000   0.0000   0.0000   0.0000   0.0000
 0.0000   0.0000   1.0000   0.0000   0.0000