在进一步学习推荐系统之前,先把奇异值分解这块的理论理清。

矩阵变换

我们知道,方阵和向量相乘,从几何意义上来讲,就是对向量作 旋转、伸缩 变换。比如下图中单位圆上不同颜色的点,在与矩阵\(\left[\begin{array}{cc} 1 & 3 \\ -3 & 2 \end{array}\right]\)相乘后,进行了相应旋转(rotating)和拉伸(stretching)变换1

再来瞅瞅三维矩阵 \(\left[ \begin{array}{ccc} 2 & -0.48 & -0.56 \\ -0.072 & 0.74 & -2 \\ 1.1 & 0.45 & -1.5 \end{array} \right]\)

特征值分解

如果方阵对某个向量只产生伸缩,而不产生旋转效果,那么这个向量就称为矩阵的特征向量,伸缩的比例就是对应的特征值

\[A\mathbf{x} = \lambda \mathbf{x}\]

学线性代数的时候,我们应该都学过这样一个定理:

若 A 为 n 阶实对称阵(方阵),则存在由特征值组成的对角阵$ $ 和特征向量组成的正交阵 Q,使得: $ A = QQ^T $

这就是我们所说的 特征值分解(Eigenvalue decomposition: EVD)\((R^n \rightarrow R^n)\),而奇异值分解其实可以看做是特征值分解在任意矩阵\((m \times n)\)上的推广形式$ (R^n R^m)$。(只有对方阵才有特征值的概念,所以对于任意的矩阵,我们引入了奇异值)


奇异值分解

上面的特征值分解的A矩阵是对称阵,可以将一组正交基映射到另一组正交基!那么现在来分析:对任意\(m \times n\)的矩阵,能否找到一组正交基使得经过它变换后还是正交基?答案是肯定的,它就是SVD分解的精髓所在。

下面我们从特征值分解出发,导出奇异值分解。

首先我们注意到 \(A^TA\) 为 n 阶对阵矩阵,我们可以对它做特征值分解。

\(A^TA = VDV^T\)

这个时候我们得到一组正交基,\(\{v_1,v_2,\cdots,v_n\}\)

\[\begin{align*}(A^TA)v_i & = \lambda_iv_i\\(Av_i,Av_j) & = (Av_i)^T(Av_j)\\& = v_i^TA^TAv_j\\& = v_i^T(\lambda_jv_j)\\& = \lambda_jv_i^Tv_j\\& = 0\end{align*} \]

\(r(A^TA)=r(A)=r\),这个时候我们得到了另一组正交基,\(\{Av_1,Av_2,\cdots,Av_r\}\)。先将其标准化,令:

\[\begin{align*}u_i & = \frac{Av_i}{\lvert Av_i \rvert} = \frac{1}{\sqrt{\lambda_i}}Av_i\\\Rightarrow Av_i & = \sqrt{\lambda_i}u_i = \delta_i u_i \end{align*}\]

注:

\[\begin{align*}\lvert Av_i \rvert^2 & = (Av_i,Av_i) = \lambda_iv_i^Tv_i = \lambda_i\\\Rightarrow \lvert Av_i \rvert & = \sqrt{\lambda_i} = \delta_i \ \ \text{(奇异值)}\end{align*} \]

将向量组 ${u_1,u_2,,u_r} $扩充为 \(R^m\)中的标准正交基 \(\{u_1,u_2,\cdots,u_r,\cdots,u_m\}\)

则:

\[\begin{align*}AV & = A(v_1 v_2 \cdots v_n) = (Av_1\ Av_2\ \cdots\ Av_r\ 0 \cdots\ 0)\\& = (\delta_1 u_1\ \delta_2 u_2\ \cdots \delta_r u_r\ 0 \cdots\ 0)\\& = U\Sigma\\\Rightarrow A &= U\Sigma V^T \end{align*}\]

这就表明任意的矩阵 A 是可以分解成三个矩阵。V 表示了原始域的标准正交基,U 表示经过 A 变换后的co-domain的标准正交基,Σ 表示了 V 中的向量与 U 中相对应向量之间的关系。