We Recommend a Singular Value Decomposition

我们推荐奇异值分解

奇异值分解可以方便地把一个矩阵（包含我们感兴趣的数据）分解得更加简单和有意义。 本文讲解了奇异值分解的几何解释，顺便也介绍了一些应用。

From http://www.ams.org/samplings/feature-column/fcarc-svd

David Austin，Grand ValleyState University

介绍

  本文的主题是奇异值分解(singular value decomposition，SVD)，它应该是数学系研究生标准课程的一部分，但是经常被忽略。除了十分直观，此类分解(decomposition)还极其有用。比如，Netflix，一在线电影租赁公司，为改进他们的推荐系统设立了100万美元奖金，要求是准确度(accuracy)提高10%。 令人惊讶的是，这个看起来很普通的问题，实际上十分具有挑战性。参与的团队正在使用十分复杂的技术。这些技术的核心便是奇异值分解。

  奇异值分解可以方便地把一个矩阵（包含我们感兴趣的数据）分解得更加简单和有意义。 本文讲解了奇异值分解的几何解释，顺便也介绍了一些应用。

线性转换的几何学解释

让我们先看一些简单的2x2的矩阵。第一个例子是如下对角矩阵(diagonal matad-images.jianshu.io/upload_images/10000468-3f74806ef09d3c2c?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

从几何学角度，我们可以把类似矩阵看作是一种转换：在平面上取一点(x, y)，然后通过矩阵相乘，把此点转换到另外一点:

image

此转换效果是：平面在水平方向伸展了3倍，垂直方向无变化。

image

现在我们再看矩阵

image

它产生以下效果：

image

此转换看上去不像前面的简单明了。但是让我们把网格(grid，http://mathworld.wolfram.com/Grid.html)旋转45度，看看会发生什么情况。

image

啊哈。我们发现这个新网格的转换与第一张图的网格转换一样：乘以一个对角矩阵，网格在某个方向上拉伸了3倍。

因为矩阵M是对称的，即M的转置(transpose，沿着对角翻转)等于M，所以这只是一类特殊的情况。如果我们有一2x2的对称矩阵，通常会产生以下转换效果：先在domain中旋转网格，然后在两个方向上拉伸(stretch)或者反射(reflect)。换句话讲，对称矩阵的行为像对角矩阵（除了旋转）。

说得更数学化些：给定一对称矩阵M, 我们可能会找到一由正交向量(orthogonal vector) v_i 组成的集合，M*****v_i是v_i的标量倍(scalarmultiple)，也就是说

M****v_i = λ_iv**_i

其中λ_i 是一标量。

从几何角度来说，这意味着当向量v_i乘以M后，它被简单的拉伸(stretch)或者反射(reflect)了。

正因为这个特性，我把向量v_i 称为矩阵M的特征向量（eigenvector）；标量λ_i 称为特征值(eigenvalue)。一个容易验证的重要的事实是：对称矩阵的特征向量（带不同特征值）是正交的。

如果用对称矩阵的特征向量按放(align)网格，这个矩阵会再拉伸(stretch)或者反射(reflect)这个（被旋转后的）网格，如同它对自己的特征向量一样。

这个线性转换的几何描述属于简单的一类：网格只是在某个方向被拉伸了。对于更加普通的矩阵，我们会问这么一个问题：我们能否找到一个正交网格（两组线相互垂直的），能转换到另外一个正交网格。让我们看最后一个例子，它使用一非对称矩阵：

image

这个矩阵产生一个称为 “修剪”（shear）的几何效果。

image

沿着水平轴，容易找到一组特征向量。但是，上面的图片显示这些特征向量不能用于创建正交的网格（能转换到另外一个正交网格），虽然如此，我们还是先看一下我们旋转这个网格30度会发生什么。

image

注意由平行四边形构成的位于坐标原点的夹角在右边增加了。让我们把网格旋转60度。

image

嗯。右边的网格看上去是正交的了。实际上，通过在domain中旋转网格大约58.28度，两个网格就全是正交的了。

image

奇异值分解(Singular Value Decomposition)

这就是SVD在2x2矩阵下的几何学本质：对于任意的2x2矩阵，我们能找到一个正交的网格(grid)，它被转换到了另外一个正交网格。

我们使用向量来描述这个现象：如果我们通过某种方式挑出两个单位向量（unit vector）v₁和v₂，它们是正交的，向量Mv₁ 和Mv₂ 也是正交的。

image

我们用u₁和u₂代表向量Mv₁ 和Mv₂ 方向的单位向量，用σ₁ andσ₂代表向量Mv₁ 和Mv₂的长度，它们描述网格在这些方向上的拉伸量。这些数字称为M的奇异值(singularvalue，在这个例子里，奇异值是golden ratio 和它的reciprocal,但是在这里不重要)。

image

因此我们有

Mv₁ = σ₁u₁

Mv₂ = σ₂u₂

现在我们可简单说一下矩阵M是如何处理普通向量x的。因为单位向量v₁和v₂是正交的（译者注：形成了一规范正交基，****orthonomal basis），所以我们有：

x = (v₁∙x)v1 + (v2∙x)v2

（译者注：x ∙v1 = (v1∙x) v1∙v1 + (v2∙x)v2∙v1 = (v1∙x) 1+0 = v1∙x=x*∙v1）

这意味着

Mx = (v₁∙x)M****v₁ + (v₂∙x)Mv**₂

Mx = (v₁∙x)σ₁u1+ (v₂∙x)σ₂u₂

记住dot product 操作可以用矩阵转置实现：

v∙x = v^Tx

从而导出

Mx = u₁σ₁v₁^Tx +u₂σ₂v₂^Tx**

M = u₁σ₁v₁^T +u₂σ₂v₂^T**

上述表达式可以简写成

M = UΣV^T

其中U 是由向量u₁ 和u₂（作为列）组成的矩阵,Σ 是对角矩阵，对角线上的值是σ₁ 和σ₂,V 是向量v₁和v₂(作为列)组成的矩阵. 矩阵V的上标T 代表V的矩阵转置。

上面显示了如何将矩阵M分解为三矩阵的积: V描述在domain中的规范正交基（orthonomal basis），U描述co-domain中的规范正交基，Σ描述在V中的向量在U中拉伸量。

译者注：

1. 如果把每个矩阵看作一种转换动作，可以描述为：先旋转，然后拉伸展，然后再一次旋转。

2．所以SVD的Idea是：如果我们在向量空间Rⁿ 和R^m上选择正确的基(basis)，每个mxn矩阵均可对角线化(diagonalized)。计算的问题就是如何找到这些basis。

如何作奇异值分解？

奇异值分解的强大之处在于适用于任何矩阵。那我们是如何做到呢？让我们回顾前面的一个例子，在domain中加上一个单位圆。在co-domain中它将是椭圆，它的长轴(major axis)和短轴(minoraxis) 定义了在co-domain中的正交网格。

image

注意长轴短轴分别由Mv₁和Mv₂定义。因此这两个向量是单位圆上向量（在椭圆上的）最长和最短的向量。

image

换句话讲，单位圆上的函数|Mx| 在x=v₁时有最大值，x=v₂有最小值。这把问题降低到一个十分标准的微积分问题：我们希望在单位圆上优化一个函数。可以证明函数的临界点在矩阵M^TM的特征向量上。因此这个矩阵是对称的，对应于不同的特征值的特征向量将是正交的。这就产生了一组向量v_i。

奇异值定义为σ_i = |Mv_i|, 向量u_i则是Mv_i方向上的单位向量。但是为什么这些u_i是正交的呢？

要解释这个，我们假设σ_i and σ_j 是两个不同的奇异值。于是有

Mv_i = σ_iu_i

Mv_j = σ_ju_j

让我们先看表达式Mv_i∙Mv_j。 为了方便先假设它们的奇异值是非零的。另外一方面，v_i和v_j是对称矩阵M^TM的特征向量，它们是相互正交的，结果是这个表达式等于零。

Mv_i∙Mv_j =v_i^TM^TMv_j = v_i∙M^TMv_j =v_i∙λ_jv_j = λ_jv_i∙v_j =0.**

另外一方面，我们有

Mv_i∙Mv_j =σ_iσ_ju_i∙u_j =0**

因此u_i和u_j是正交的。到此为止，我们发现了一组正交向量v_i，它能转换为另外一组正交向量u_i。(v_i对应的)奇异值描述了在不同方向上的拉伸程度。

在实际应用中，这不是为矩阵寻找奇异值分解的过程，因为这种方法效率不高，或者说数值计算上是低效的。

另外一个例子

让我们看一矩阵：

image

这个矩阵在几何上的效果如下图：

image

| | | |

在这种情况下，第二个奇异值是0，因此我们写成

M = u₁σ₁v₁^T**.

（译者注：M = u1σ1 v1^T+ u2σ2 v2^T）

换句话讲，如果其中的一些奇异值是0，对应的项就不出现在M的分解中。这样，我们发现M的rank（矩阵秩，它等于线性转换后的维度）就等于非0奇异值的数量。

数据压缩

奇异值分解能让数据表示更加有效。例如，我们想传输以下图片，含15x25个黑或白的像素点。

image

因为图片中只有三种列，就像下图显示的，也许我们能用更加紧凑的形式。

image

我们用0代表黑色，1代表白色，用一个15x25的矩阵表示这个图像。如此一来，便有了375个元素的矩阵：

image

如果我们对上述M作奇异值分解，会发现只有三个非0的奇异值

σ₁ = 14.72
σ₂ = 5.22
σ₃ = 3.31

因此，矩阵可表示为：

M=u₁σ₁v₁^T +u₂σ₂v₂^T + u₃σ₃v₃^T

这意味着我们有：三个向量v_i，每个有15 个元素；三个向量u_i，每个有25个元素；三个奇异值σ_i。这意味着我们能只用123个数字代表矩阵（153+253+3=123），而不是375个。就这样奇异值分解帮助我们发现了矩阵中存在的冗余，并提供了剔除它们的方法。

为什么只有三个非零的奇异值呢？前面讲过，非0奇异值的数量等于矩阵的rank。在这个例子中，矩阵只有三个线性独立的列，也就是它的rank=3。

降噪

前面的例子显示我们是如何利用“很多奇异值是0”来解决问题的。通常大的奇异值对应着有趣信息多的所在。比如，设想我们用一个扫描仪把这个图像输入到电脑。但是，扫描仪在图像中引入了一些非理想的数据（通常称为“噪音”）。

image

与前面的例子一样我们用15x25的矩阵表示数据，然后进行奇异值分解。可发现以下奇异值

*** σ***₁ = 14.15
σ₂= 4.67
σ₃= 3.00
σ₄= 0.21
σ₅= 0.19
...
σ₁₅= 0.05

显然，前三个是最重要的（最大），我们可以假设其他小的奇异值是噪音造成的，所以近似表示矩阵如下

M u₁σ₁v₁^T +u₂σ₂v₂^T+u₃σ₃v₃^T

这导致了以下改进的图像。

image

数据分析

在收集数据的时候会遇到噪音数据：无论如何好的器材，测量经常会有误差。因为大的奇异值(singular values)对应了矩阵中的重要特性。因此一旦数据收集完成，便自然可用SVD来研究。

例如，我们收集了以下数据

image

我们可能会把这些数据放到一个矩阵中

-1.03 0.74 -0.02 0.51 -1.31 0.99 0.69 -0.12 -0.72 1.11

-2.23 1.61 -0.02 0.88 -2.39 2.02 1.62 -0.35 -1.67 2.46

然后运行SVD，我们发现如下奇异值

σ₁ = 6.04

σ₂ = 0.22

其中一个奇异值如此之大，可以安全地假设小的σ₂ 是由于数据噪音引起的，这个奇异值在理想情况下应该是0。在这则案例中，矩阵的rank 等于1，意味着所有数据应该在向量u_i定义的这条线上。

image

这个简单的例子说出了PCA（principal component analysis）起源，它是一组使用奇异值剔除数据中依赖和冗余的技术。

同样，SVD可用于检测数据中的存在的分组(group)。这就可以解释，为什么SVD正用于改进netflix的电影推荐系统。系统会根据你的电影评分（观看过的），把你分到某个组中，组内人员的评分与你的相似，然后系统就向你推荐组内其他人评分高的电影。

参考文献

• Gilbert Strang, Linear Algebra and Its Applications. Brooks Cole.

  Strang's book is something of a classic though some may find it to be a little too formal.

• William H. Press et al, Numercial Recipes in C: The Art of Scientific Computing. Cambridge University Press.

  Authoritative, yet highly readable. Older versions are available online.

• Dan Kalman, A Singularly Valuable Decomposition: The SVD of a Matrix, The College Mathematics Journal27 (1996), 2-23.

  Kalman's article, like this one, aims to improve the profile of the singular value decomposition. It also a description of how least-squares computations are facilitated by the decomposition.

• If You Liked This, You're Sure to Love That,The New York Times, November 21, 2008.

  This article describes Netflix's prize competition as well as some of the challenges associated with it.