qre#

Purpose#

Computes the orthogonal-triangular (QR) decomposition of a matrix x, such that: \(X[.,E] = Q_1R\)

Format#

{ r, e } = qre(x)#

Parameters:

x (NxP matrix) – data

Returns:

r (KxP upper triangular matrix) – \(K = min(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{split}Q′X[.,E] = \begin{bmatrix} R \\ 0 \end{bmatrix}\end{split}\]

where \(R\) is upper triangular. If we partition

\[Q⁢ = \begin{bmatrix} Q_1 & Q_2 \end{bmatrix}\]

where \(Q_1\) has \(P\) columns, then

\[X[.,E] = Q_1R\]

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 \(QY\), \(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{bmatrix} X_1 & X_2 \end{bmatrix}\]

where \(X_1\) is NxM and \(X_2\) is Nx(P-M). Further partition \(R\) in the following way:

\[\begin{split}R = \begin{bmatrix} R_{11} & R_{12} \\ 0 & 0 \end{bmatrix}\end{split}\]

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

\[A = R_{11}^{-1}R_{12}\]

and

\[X_2 = X_1A\]

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{bmatrix} R_1 & R_2 \end{bmatrix}\]

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