> For the complete documentation index, see [llms.txt](https://theshank.gitbook.io/ai/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://theshank.gitbook.io/ai/linear-algebra/matrix-decomposition/qr-decomposition.md).

# QR Decomposition

For any real square matrix $$A$$we have

$$
A = QR
$$

Where $$Q$$is an orthogonal matrix and $$R$$is an upper trianguler matrix. 

* Used to solve linear least square problems. 

### Orthogonal Matrices

Remember that the orthogonal matrix preserves lengths and angles in linear space. This means that multiplying a vector by an orthogonal matrix will preserve lengths and angles between vectors. 

### Upper Triangular Matrices

What does the upper triangular matrix mean? So let's say if we have an upper triangular matrix $$R$$.

$$
XR = Y
$$

$$Y$$ columns are linear combinations of columns of $$X$$in proportion decided by values in matrix $$R$$. Since $$R$$ is an upper triangular matrix, it means that any column of $$Y$$is linear combination of only columns on or before that column in $$X$$i.e column $$i$$ of $$Y$$is combinations of columns $$1:i$$ of $$X$$. 

The first *k* columns of *Q* form an orthonormal basis for the [span](https://en.wikipedia.org/wiki/Linear_span) of the first *k* columns of *A* for any 1 ≤ *k* ≤ *n*. The fact that any column *k* of *A* only depends on the first *k* columns of *Q* is responsible for the triangular form of *R*.

### Derivation of QR factorization

![](https://1877261540-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-LFDuA0A2VRqmT31Blrq%2Fuploads%2FsewM3OVOOr7FBdUlqIaE%2FPXL_20220310_215544665.jpg?alt=media\&token=dae83070-b382-4333-be61-ed2277fd8130) ![](https://1877261540-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-LFDuA0A2VRqmT31Blrq%2Fuploads%2FEnApTFxk3VjM7jPlGfm3%2FPXL_20220310_215554120.jpg?alt=media\&token=e6ff7cd4-2b91-421c-afdc-053db46741d1)

The process described in the pictures above is called **Gram-Schimdt Orthogonalizatoin procedure.** 

So basically **QR** decomposition captures the gram-schimdt orthogonailzation. it decomposed the matrix $$A$$as to how to get multiply an orthogonal matrix $$Q$$by an upper triangular matrix $$R$$. 

### Solving Linear Square Solution with QR factorization

{% embed url="<https://youtu.be/7KP6TO5JXYY>" %}

{% embed url="<https://youtu.be/hBOruhKIItE>" %}

### Relationship between QR and Cholesky Decomposition

The QR decomposition of tall matrix $$A$$ of full rank is closely related to the problem of computing a Cholesky factorization of the nonsingular matrix $$A^TA$$. Specifically, if $$A=QR$$, then $$A^TA=R^TQ^TQR=LL^T$$ where the lower triangular matrix $$L=R^T$$ can now be identified as the Cholesky factor of $$A^TA$$.