Linear Algebra Decomposition (1)

# Linear Algebra Decomposition (1) ###### tags: `Data Science`, `Linear Algebra` ## LU Decomposition $\pmb{A}=\pmb{L}\pmb{U}$: where $\pmb{L}$ is a lower triangular matrix, and the $\pmb{U}$ is an upper triangular matrix. The LU decomposition can be seen as the process of Gaussian elimination. The $\pmb{L}$ matrix is the multiplier used in the process of row reduction, while the $\pmb{U}$ matrix is the resulting row echelon form after Gaussian elimination. Suppose we have a matrix $\pmb{A}$ defined as follows: $\pmb{A}=\begin{bmatrix} A_{1,1} & A_{1,2} & \cdots & A_{1,m}\\ A_{2,1} & A_{2,2} & \cdots & A_{2,m}\\ \vdots & \vdots & \ddots & \vdots \\ A_{n,1} & A_{n,2} & \cdots & A_{n,m}\\ \end{bmatrix}$ First, we eliminate the $A_{2,1}$ element by adding the first row multiply by $-\frac{A_{2,1}}{A_{1,1}}$. This operation can be recorded as $\pmb{A'}=\pmb{E}_{(1)}\pmb{A}$, where $\pmb{E_{(1)}}=\begin{bmatrix} 1 & 0 & \cdots & 0\\ -\frac{A_{2,1}}{A_{1,1}} & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1\\ \end{bmatrix}$ The value in $\pmb{L}_{(1)\:2,1}$ means the number which the first row of $\pmb{A}$ multiply by in our first operation. Continue the Gaussian elimination process, matrix $\pmb{A}$ can be reduce to row echelon form $\pmb{U}=\pmb{E}_{(n-1)}\pmb{E}_{(n-2)}...\pmb{E}_{(1)}\pmb{A}$. Let $\pmb{L}=\pmb{E}_{(n-1)}^{-1}\pmb{E}_{(2)}^{-1}...\pmb{E}_{(n-1)}^{n-1}$ and we can derive the LU decomposition of $\pmb{A}$ to be $\pmb{A}=\pmb{L}\pmb{U}$. ## QR Decomposition $\pmb{A}=\pmb{Q}\pmb{R}$: where $\pmb{Q}$ is an orthogonal matrix and $\pmb{R}$ is an upper triangular matrix. Given the matrix $\pmb{A}$ represented with its column vectors: $\pmb{A}=\begin{bmatrix} \pmb{v}_{.,1} & \pmb{v}_{.,2} & \cdots & \pmb{v}_{.,m}\\ \end{bmatrix}$ First, to make $\pmb{v}_{.,1}$ a basis of orthornomal vectors, we turn $\pmb{v}_{.,1}$ into a unit vector by deviding its norm: $\pmb{q}_{.,1}=\frac{\pmb{v}_{.,1}}{\|\pmb{v}_{.,1}\|}$. Then we look into the second column vector $\pmb{v}_{.,2}$, and to make it a basis of orthonormal vectors, we have to make sure that the new vector is orthogonal to $\pmb{q}_{.,1}$. Therefore, we subtract $\pmb{v}_{.,2}$ with its projection onto $\pmb{q}_{.,1}$. Specifically, $\pmb{q}'_{.,2}=\pmb{v}_{.,2}-\langle\pmb{v}_{.,2},\pmb{q}_{.,1}\rangle\pmb{q}_{.,1}$ to ensure it is orthogoanl to the first vector. Similarly, we make it orthonomal by deviding its norm to get $\pmb{q}_{.,2}=\frac{\pmb{q}'_{.,2}}{\|\pmb{q}'_{.,2}\|}$. In this way, we can transform the original matrix $\pmb{A}$ into an orthogonal matrix $\pmb{Q}$, and the column vectors of $\pmb{Q}$ is defined as: $\pmb{q}_{.,k}=\frac{\pmb{q}'_{.,k}}{\|\pmb{q}'_{.,k}\|}$, where $\pmb{q}'_{.,k}=\pmb{v}_{.,k}-\sum_{i=1}^{k}\langle\pmb{v}_{.,i},\pmb{v}_{.,k}\rangle\pmb{q}_{.,i}$ Using the above equation, we can found that $\pmb{q}'_{.,1}=\pmb{v}_{.,1}$ $\pmb{q}'_{.,2}=\pmb{v}_{.,2}-\langle\pmb{v}_{.,2},\pmb{q}_{.,1}\rangle\pmb{q}_{.,1}$ $\pmb{q}'_{.,3}=\pmb{v}_{.,3}-\langle\pmb{v}_{.,3},\pmb{q}_{.,1}\rangle\pmb{q}_{.,1}-\langle\pmb{v}_{.,3},\pmb{q}_{.,2}\rangle\pmb{q}_{.,2}$ $\:\:\:\:\:\:\:\vdots$ Because $\pmb{q}_{.,k}$ forms the orthogonal basis of $\pmb{A}$. Therefore, $\|\pmb{q}'_{.,k}\|=\langle\pmb{v}_{.,k},\pmb{q}_{.,k}\rangle$ $\pmb{v}_{.,1}=\|\pmb{v}_{.,1}\|\pmb{q}_{.,1}=\langle\pmb{q}_{.,1},\pmb{v}_{.,1}\rangle\pmb{q}_{.,1}$ $\pmb{q}'_{.,2}=\|\pmb{q}'_{.,2}\|\pmb{q}_{.,2}=\pmb{v}_{.,2}-\langle\pmb{v}_{.,2},\pmb{q}_{.,1}\rangle\pmb{v}_{.,1}\\\:\:\:\:\:\Rightarrow\pmb{v}_{.,2}=\langle\pmb{v}_{.,2},\pmb{q}_{.,1}\rangle\pmb{q}_{.,1}+\|\pmb{q}'_{.,2}\|\pmb{q}_{.,2}=\langle\pmb{v}_{.,2},\pmb{q}_{.,1}\rangle\pmb{q}_{.,1}+\langle\pmb{v}_{.,2},\pmb{q}_{.,2}\rangle\pmb{q}_{.,2}$ $\pmb{q}'_{.,3}=\|\pmb{q}'_{.,3}\|\pmb{q}_{.,3}=\pmb{v}_{.,3}-\langle\pmb{v}_{.,3},\pmb{q}_{.,1}\rangle\pmb{q}_{.,1}-\langle\pmb{v}_{.,3},\pmb{q}_{.,2}\rangle\pmb{q}_{.,2} \\\:\:\:\:\:\Rightarrow\pmb{v}_{.,3}=\langle\pmb{v}_{.,3},\pmb{q}_{.,1}\rangle\pmb{q}_{.,1}+\langle\pmb{v}_{.,3},\pmb{q}_{.,2}\rangle\pmb{q}_{.,2}+\|\pmb{q}'_{.,3}\|\pmb{q}_{.,3}=\langle\pmb{v}_{.,3},\pmb{q}_{.,1}\rangle\pmb{q}_{.,1}+\langle\pmb{v}_{.,3},\pmb{q}_{.,2}\rangle\pmb{q}_{.,2}+\langle\pmb{v}_{.,3},\pmb{q}_{.,3}\rangle\pmb{q}_{.,3}$ $\:\:\:\:\:\:\:\vdots$ This suggest that $\pmb{v}_k=\sum_{i=1}^{k}\langle\pmb{v}_{.,i},\pmb{q}_{.,k}\rangle\pmb{q}_{.,i}$. if we define two matrices: $\pmb{Q}=\begin{bmatrix} \pmb{q}_{.,1} & \pmb{q}_{.,2} & \cdots & \pmb{q}_{.,m}\\ \end{bmatrix}$ $\pmb{R}=\begin{bmatrix} \langle\pmb{q}_{.,1},\pmb{v}_{.,1}\rangle & \langle\pmb{q}_{.,1},\pmb{v}_{.,2}\rangle & \cdots & \langle\pmb{q}_{.,1},\pmb{v}_{.,m}\rangle \\ 0 & \langle\pmb{q}_{.,2},\pmb{v}_{.,2}\rangle & \cdots & \langle\pmb{q}_{.,2},\pmb{v}_{.,m}\rangle\\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \langle\pmb{q}_{.,n},\pmb{v}_{.,m}\rangle\\ \end{bmatrix}$ We can derive the QR decomposition of $\pmb{A}$ to be $\pmb{A}=\pmb{Q}\pmb{R}$. ## Reference * [Wikipedia (LU Decomposition)](https://en.wikipedia.org/wiki/LU_decomposition) * [Wikipedia (QR Decomposition)](https://en.wikipedia.org/wiki/QR_decomposition) * Gilbert Strang. 2011. "MIT 18.06SC Linear Algebra" * Gilbert Strang. 2018. "MIT 18.065 Matrix Methods in Data Analysis, Signal Processing, and Machine Learning"