12.1 QR Decomposition

QR Decomposition

The QR decomposition of a general matrix $A\in {\mathbb{R}}^{m\times n}$ is its factorization into the product of a matrix with orthonormal columns $Q\in {\mathbb{R}}^{m\times n}$, and an upper triangular matrix $R\in {\mathbb{R}}^{n\times n}$, for which
$A=QR,$

where $Q=\left[\begin{array}{cccc}{\vec{q}}_1& {\vec{q}}_2& \dots & {\vec{q}}_l\end{array}\right]$, and $R=\left[\begin{array}{cccc}⟨{\vec{a}}_1,{\vec{q}}_1⟩& ⟨{\vec{a}}_2,{\vec{q}}_1⟩& \dots & ⟨{\vec{a}}_l,{\vec{q}}_1⟩\\ 0& ⟨{\vec{a}}_2,{\vec{q}}_2⟩& \dots & ⟨{\vec{a}}_l,{\vec{q}}_2⟩\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \dots & ⟨{\vec{a}}_l,{\vec{q}}_l⟩\end{array}\right].$

Intuition

We can interpret the QR decomposition of $A$ as a change of basis, where an upper-triangular matrix can be transformed into any matrix using an orthonormal basis. More particularly,

• $A$ is originally expressed in some arbitrary coordinate system (its column vectors may not be orthogonal).
• In QR decomposition, we convert the basis of $A$ into an orthonormal basis to make computations easier:
  • $Q$ contains the orthonormal basis, computed using Gram-Schmidt.
  • $R$ describes how the original coordinates of $A$ are represented in this new basis.
    Then,

For example, we can perform a real change of basis on $A$ to find $R$, such that $Q^{T}A=R$

Properties

(Full Rank Matrix) If $A$ has full rank,

Examples

Least Squares Using QR