奇异值分解(SVD)

奇异值分解(SVD)是一种矩阵因子分解方法。任意一个m*n的矩阵，都可以表示为三个矩阵的乘积(因子分解)的形式，分别是m阶正交矩阵、由降序排列的非负的对角线元素组成的m*n矩阵和n阶正交矩阵，称为该矩阵的奇异值分解。矩阵的奇异值分解一定存在，但不唯一。奇异值分解可以看作出矩阵数据压缩的一种方法。即用因子分解的方式近似地表示原始矩阵，这种矩阵在平方损失意义下的最优近似。

一、奇异值分解的定义与性质

矩阵的奇异值分解是指，将一个非零的m*n实矩阵 $A$ ，表示为以下三个实矩阵乘积形式的运算，即进行矩阵的因子分解
$A =U\Sigma V^T$
其中U是m阶正交矩阵，V是n阶正交矩阵， $\Sigma$ 是由降序排列的非负的对角元素组成的 $m\*n$ 的矩形对角矩阵
$\begin{aligned} UU^T = I \\ VV^r=T = I \\ \Sigma = diag(\sigma_1,\sigma_2,\dots,\sigma_p) \\ \sigma_1 \ge \sigma_2 \ge \dots \ge \sigma_p \ge 0 \\ p = min(m,n) \end{aligned}$
$U\Sigma V^T$ 称为矩阵的奇异值分解， $\sigma_i$ 称为矩阵A的奇异值, $U$ 的列向量称为左奇异向量， $V$ 的列向量成为右奇异向量

(1)紧奇异值分解与截断奇异值分解

紧凑奇异值分解是与原始矩阵等秩的奇异值分解，截断奇异值分解是比原始矩阵降低秩的奇异值分解。在实际应用中，常常需要对矩阵的数据进行压缩，将其近似表示，奇异值分解提供了一种方法。奇异值分解是在平方损失意义下对矩阵的最优近似。紧奇异值分解对应着无损压缩，截断奇异值分解对应着有损压缩

(a)紧奇异值分解

设有 $m*n$ 实矩阵A，其秩为rank(A) = r, $r \le min(m,n)$ ，则称 $U_r\Sigma_rV_r^T$ 为A的紧奇异值分解，即
$A = U_r\Sigma_rV_r^T$
其中 $U_r$ 是 $m*r$ 矩阵， $V_r$ 是 $n*r$ 矩阵， $\Sigma_r$ 是r阶对角矩阵，矩阵 $U_r$ 由完全奇异分解中的前r列，矩阵 $V_r$ 由V的前r列，矩阵 $\Sigma_r$ 由 $\Sigma$ 的前r个对角线元素得到，紧奇分解的对角矩阵 $\Sigma_r$ 的秩与原始矩阵A的秩相等

(b)截断奇异值分解

在矩阵的奇异值分解中，只取最大的k个奇异值(k < r,r为矩阵的秩）对应的部分，就得到矩阵的截断奇异值分解。实际应用中提到的矩阵的奇异值分解，通常指截断奇异值分解

设A为 $m*n$ 实矩阵，其秩rank(A)=r,且， $0 < k < r$ ，则称 $U_k\Sigma_kV_k^T$ 为矩阵A的截断奇异值分解
$A \approx U_k\Sigma_kV_k^T$
其中 $U_k$ 是 $m*k$ 矩阵， $V_k$ 是n*k矩阵， $\Sigma_k$ 是k阶对角矩阵；矩阵 $U_K$ 由完全奇异分解U的前k列，矩阵 $V_k$ 由V的前k列，矩阵 $\Sigma_k$ 由 $\Sigma$ 的前k个对角线元素得到。对角矩阵 $\Sigma_k$ 的秩比原始矩阵A的秩低。

(2)几何解释

从线性变换的角度理解奇异值分解， $m*n$ 矩阵A表示从n维空间 $R^n$ 到m空间 $R^m$ 的一个线性变换，
$T:x \to Ax$
x和Ax分别表示各自空间的向量。线性变换可以分解为三个简单的变换：一个坐标系的旋转或反射变换、一个坐标轴的缩放变换、另一个坐标系的旋转或反射。

对矩阵A进行奇异值分解，得到 $A=U\Sigma V^T$ ,V和U都是正交矩阵，所以V的列向量 $v_1,v_2,\dots,v_n$ 构成空间的一组标准正交基，表示 $R^n$ 中的正交坐标系的旋转或反射；U的列向量 $u_1,u_2,\dots,u_n$ 构成 $R^m$ 空间的一组标准正交基，表示 $R^m$ 中正交坐标系的旋转或反射； $\Sigma$ 的对角元素 $\sigma_1,\sigma_2,\dots,\sigma_n$ 是一组非负实数，表示 $R^n$ 中原始正坐标系坐标轴的 $\sigma_1,\sigma_2,\dots,\sigma_n$ 倍的缩放变换。

任意一个向量 $x \in R^n$ ，经过基于 $A=U\Sigma V^T$ 的线性变换，等价于经过坐标系的旋转或反射变换 $V^T$ ，坐标轴的缩放变换 $\Sigma$ ，以及坐标轴的旋转或反射变换U,得到相框 $Ax \in R^m$

二、奇异值分解的方法

（1）确定 $V$ 和 $\Sigma$

矩阵A是 $m*n$ 的正交实矩阵，则矩阵 $A^TA$ 是n阶实对称矩阵，因而 $A^TA$ 的特征值都是实数，并且存在一个n阶正实矩阵V实现 $A^TA$ 的对角化，使得 $V^T (A^TA)V = \Lambda$ 成立，其中 $\Lambda$ 是n阶对角矩阵，其对角元素由 $A^TA$ 的特征值组成。

而且， $A^TA$ 的特征值都是非负的。事实上，令 $\lambda$ 是 $A^TA$ 的一个特征值，x是对应的特征向量，则
$\|Ax\|^2 = x^TA^TAx=\lambda x^Tx =\lambda \|x\|^2$
于是
$\lambda = \frac{\|Ax\|^2}{\|x\|^2} \ge 0$
可以假设正交矩阵V的列排列使得对应的特征值形成降序排列。
$\lambda_1 \ge \lambda_2 \ge \dots \ge \lambda_n \ge 0$
计算特征值的平方根(实际上解释矩阵A的奇异值)
$\sigma_j = \sqrt{\lambda_j},j=1,2,\dots,n$
设矩阵A的秩是r,rank(A)=r,则矩阵 $A^TA$ 的秩也是r。由于 $A^TA$ 是对称矩阵，它的秩等于正的特征值的个数。

$\lambda_1 \ge \lambda_2 \ge \dots \ge \lambda_r \ge 0 ，\lambda_{r+1}=\lambda_{r+2}=\dots,\lambda_n=0$
对应的
$\sigma_1 \ge \sigma_2 \ge \dots \ge \sigma_r \ge 0 ,\sigma_{r+1}=\sigma_{r+2}=\sigma_n=0$
令
$V_1 =[v_2,v_2,\dots,v_r],v_2=[v_{r+1},v_{r+2},\dots,v_n]$
其中 $v_2,\dots,v_r$ 为 $A^TA$ 的特征值对应的特征向量， $v_{r+1},\dots,v_n$ 为0特征值对应的特征向量。
则
$V=[V_1,V_2]$

这就是矩阵A的奇异值分解中的n阶正交矩阵V

令
$\Sigma_1 = \begin{bmatrix} \sigma_1 &\space &\space &\space \\[0.3em] \space & \sigma_2 & \space &\space\\[0.3em] \space&\space& \ddots \\[0.3em] \space & \space & \space &\sigma_r \end{bmatrix}$
则 $\Sigma_1$ 是个一个r阶对角矩阵，其对角线元素为按降序排列的正的 $\sigma_1,\dots,\sigma_r$ ，于是 $m*n$ 矩形对角矩阵 $\Sigma$ 可以表示为
$\Sigma = \begin{bmatrix} \Sigma_1 & 0 \\[0.3em] 0 & 0 \end{bmatrix}$
这就是矩阵A的奇异值分解中的 $m*n$ 矩阵对角矩阵 $\Sigma$

（2）确定U

接着构造m阶正交实矩阵U
令
$\begin{aligned} u_j = \frac{1}{\sigma_i}Av_j,j=1,2,\dots,r \\ U_1 = [u_1,u_2,\dots,u_r] \end{aligned}$
则有
$AV_1 = U_1\Sigma_1$
$U_1$ 的列向量构成正交基是因为
$\begin{aligned} u_i^T u_j =\bigg (\frac{1}{\sigma_i}v_i ^T A^T\bigg )\bigg(\frac{1}{\sigma_j}AV_j\bigg) \\ = \frac{1}{\sigma_i\sigma_j}v_i^T (A^T AV_j) \\ = \frac{\sigma_j}{\sigma_i}v_i^T v_j \\ =\delta_{ij},i=1,2\dots,r;j=1,2,\dots,r \end{aligned}$
对 $A^T$ 的非零空间的一组标准正交基 $\{u_{r+1},u_{r+2},\dots,u_m\}$ ，令
$U_2 = [u_{r+1},u_{r+2},\dots,u_m]$
并令
$U=[U_1,U_2]$

(3)得到奇异值分解

$A=U\Sigma V^T$

(4)证明 $U\Sigma V^T=A$

$\begin{aligned} U\Sigma V^T = [U_1,U_2] \begin{bmatrix} \Sigma_1 & 0 \\[0.3em] 0 & 0 \end{bmatrix} \begin{bmatrix} V_1^T \\[0.3em] V_2^T \end{bmatrix} \end{aligned} \\ =U_1\Sigma_1V_1^T \\ =AV_1V_1^T$

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 203,271评论 5赞 476
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 85,275评论 2赞 380
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 150,151评论 0赞 336
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,550评论 1赞 273
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,553评论 5赞 365
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,559评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 37,924评论 3赞 395
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,580评论 0赞 257
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 40,826评论 1赞 297
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,578评论 2赞 320
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,661评论 1赞 329
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,363评论 4赞 318
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 38,940评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,926评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,156评论 1赞 259
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 42,872评论 2赞 349
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,391评论 2赞 342

奇异值分解(SVD)

奇异值分解(SVD)

一、奇异值分解的定义与性质

(1)紧奇异值分解与截断奇异值分解

(a)紧奇异值分解

(b)截断奇异值分解

(2)几何解释

二、奇异值分解的方法

（1）确定和

（2）确定U

(3)得到奇异值分解

(4)证明

推荐阅读更多精彩内容

（1）确定 $V$ 和 $\Sigma$

(4)证明 $U\Sigma V^T=A$