三角矩阵
三角矩阵首先是方阵，其次，如果这个方阵对角线上面或下面（不含对角线）的元素都为0的话，那么这个矩阵就被称为三角矩阵。如果是上面的元素都为0，则称之为下三角矩阵，反之则是上三角矩阵。
$$ \mathbf{上三角矩阵} \begin{bmatrix} a_{11} & a_{12} & ... & a_{1n} \\ 0 & a_{22} & ... & a_{2n} \\ 0 & 0 & ... & a_{3n} \\ ... & ... & ... & .... \\ 0 & 0 & 0.. & a_{nn} \\ \end{bmatrix} $$ $$ \mathbf{下三角矩阵} \begin{bmatrix} a_{11} & 0 & ... & 0 \\ a_{21} & a_{22} & 0.. & 0 \\ a_{31} & a_{32} & ... & 0 \\ ... & ... & ... & ... \\ a_{n1} & a_{n2} & ... & a_{nn} \\ \end{bmatrix} $$三角矩阵有一个非常好的性质，那就是在作为一个方程组的参数时，那么可以快速地解这个方程组，假设矩阵A是一个下三角矩阵，那么方程组 $$$ Ax = b $$$，可以很快地解出，解普通方程组节省很多时间，这个方程组的解具有如下形式
$$ \begin{eqnarray*} x_1 &=& \frac{b_1}{a_{11}} \\ x_2 &=& \frac{b_2 - a_{21}x_1}{a_{22}} \\ x_3 &=& \frac{b_3 - a_{31}x_1 - a_{32}x_2}{a_{33}} \\ ... \\ x_n &=& \frac{b_n - \sum_{i=1}^{n-1} a_{ni}x_i }{a_{nn}} \end{eqnarray*} $$Cholesky Descomposition
由于三角矩阵具有非常好的性质，因此我们在计算时，我们可以把一个矩阵分解成两个三角矩阵乘积的形式，从而可以利用三角矩阵的优点，但并不是任何矩阵都可以转化成三角矩阵形式的。在实数域，只有正定矩阵（positive defined matrix）才满足条件。假设矩阵A是堆成的正定矩阵，把A分解成如下形式就是Cholesky Decomposition,其中U为上三角矩阵，L为下三角矩阵。 $$ \begin{eqnarray*} A &=& U^T U \\ A &=& L L^T \end{eqnarray*} $$
正定矩阵
首先我们需要知道什么是正定矩阵。首先正定矩阵是对称的，对称很容易理解，即矩阵A中的所有元素，有$$$ a_{ij} = a_{ji}$$$，那么A必然是方阵；此外对于任何非零的向量z，正定矩阵A满足$$$ z^T A z > 0 $$$。正定矩阵还有如下性质：
- 正定矩阵是非奇异矩阵。假设A为正定矩阵，对于任意非零向量x，满足 $$ x^T A x > 0 $$ 那么我们可以得到 $$ A x \neq 0 $$ 所以正定矩阵是非奇异矩阵。
- 对角线上的所有元素都是正的。令$$$e_i$$$表示第i个元素为1，其余为0的单位向量，那么 $$ a_{ii} = e_i^T A e_i > 0 $$
- 正定矩阵的Schur补也是正定矩阵。对于正定矩阵 $$ A_n = \begin{bmatrix} a_{11} & a_{n1}^T \\ a_{n1} & A_{n-1} \end{bmatrix} $$ 其中$$$a_{11}$$$为实数，$$$a_{n1}$$$为向量，$$$A_{n-1}$$$为方阵。$$$A_n$$$的Schur补为 $$ S = A_{n-1} - \frac{1}{a_{11}} a_{n1} a_{n1}^T $$ 令w为实数，v为长度为n-1的任意向量，由于$$$A_n$$$为正定矩阵，因此我们有 $$ \begin{eqnarray*} [w, v^T] A_n [w, v^T]^T &>& 0 \\ w^2a_{11} + wv^T a_{n1} + wa_{n1}^Tv + v^TA_{n-1}v &>& 0 \end{eqnarray*} $$ 要证明S为正定矩阵，只需要证明对于任意非零向量v，$$$v^T S v > 0 $$$即可，也就要证明 $$ \begin{eqnarray*} v^T A_{n-1} v - \frac{1}{a_{11}}v^T a_{n1} a_{n1}^T v > 0 \end{eqnarray*} $$ 观察上面两个不等式发现，只需要令 $$ \begin{eqnarray*} w^2a_{11} + wv^Ta_{n1} + wa_{n1}^Tv + v^TA_{n-1}v&=& v^TA_{n-1}v- \frac{1}{a_{11}} v^Ta_{n1}a_{n1}^Tv \\ w^2a_{11} + 2w v^Ta_{n1} + \frac{1}{a_{11}}(v^T a_{n1})^2 &=& 0 \\ w^2 + \frac{2v^Ta_{n1}}{a_{11}}w + (\frac{(v^T a_{n1})}{a_{11}})^2 &=& 0 \\ (w + \frac{v^T a_{n1}}{a_{11}})^2 &=& 0 \\ w &=& -\frac{1}{a_{11}} v^T a_{n1} \end{eqnarray*}$$ 所以对任意的非零向量v，我们可以令$$$w = -\frac{1}{a_{11}} v^T a_{n1} $$$，根据$$$A_n$$$的性质，我们可以证明$$$v^T S v > 0$$$。因此，正定矩阵的Schur补也是正定矩阵。
为什么正定矩阵可以分成三角矩阵的乘积？
假设正定矩阵可以分解为两个三角矩阵的乘积。不妨令$$$ A_n = L_n L_n^T $$$，同时分别将$$$A_n$$$ 和 $$$L_n$$$ 写作
$$ \begin{eqnarray*} A_n &=& \begin{bmatrix} a_{11} & a_{n1}^T \\ a_{n1} & A_{n-1} \end{bmatrix} \\ L_n &=& \begin{bmatrix} l_{11} & 0 \\ l_{n1} & L_{n-1} \end{bmatrix} \end{eqnarray*} $$ 如果我们能证明下面的等式成立，那么我们就证明了正定矩阵可以分成了两个三角矩阵的乘积。 $$\begin{eqnarray*} A_n &=& L_n L_n^T \\ \begin{bmatrix} a_{11} & a_{n1}^T \\ a_{n1} & A_{n-1} \end{bmatrix} &=& \begin{bmatrix} l_{11} & 0 \\ l_{n1} & L_{n-1} \end{bmatrix} \begin{bmatrix} l_{11} & l_{n1}^T \\ 0 & L_{n-1}^T \end{bmatrix} &=& \begin{bmatrix} l_{11}^2 & l_{11}l_{n1}^T \\ l_{11}l_{n1} & l_{n1}l_{n1}^T + L_{n-1}L_{n-1}^T \end{bmatrix} \end{eqnarray*}$$由于$$$A_n$$$是正定矩阵，而正定矩阵对角线上的元素都为正，因而$$$a_{11} > 0 $$$，所以我们得到
$$ l_{11} = \sqrt{a_{11}} $$因为 $$$ a_{n1} = l_{11}l_{n1} $$$，所以我们可以得到
$$ l_{n1} = \frac{1}{\sqrt{a_{11}}} a_{n1} $$至此，我们只需要证明 $$$ A_{n-1} = l_{n1}l_{n1}^T + L_{n-1}L_{n-1}^T $$$，既可以证明正定矩阵可以分解成三角矩阵的乘积，也就是证明
$$\begin{eqnarray*} A_{n-1} - l_{n1}l_{n1}^T &=& L_{n-1}L_{n-1}^T \\ A_{n-1} - \frac{1}{a_{11}} &=& L_{n-1}L_{n-1}^T \end{eqnarray*}$$观察上面的等式，我们发现，只需要证明 $$$ A_{n-1} - \frac{1}{a_{11}} $$$ 是正定矩阵就可以了。而这个表达式恰好是矩阵$$$A_n$$$的Schur补，根据正定矩阵的性质，我们知道这个表达式也是正定矩阵。接着我们采用归纳证明，假设维度为n-1的正定矩阵可以分解成下三角矩阵和上三角矩阵的乘积，那么根据上面的分析，我们知道维度为n的正定矩阵也可以分解成下三角矩阵和上三角矩阵的乘积；当n=1时，显然可以分解成三角矩阵的乘积。因此我们证明了$$$ A_{n-1} = l_{n1}l_{n1}^T + L_{n-1}L_{n-1}^T$$$，从而也就证明了Cholesky Decomposition。
在Least Angle Regression 中的运用
在最小角回归中，有一个矩阵$$$X_A$$$是专门用来记录选中的特征，在每一步中我们都需要计算$$$(X_A^T X_A)^{-1}$$$。$$$X_A = (...,s_jX_j,...) $$$，$$$X_j$$$ 表示被选择的特征，$$$s_j$$$表示$$$X_j$$$与期望输出相关性的正负。$$$X_A$$$是逐渐增大，一般在最小角回归的每一步中增加一个列向量，正是这个特点，可以使我们利用Cholesky Decomposition来简化逆矩阵的计算。
上面已经证明过正定矩阵一定可以分解为下三角矩阵和上三角矩阵的乘积。所以$$$ X_A^T X_A$$$是正定矩阵的话，那么它也可以分解为三角矩阵的乘积。显然，这是很好证明的，首先由于需要计算$$$X_A^TX_A$$$的逆矩阵，所以最小角回归的前提必然要求所有的特征向量都是线性无关的，这是前提条件。既然$$$X_A^TX_A$$$存在逆矩阵，那么对于任意非零的向量z,$$$z^T X_A^T X_A z = (X_Az)^T(X_Az) > 0$$$，因为如果等于0的话，必然要求$$$X_Az = 0$$$，这样的话就说明存在线性相关的特征向量，与前提矛盾。所以至此我们证明了$$$X_A^T X_A$$$是正定矩阵。
由于$$$X_A^T X_A$$$是正定矩阵，且$$$X_A$$$每一步中增加一个列向量，因此我们正好可以采用递进的方式逐步计算每一步中的分解矩阵。假设$$$A_n$$$可以分解为$$$A_n= U_n^T U_n$$$，其中$$$U_n$$$为上三角矩阵。
$$\begin{eqnarray*} A_n &=& U_n^T U_n \\ \begin{bmatrix} A_{n-1} & a_{1n} \\ a_{1n}^T & a_{nn} \end{bmatrix} &=& \begin{bmatrix} U_{n-1}^T & 0 \\ u_{1n}^T & u_{nn} \end{bmatrix} \begin{bmatrix} U_{n-1} & u_{1n} \\ 0 & u_{nn} \end{bmatrix} \\ &=& \begin{bmatrix} U_{n-1}^T U_{n-1} & U_{n-1}^T u_{1n} \\ u_{1n} U_{n-1} & u_{1n}^T u_{n1} + u_{nn}^2 \end{bmatrix} \end{eqnarray*} $$由于每一步中$$$X_A^TX_A$$$都是正定矩阵，因此$$$A_{n-1}$$$也可以分解成三角矩阵的乘积，所以$$$U_{n-1}$$$可以从上一步得到。接着我们可以利用上面得到的递推公式，在第n-1步时，我们得到了$$$U_{n-1}$$$，且其为三角矩阵，通过解$$$U_{n-1}^T u_{1n} = a_{1n} $$$，我们可以快速地得到$$$u_{1n}$$$，接着就可以计算出$$$u_{nn}$$$，所以每一步的计算量都不大的。初始时，$$$X_A^TX_A$$$就一个元素，直接开方即可得到$$$U_1$$$，之后步骤中使用上述递推公式即可。