qqre#

Purpose#

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

Format#

{ q1, r, e } = qqre(x)#

Parameters:

x (NxP matrix) – data

Returns:

q1 (NxK matrix) – unitary matrix, \(K = min(N, P)\).
r (KxP matrix) – upper triangular matrix
e (Px1 vector) – permutation vector

Remarks#

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′R[\; .,\; 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\; ]\).

If you want only the \(R\) matrix, see qre(). Not computing \(Q_1\) can produce significant improvements in computing time and memory usage.

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\) is NxM and \(X_2\) is \(N \times (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 \(M \times (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#

qqr.src