qre#

Purpose#

Computes the orthogonal-triangular (QR) decomposition of a matrix x, such that: $X [., E] = Q_{1} R$

Format#

{ r, e } = qre(x)#

Parameters:

x (NxP matrix) – data

Returns:

r (KxP upper triangular matrix) – $K = m i n (N, P)$ .
e (Px1 vector) – permutation vector

Remarks#

qre() is the same as qqre() but doesn’t return the $Q_{1}$ matrix. If $Q_{1}$ is not wanted, qre() will save a significant amount of time and memory usage, especially for large problems.

Given $X [., E]$ , where $E$ is a permutation vector that permutes the columns of x, there is an orthogonal matrix $Q$ such that $Q^{'} X [., E]$ is zero below its diagonal, i.e.,

\begin{array}{r} Q' X [., E] = [\begin{array}{c} R \\ 0 \end{array}] \end{array}

where $R$ is upper triangular. If we partition

Q = [\begin{matrix} Q_{1} & Q_{2} \end{matrix}]

where $Q_{1}$ has $P$ columns, then

X [., E] = Q_{1} R

is the QR decomposition of $X [., E]$ .

qre() does not return the $Q_{1}$ matrix because in most cases it is not required and can be very large. If you need the $Q_{1}$ matrix, see the function qqre(). If you need the entire $Q$ matrix, call qyre() with $Y$ set to a conformable identity matrix. For most problems $Q^{'} Y$ , $Q_{1}^{'} Y$ , or $Q Y$ , $Q_{1} Y$ , for some y, are required. For these cases see qtyre() and qyre().

If $X$ has rank $P$ , then the columns of $X$ will not be permuted. If $X$ has rank $M < P$ , then the $M$ linearly independent columns are permuted to the front of $X$ by $E$ . Partition the permuted $X$ in the following way:

X [., E] = [\begin{matrix} X_{1} & X_{2} \end{matrix}]

where $X_{1}$ is NxM and $X_{2}$ is Nx(P-M). Further partition $R$ in the following way:

\begin{array}{r} R = [\begin{array}{c} R_{11} & R_{12} \\ 0 & 0 \end{array}] \end{array}

where $R_{11}$ is MxM and $R_{12}$ is Mx(P-M). Then

A = R_{11}^{- 1} R_{12}

and

X_{2} = X_{1} A

that is, $A$ is an Mx(P-N) matrix defining the linear combinations of $X_{2}$ with respect to $X_{1}$

If $N < P$ the factorization assumes the form:

Q^{'} X = [\begin{matrix} R_{1} & R_{2} \end{matrix}]

where $R_{1}$ is a PxP upper triangular matrix and $R_{2}$ is Px(N-P). Thus $Q$ is a PxP matrix and $R$ is a PxN matrix containing $R_{1}$ and $R_{2}$ . This type of factorization is useful for the solution of underdetermined systems. For the solution of

X [., E] b = Y

it can be shown that

b = qrsol(Q'Y, R1)|zeros(N-P,1);

The explicit formation here of $Q$ , which can be a very large matrix, can be avoided by using the function qtyre().

For further discussion of QR factorizations see the remarks under qqr().

Source#

qr.src