奇异值分解（SVD）原理
奇异值分解(Singular Value Decomposition，以下简称SVD)是在机器学习领域广泛应用的算法，它不光可以用于降维算法中的特征分解，还可以用于推荐系统，以及自然语言处理等领域。本文简要讨论SVD的基本原理。
1. 特征值、特征向量的定义与应用
设A是一个n×n的矩阵，x是一个n维向量。若A,x满足Ax=λx，则我们说λ是矩阵A的一个特征值，而x是矩阵A的特征值λ所对应的特征向量。
根据一个方阵的特征值和特征向量，我们可以对其进行特征分解。如果我们求出了矩阵A的n个特征值λ1≤λ2≤...≤λn,以及这n个特征值所对应的特征向量{w1,w2,...wn}，那么矩阵A就可以用下式的特征分解表示：
其中W是这n个特征向量所组成的n×n维矩阵，而Σ是主对角线元素为这n个特征值的n×n维对角矩阵。
一般我们会把W的这n个特征向量标准化，即满足||wi||^2=1, 或者说wi'wi=1，此时W的n个特征向量为标准正交基，满足W'W=I，即W'=W−1, 也就是说W为酉矩阵。这样我们的特征分解表达式可以写成：
由于矩阵A必须为方阵，才可以进行特征分解。因此对于非方阵的矩阵而言就不能通过该方法进行特征分解，而SVD就可以解决该问题。
2. SVD的定义
SVD也是对矩阵进行分解，但是和特征分解不同，SVD并不要求要分解的矩阵为方阵。假设我们的矩阵A是一个m×n的矩阵，那么我们定义矩阵A的SVD为：
其中U是一个m×m的矩阵，Σ是一个m×n的矩阵，除了主对角线上的元素以外全为0，主对角线上的每个元素都称为奇异值，V是一个n×n的矩阵。此外，U和V都是酉矩阵，即满足U'U=I, V'V=I。那么我们如何求出SVD分解后的U,Σ,V这三个矩阵呢？
如果我们将A的转置和A做矩阵乘法，那么会得到n×n的一个方阵A'A。既然A'A是方阵，那么我们就可以进行特征分解，得到的特征值和特征向量满足下式：
这样我们就可以得到矩阵A'A的n个特征值和对应的n个特征向量v了。将A'A的所有特征向量组成一个n×n的矩阵V，就是我们SVD公式里面的V矩阵了。一般我们将V中的每个特征向量叫做A的右奇异向量。
如果我们将A和A的转置做矩阵乘法，那么会得到m×m的一个方阵AA'。既然AA'是方阵，那么我们就可以进行特征分解，得到的特征值和特征向量满足下式：
这样我们就可以得到矩阵AA'的m个特征值和对应的m个特征向量u了。将AA'的所有特征向量组成一个m×m的矩阵U，就是我们SVD公式里面的U矩阵了。一般我们将U中的每个特征向量叫做A的左奇异向量。
至此，U和V我们都求出来了，现在就剩下奇异值矩阵Σ没有求出了。由于Σ除了对角线上是奇异值其他位置都是0，那我们只需要求出每个奇异值σ就可以了。进而可以推导：
根据上式可以看出A'A的特征向量组成的的确就是我们SVD中的V矩阵。同理可证AA'的特征向量组成的就是我们SVD中的U矩阵。根据上式我们进一步可以得出，我们的特征值矩阵等于奇异值矩阵的平方，即
.
3. SVD示例
这里我们用一个简单的例子来说明矩阵是如何进行奇异值分解的。我们的矩阵A定义为：
那么计算A'A, AA'：
进一步计算A'A的特征值、特征向量：
接着求AA'的特征值和特征向量：
最后利用Avi=σiui,i=1,2求奇异值：
当然，我们也可以用V的特征值开根号直接求出奇异值。
4. SVD的性质
介绍完SVD的定义和求法，下面我们谈一谈SVD的性质。
对于奇异值,它跟我们特征分解中的特征值类似，在奇异值矩阵中也是按照从大到小排列，而且奇异值的减少特别的快，在很多情况下，前10%甚至1%的奇异值的和就占了全部的奇异值之和的99%以上的比例。也就是说，我们也可以用最大的k个的奇异值和对应的左右奇异向量来近似描述矩阵。也就是说：
其中k要比n小很多，也就是一个大的矩阵A可以用三个小的矩阵Um×k,Σk×k,V'k×n来表示。
由于这个重要的性质，SVD可以用于PCA降维，来做数据压缩和去噪。也可以用于推荐算法，将用户和喜好对应的矩阵做特征分解，进而得到隐含的用户需求来做推荐。同时也可以用于NLP中的算法，比如潜在语义索引（LSI）。
参考资料：