矩阵分解和线性方程组求解算法介绍

svd(奇异值分解)

分解结果：

对于方阵,其中P为的特征向量，P它是一个正交阵，Q为的特征向量，Q也是一个正交阵，S主对角的平方为的特征值并且它们是从大到小排列的均大于等于零，S是一个对角阵。

对于非方阵，其中为对角阵，P和Q都是正交阵

优点：1、能够对任意矩阵分解，适用范围广。

2、数值稳定性好，在处理病态矩阵时能提供可靠结果。

缺点：1、依赖于特征值的计算，所以计算复杂度较高。

2、对于P和Q有时分解不唯一，比如如果有零奇异值，那么分解不唯一。

QR分解

介绍：QR分解有2种方法，一种是基于古文斯方法，另一种是基于豪斯霍尔德方法，豪斯霍尔德方法计算量约是吉文斯方法的一半，这是它的优势，但对于稀疏矩阵吉文斯仍有不便之处。

分解结果：

A可逆，则,其中Q是正交阵，R是主对角线全为正的上三角阵。

A非方阵，则,其中n>s,为正交阵，,其中为主对角线上全为正的上三角阵。

优点：1、如果分解的矩阵可逆，那么分解唯一。

2、使用豪斯霍尔德方法时，数值稳定性较好，误差传播较小。

缺点：1、不能够对任意矩阵分解，比如行数小于列数时就不能分解了。

注意：QR分解不是lsqr算法，lsqr算法并没有使用QR分解，不过有类似QR分解的结构。QR分解是将矩阵分解为正交矩阵和上三角矩阵乘积的一种矩阵分解方法，主要用于求解线性方程组、计算矩阵的特征值等。而LSQR是一种用于求解线性方程组或最小二乘问题的迭代算法。下面介绍一下lsqr算法。

lsqr算法（它并不属于矩阵分解，但是为了区别于QR分解这里就简单介绍了）

介绍：主要用来求最小二乘解。

优点：1、适用于大规模问题。尤其是矩阵为稀疏矩阵时，lsqr算法能有效减少计算量和储存空间。

2、无需矩阵求逆，lsqr巧妙的避开了矩阵求逆，避免了矩阵求逆过程中可能出现的数值不稳定问题以及高昂的计算成本，特别是大型矩阵求逆计算量和难度都非常大。

3、在sklearn源码注释中说它是在{'auto', 'svd ', 'cholesky', 'lsqr', 'sparse_cg', 'sag', 'saga'}中求解岭回归模型速度是最快的。

缺点：1、依赖初始值。

2、解的精度取决于迭代次数和收敛条件。

cholesky分解

介绍：cholesky分解主要用于求解对称正定线性方程组。

分解结果：对称正定阵，L是对角元素均为正的下三角矩阵，。

优点：1、分解是唯一的。

缺点：1、要求分解矩阵是对称正定的。

sparse_cg算法(用于求解稀疏线性方程组的共轭梯度法的变体)

优点：1、计算效率高。充分利用了矩阵的稀疏性，避免了大量不必要的运算。

2、比“cholesky”更适合大规模数据。

缺点：1、要求矩阵必须是对称正定的。

sag算法(随机平均梯度下降算法)后续待更新

优点：1、适用于处理大规模数据。

2、在岭回归模型中的求解器{'auto', 'svd ', 'cholesky', 'lsqr', 'sparse_cg', 'sag', 'saga'}中，求解速度算是比较快的了。

缺点：1、对非凸问题效果有限。

saga算法(sag算法的变体)后续待更新

介绍：每次迭代时，不仅利用当前样本的梯度，还结合了之前所有样本梯度的信息来更新模型参数。

优点：1、相比于sag算法，对于非凸问题它能有效的避免陷入局部最优解。

2、适用于处理大规模数据。

3、在岭回归模型中的求解器{'auto', 'svd ', 'cholesky', 'lsqr', 'sparse_cg', 'sag', 'saga'}中，求解速度算是比较快的了

缺点：相比于sag算法，对超参数敏感性较高。