点击上方“小白学视觉”,选择加"星标"或“置顶”
重磅干货,第一时间送达
前言
奇异值分解(SVD)在降维,数据压缩,推荐系统等有广泛的应用,任何矩阵都可以进行奇异值分解,本文通过正交变换不改变基向量间的夹角循序渐进的推导SVD算法,以及用协方差含义去理解行降维和列降维,最后介绍了SVD的数据压缩原理 。
目录
1. 正交变换
2. 特征值分解含义
3. 奇异值分解
4. 奇异值分解例子
5. 行降维和列降维
6. 数据压缩
7. SVD总结
1.正交变换
正交变换公式:
![d4fb6dcb716ece392cf8d58d8158b9d4.png](https://img-blog.csdnimg.cn/img_convert/d4fb6dcb716ece392cf8d58d8158b9d4.png)
上式表示:X是Y的正交变换 ,其中U是正交矩阵,X和Y为列向量 。
下面用一个例子说明正交变换的含义:
假设有两个单位列向量a和b,两向量的夹角为θ,如下图:
![5374215d4342cf0026c01ab229d90ab8.png](https://img-blog.csdnimg.cn/img_convert/5374215d4342cf0026c01ab229d90ab8.png)
现对向量a,b进行正交变换:
![865ccaffed2ea141a2fbe096c2dfd994.png](https://img-blog.csdnimg.cn/img_convert/865ccaffed2ea141a2fbe096c2dfd994.png)
,
的模:
![74159520bb7b5926777062897ed20162.png](https://img-blog.csdnimg.cn/img_convert/74159520bb7b5926777062897ed20162.png)
由上式可知
和
的模都为1。
和
的内积:
![7145e3f6ef5b94b5ede3cdf4699fe7a6.png](https://img-blog.csdnimg.cn/img_convert/7145e3f6ef5b94b5ede3cdf4699fe7a6.png)
由上式可知,正交变换前后的内积相等。
和
的夹角
:
![5e6c4690946ad8eb777c0c0dde990cf7.png](https://img-blog.csdnimg.cn/img_convert/5e6c4690946ad8eb777c0c0dde990cf7.png)
比较(2)式和(3)式得:正交变换前后的夹角相等,即:![4c7c92313e9e003a8fec7a4f88e7a485.png](https://img-blog.csdnimg.cn/img_convert/4c7c92313e9e003a8fec7a4f88e7a485.png)
因此,正交变换的性质可用下图来表示:
![9a1d6b9190433aeb37a3b6a3628e1811.png](https://img-blog.csdnimg.cn/img_convert/9a1d6b9190433aeb37a3b6a3628e1811.png)
正交变换的两个重要性质:
1)正交变换不改变向量的模。
2)正交变换不改变向量的夹角。
如果向量
和
是基向量,那么正交变换的结果如下图:
![cb9de2369daef3a44af94a385f679a2f.png](https://img-blog.csdnimg.cn/img_convert/cb9de2369daef3a44af94a385f679a2f.png)
上图可以得到重要结论:基向量正交变换后的结果仍是基向量 。基向量是表示向量最简洁的方法,向量在基向量的投影就是所在基向量的坐标,我们通过这种思想去理解特征值分解和推导SVD分解。
2.特征值分解的含义
对称方阵A的特征值分解为:
![ec40564e7583182210f35fef1aba5958.png](https://img-blog.csdnimg.cn/img_convert/ec40564e7583182210f35fef1aba5958.png)
其中U是正交矩阵,
是对角矩阵。
为了可视化特征值分解,假设A是2×2的对称矩阵,
,
。(2.1)式展开为:
![fc39bcda9424a6611c84bb923f2bb7ba.png](https://img-blog.csdnimg.cn/img_convert/fc39bcda9424a6611c84bb923f2bb7ba.png)
用图形表示为:
![60a27f6a55ee3f5c8aef27c84be75076.png](https://img-blog.csdnimg.cn/img_convert/60a27f6a55ee3f5c8aef27c84be75076.png)
由上图可知,矩阵A没有旋转特征向量,它只是对特征向量进行了拉伸或缩短(取决于特征值的大小),因此,对称矩阵对其特征向量(基向量)的变换仍然是基向量(单位化) 。
特征向量和特征值的几何意义:若向量经过矩阵变换后保持方向不变,只是进行长度上的伸缩,那么该向量是矩阵的特征向量,伸缩倍数是特征值。
3.SVD分解推导
我们考虑了当基向量是对称矩阵的特征向量时,矩阵变换后仍是基向量,但是,我们在实际项目中遇到的大都是行和列不相等的矩阵,如统计每个学生的科目乘积,行数为学生个数,列数为科目数,这种形成的矩阵很难是方阵,因此SVD分解是更普遍的矩阵分解方法 。
先回顾一下正交变换的思想:基向量正交变换后的结果仍是基向量 。
我们用正交变换的思想来推导SVD分解:
假设A是M*N的矩阵,秩为K,Rank(A)=k。
存在一组正交基V:
![966d598aa2be06517858a9862fc1aa46.png](https://img-blog.csdnimg.cn/img_convert/966d598aa2be06517858a9862fc1aa46.png)
矩阵对其变换后仍是正交基,记为U:
![92e23480b608fb89588c4963c7655ca5.png](https://img-blog.csdnimg.cn/img_convert/92e23480b608fb89588c4963c7655ca5.png)
由正交基定义,得:
![f6af6a03df264121e4b6e1502faf89e3.png](https://img-blog.csdnimg.cn/img_convert/f6af6a03df264121e4b6e1502faf89e3.png)
上式展开:
![22bc3d91fe6ca49fad60be4e75a8fd24.png](https://img-blog.csdnimg.cn/img_convert/22bc3d91fe6ca49fad60be4e75a8fd24.png)
![61c30aed94b72bcf822cfd3508b0223a.png](https://img-blog.csdnimg.cn/img_convert/61c30aed94b72bcf822cfd3508b0223a.png)
![a6e5471e0c8972ef6b01d8ee26b08971.png](https://img-blog.csdnimg.cn/img_convert/a6e5471e0c8972ef6b01d8ee26b08971.png)
∴ (3.2)式得:
![df2cb416a05c78ce7ec6e0333b9d465a.png](https://img-blog.csdnimg.cn/img_convert/df2cb416a05c78ce7ec6e0333b9d465a.png)
即假设成立 。
图形表示如下:
![b4934934b6337c2f31be0d825aa4bd76.png](https://img-blog.csdnimg.cn/img_convert/b4934934b6337c2f31be0d825aa4bd76.png)
正交向量的模:
![fd2c12bdd5f7fbbe5503b16038c4b788.png](https://img-blog.csdnimg.cn/img_convert/fd2c12bdd5f7fbbe5503b16038c4b788.png)
单位化正交向量,得:
![1a744923a5e5851de952c531e50a30da.png](https://img-blog.csdnimg.cn/img_convert/1a744923a5e5851de952c531e50a30da.png)
结论:当基向量是
的特征向量时,矩阵A转换后的向量也是基向量 。
用矩阵的形式表示(3.3)式:
![94d5b62fd39d9c2104a40b1700d1f59f.png](https://img-blog.csdnimg.cn/img_convert/94d5b62fd39d9c2104a40b1700d1f59f.png)
![7e808e7ea262cde110664dd0664f541f.png](https://img-blog.csdnimg.cn/img_convert/7e808e7ea262cde110664dd0664f541f.png)
![a1c2c9cd59dca3f1c2f65fe5c08bb915.png](https://img-blog.csdnimg.cn/img_convert/a1c2c9cd59dca3f1c2f65fe5c08bb915.png)
V是N*K矩阵,U是M*K矩阵,
是M*K的矩阵,需要扩展成方阵形式:
将正交基
扩展
空间的正交基,即U是M*M方阵 。
将正交基
扩展成
空间的正交基,其中
是矩阵A的零空间,即:
![98eaf7f8c1b350640f412d18239f0f0f.png](https://img-blog.csdnimg.cn/img_convert/98eaf7f8c1b350640f412d18239f0f0f.png)
对应的特征值
=0,
是M*N对角矩阵,V是N*N方阵
因此(3.4)式写成向量形式为:
![cf0155ff6a2d5be729887aec6b0d713c.png](https://img-blog.csdnimg.cn/img_convert/cf0155ff6a2d5be729887aec6b0d713c.png)
得:
![d08db37085b1a967e1f5386fc253bccc.png](https://img-blog.csdnimg.cn/img_convert/d08db37085b1a967e1f5386fc253bccc.png)
![7fcbfac97a2823cc9759384b1459c064.png](https://img-blog.csdnimg.cn/img_convert/7fcbfac97a2823cc9759384b1459c064.png)
![9bd875e14fd4839ece217eda67a74526.png](https://img-blog.csdnimg.cn/img_convert/9bd875e14fd4839ece217eda67a74526.png)
(3.5)式写成向量形式:
![9eedc279a0366ccc2f47b4875c4f82d7.png](https://img-blog.csdnimg.cn/img_convert/9eedc279a0366ccc2f47b4875c4f82d7.png)
令:
![9c772221066f442bb592704ac066b39a.png](https://img-blog.csdnimg.cn/img_convert/9c772221066f442bb592704ac066b39a.png)
![576af2f614ad413d89cbbc2f0cdcd64d.png](https://img-blog.csdnimg.cn/img_convert/576af2f614ad413d89cbbc2f0cdcd64d.png)
则:
A = XY
因为X和Y分别是列满秩和行满秩,所以上式是A的满秩分解。
(3.5)式的奇异矩阵
的值
是
特征值的平方根,下面推导奇异值分解的U和V:
![ac8904a621c03c65c14f81880f8429a2.png](https://img-blog.csdnimg.cn/img_convert/ac8904a621c03c65c14f81880f8429a2.png)
即V是
的特征向量构成的矩阵,称为右奇异矩阵。
![b3577f52fd8013e61a437d93bdc69688.png](https://img-blog.csdnimg.cn/img_convert/b3577f52fd8013e61a437d93bdc69688.png)
即U是
的特征向量构成的矩阵,称为左奇异矩阵 。
小结:矩阵A的奇异值分解:
![020a8a565bc0aafe43ab4bd57f199b86.png](https://img-blog.csdnimg.cn/img_convert/020a8a565bc0aafe43ab4bd57f199b86.png)
其中U是
的特征向量构成的矩阵,V是
的特征向量构成的矩阵,奇异值矩阵
的值是
特征值的平方根 。
3.奇异值分解的例子
本节用一个简单的例子来说明矩阵是如何进行奇异值分解的。矩阵A定义为:
![7d88bcf309cf4741cb5f7bf7eae4ed0c.png](https://img-blog.csdnimg.cn/img_convert/7d88bcf309cf4741cb5f7bf7eae4ed0c.png)
![34b22b2cd8edb5e4274d001b14491946.png](https://img-blog.csdnimg.cn/img_convert/34b22b2cd8edb5e4274d001b14491946.png)
![0f50460286a8dadd6e699f940e63763e.png](https://img-blog.csdnimg.cn/img_convert/0f50460286a8dadd6e699f940e63763e.png)
![efd6d7768758c294e2a7015ecb53e5b4.png](https://img-blog.csdnimg.cn/img_convert/efd6d7768758c294e2a7015ecb53e5b4.png)
![8c9bcac5874c286dc0ad9628ccde00b1.png](https://img-blog.csdnimg.cn/img_convert/8c9bcac5874c286dc0ad9628ccde00b1.png)
![4abd07fd9fdf9ea921ccf355669c9835.png](https://img-blog.csdnimg.cn/img_convert/4abd07fd9fdf9ea921ccf355669c9835.png)
![5ebed42f1d2a759410f4f610ea129dab.png](https://img-blog.csdnimg.cn/img_convert/5ebed42f1d2a759410f4f610ea129dab.png)
![a64daec0093a533a863f1367ce8de170.png](https://img-blog.csdnimg.cn/img_convert/a64daec0093a533a863f1367ce8de170.png)
![751d745758344f0751222161e674c98d.png](https://img-blog.csdnimg.cn/img_convert/751d745758344f0751222161e674c98d.png)
![174f6bbdc03da4445504a85acba5a773.png](https://img-blog.csdnimg.cn/img_convert/174f6bbdc03da4445504a85acba5a773.png)
4. 行降维和列降维
4.行降维和列将维
本节通过协方差的角度去理解行降维和列降维,首先探讨下协方差的含义:
单个变量用方差描述,无偏方差公式:
![a3e6251c5f246d24ce919c1e2a368d1e.png](https://img-blog.csdnimg.cn/img_convert/a3e6251c5f246d24ce919c1e2a368d1e.png)
![0d7e9a10b80a86f144b486267dd08887.png](https://img-blog.csdnimg.cn/img_convert/0d7e9a10b80a86f144b486267dd08887.png)
两个变量用协方差描述,协方差公式:
![f7d28cf36fef26e5ec967529723e2515.png](https://img-blog.csdnimg.cn/img_convert/f7d28cf36fef26e5ec967529723e2515.png)
多个变量(如三个变量)之间的关系可以用协方差矩阵描述:
![908be191efbb7ba256b43227300851be.png](https://img-blog.csdnimg.cn/img_convert/908be191efbb7ba256b43227300851be.png)
相关系数公式:
![707449b8e8bed501c1b9b58b15bcb0f3.png](https://img-blog.csdnimg.cn/img_convert/707449b8e8bed501c1b9b58b15bcb0f3.png)
由上式可知,协方差是描述变量间的相关关系程度:
1)协方差cov(x,y) > 0时,变量x与y正相关;
2)协方差cov(x,y)<0时,变量x与y负相关;
3)协方差cov(x,y)=0时,变量x与y不相关;
变量与协方差关系的定性分析图:
![f041c87f568370e031f5082b42add1e1.png](https://img-blog.csdnimg.cn/img_convert/f041c87f568370e031f5082b42add1e1.png)
现在开始讨论
和
的含义:
假设数据集是n维的,共有m个数据,每一行表示一例数据,即:
![6d433eb947e2d60ca41bf0dce5a16b07.png](https://img-blog.csdnimg.cn/img_convert/6d433eb947e2d60ca41bf0dce5a16b07.png)
表示第i个样本,
表示第j维特征,
表示第i个样本的第j维特征 。
![9247ef202f4ca978409be18a8b7a5a57.png](https://img-blog.csdnimg.cn/img_convert/9247ef202f4ca978409be18a8b7a5a57.png)
![633d0116d8de0ceffef407cbe532fe3e.png](https://img-blog.csdnimg.cn/img_convert/633d0116d8de0ceffef407cbe532fe3e.png)
由上式可知,
是描述各特征间相关关系的矩阵,所以
的正交基V是以数据集的特征空间进行展开的。
数据集A在特征空间展开为:
![07f019c94fb50f08fcee5fe7793b06ed.png](https://img-blog.csdnimg.cn/img_convert/07f019c94fb50f08fcee5fe7793b06ed.png)
由上一篇文章可知,特征值表示了
在相应特征向量的信息分量。特征值越大,包含矩阵
的信息分量亦越大。
若我们选择前r个特征值来表示原始数据集,数据集A在特征空间展开为:
![977e088ea30a82ac1858e72bb4a4af16.png](https://img-blog.csdnimg.cn/img_convert/977e088ea30a82ac1858e72bb4a4af16.png)
(4.2)式对列进行了降维,即右奇异矩阵V可以用于列数的压缩,与PCA降维算法一致。
行降维:
![8dad6759380211f991d521b4786ec5c8.png](https://img-blog.csdnimg.cn/img_convert/8dad6759380211f991d521b4786ec5c8.png)
![4932e4343a72568e295fec04f12a0015.png](https://img-blog.csdnimg.cn/img_convert/4932e4343a72568e295fec04f12a0015.png)
由上式可知:
是描述样本数据间相关关系的矩阵,因此,左奇异矩阵U是以样本空间进行展开,原理与列降维一致,这里不详细介绍了 。
若我们选择前r个特征值来表示原始数据集,数据集A在样本空间展开为:
![19d06de5f6e689af8b4f742ffccb0249.png](https://img-blog.csdnimg.cn/img_convert/19d06de5f6e689af8b4f742ffccb0249.png)
因此,上式实现了行降维,即左奇异矩阵可以用于行数的压缩 。
5.数据压缩
本节介绍两种数据压缩方法:满秩分解和近似分解
矩阵A的秩为k,A的满秩分解:
![4855db854a6a570012a3fe4cdf4f8f5f.png](https://img-blog.csdnimg.cn/img_convert/4855db854a6a570012a3fe4cdf4f8f5f.png)
满秩分解图形如下:
![ac91e570ddfee31451cd2ff3ed6aaa3e.png](https://img-blog.csdnimg.cn/img_convert/ac91e570ddfee31451cd2ff3ed6aaa3e.png)
由上图可知,存储X和Y的矩阵比存储A矩阵占用的空间小,因此满秩分解起到了数据压缩作用。
若对数据再次进行压缩,需要用到矩阵的近似分解。
矩阵A的奇异值分解:
![0bd85927be9c6f5759783d3921602dd1.png](https://img-blog.csdnimg.cn/img_convert/0bd85927be9c6f5759783d3921602dd1.png)
若我们选择前r个特征值近似矩阵A,得:
![2c073286bed6852ca9132b9ba690e639.png](https://img-blog.csdnimg.cn/img_convert/2c073286bed6852ca9132b9ba690e639.png)
如下图:
![3c8d013d1383007d8d59fe250b317165.png](https://img-blog.csdnimg.cn/img_convert/3c8d013d1383007d8d59fe250b317165.png)
我们用灰色部分的三个小矩阵近似表示矩阵A,存储空间大大的降低了。
6.SVD总结
任何矩阵都能进行SVD分解,SVD可以用于行降维和列降维,SVD在数据压缩、推荐系统和语义分析有广泛的应用,SVD与PCA的缺点一样,分解出的矩阵解释性不强 。
参考:
https://blog.csdn.net/zhongkejingwang/article/details/43053513
https://www.cnblogs.com/pinard/p/6251584.html
下载1:OpenCV-Contrib扩展模块中文版教程
在「小白学视觉」公众号后台回复:扩展模块中文教程,即可下载全网第一份OpenCV扩展模块教程中文版,涵盖扩展模块安装、SFM算法、立体视觉、目标跟踪、生物视觉、超分辨率处理等二十多章内容。
下载2:Python视觉实战项目52讲
在「小白学视觉」公众号后台回复:Python视觉实战项目,即可下载包括图像分割、口罩检测、车道线检测、车辆计数、添加眼线、车牌识别、字符识别、情绪检测、文本内容提取、面部识别等31个视觉实战项目,助力快速学校计算机视觉。
下载3:OpenCV实战项目20讲
在「小白学视觉」公众号后台回复:OpenCV实战项目20讲,即可下载含有20个基于OpenCV实现20个实战项目,实现OpenCV学习进阶。
交流群
欢迎加入公众号读者群一起和同行交流,目前有SLAM、三维视觉、传感器、自动驾驶、计算摄影、检测、分割、识别、医学影像、GAN、算法竞赛等微信群(以后会逐渐细分),请扫描下面微信号加群,备注:”昵称+学校/公司+研究方向“,例如:”张三 + 上海交大 + 视觉SLAM“。请按照格式备注,否则不予通过。添加成功后会根据研究方向邀请进入相关微信群。请勿在群内发送广告,否则会请出群,谢谢理解~
![f948dc5dbf8ceb2de15c487750470fb7.png](https://img-blog.csdnimg.cn/img_convert/f948dc5dbf8ceb2de15c487750470fb7.png)
![f6cc1338f16db53abab1118ce2e87066.png](https://img-blog.csdnimg.cn/img_convert/f6cc1338f16db53abab1118ce2e87066.png)