SVD 分解，CP 分解和 Tucker 分解
date
Sep 17, 2022
Last edited time
Mar 27, 2023 08:48 AM
status
Published
slug
SVD分解，CP分解和Tucker分解
tags
Algorithm
summary
转载，张量分解的前置参考资料
type
Post
Field
Plat
1. 奇异值分解（SVD）1.1 特征值和特征向量1.2 SVD1.3 SVD 的具体应用1.3.1 压缩1.3.2 降维2. CP 分解3. Tucker 分解4. SVD 分解、Tucker 分解与 CP 分解的区别与联系参考
1. 奇异值分解（SVD）
奇异值分解 (Singular Value Decomposition，SVD) 是在机器学习领域广泛应用的算法，它不光可以用于降维算法中的特征分解，还可以用于推荐系统，以及自然语言处理等领域，是很多机器学习算法的基石。
1.1 特征值和特征向量
首先给出特征值与特征向量的定义：对矩阵 ，若有：.
其中 是一个 矩阵， 是一个 维向量，则 是矩阵 的一个特征值，而 是矩阵 的特征值 所对应的特征向量。
如何理解特征值与特征向量所代表的意义呢？
在 中，对于不同的向量 ， 这个式子像是一个函数，输入一个向量 ，则输出一个向量 。而在输入的众多向量 生成的 中， 会有这样的向量 ，它们平行于 ，我们即用上面这个式子： 来表示这个关系。
特别注意下特征值为 的情况。此时会有：。可以发现 如果是不可逆矩阵，则正好满足此性质。
我们再来谈谈如何求特征值和特征向量：
设向量 为矩阵 对应于特征值 的特征向量，即 , 则有： .
所以求解 ，就是求解 中 的非零解。其中 是单位矩阵，因此 称为 的特征多项式。
如果我们求出了矩阵 的 个特征值 ，以及这 个特征值所对应的特征向量 ，那么矩阵 就可以用下式的特征分解表示：
其中, 是这 个特征向量所张成的 维矩阵，而 为这 个特征值为主对角线的 维矩阵。
一般我们会把 的这 个特征向量标准化，即满足 ，或者 ，此时 的 个特征向量为标准正交基，满足 ，即 ，也就是说 为酉矩阵。
这样特征分解表达式可以写成：
注意：要进行特征分解，矩阵 必须为方阵。如果 不是方阵，即行和列不相同时，我们需要用 SVD。
1.2 SVD
SVD 也是对矩阵进行分解，但是和特征分解不同，SVD 并不要求要分解的矩阵为方阵。假设我们的矩阵 是一个 的矩阵，那么我们定义矩阵 的 SVD 为：
其中 是一个 的矩阵， 是一个 的矩阵，除了主对角线上的元素以外全为 ，主对角线上的每个元素都称为奇异值， 是一个 的矩阵。 和 都是酉矩阵，即满足： 。下图可以很形象的看出上面 SVD 的定义：
那么我们如何求出 SVD 分解后的 这三个矩阵呢？
如果我们将 和 做矩阵乘法，那么会得到一个方阵 。既然 是方阵，那么我们就可以进行特征分解，得到的特征值和特征向量满足下式：, 即 , 则 .
如果我们将 和 做矩阵乘法，那么会得到一个方阵 。既然 是方阵，那么我们就可以进行特征分解，得到的特征值和特征向量满足下式：, 即 , 则 .
和 我们都求出来了，现在就剩下奇异值矩阵 没有求出了.
由于 除了对角线上是奇异值其他位置都是 ，那我们只需要求出每个奇异值 就可以了。
因为：
进一步我们还可以看出我们的特征值矩阵等于奇异值矩阵的平方，也就是说特征值和奇异值满足如下关系：
这样也就是说，我们可以不用 来计算奇异值，也可以通过求出 的特征值取平方根来求奇异值。
1.3 SVD 的具体应用
1.3.1 压缩
许多存储在计算机中的数据都是以矩阵的形式存在的, 进行合理的矩阵压缩能把存储矩阵所占的空间缩减下来.。例如图像, 事实上一个灰度图像就是一个矩阵, 矩阵中的每个元素就是灰度图像的像素值。 如果我们有灰度图 , 由 我们有：
其中 要比 小很多，也就是一个大的矩阵 可以用三个小的矩阵 来表示。
奇异值 有一定的大小关系, 我们不妨设 , 取前 个分量, 则由上式可知, 若一个像素为 字节, 原始图像需 字节的存储空间, 而使用 SVD 分解后只需 字节的存储空间, 以此达到压缩图像 (矩阵) 的目的。
1.3.2 降维
数据降维在机器学习, 数据挖掘等领域是一个重要的技术, 通过数据降维可以挖掘数据的关键信息, 降低运算的成本. 使用 SVD 进行降维的核心思想是, 通过对 feature 向量 (如机器学习中的数据向量) 所组成的矩阵 进行分解, 可直接得到降维后的 feature 向量矩阵, 这其实就是 PCA(主成分分析, Principal component analysis) 的过程，具体地, 令矩阵 是若干 feature 向量 所组成的 feature 向量矩阵且矩阵 已经进行去均值处理, 则我们有：
上式即为 PCA 的求解过程, 熟悉 PCA 的同学都知道, 这个过程实际上是通过对矩阵 进行正交对角化求出投影矩阵 , 使得投影后的矩阵 各个维度相互独立, 即 为对角矩阵, 然后取方差最大的若干维以达到降维的效果. 所以我们需要对协方差矩阵 进行对角化 以求出投影矩阵 . 而现在我们可以直接对协方差矩阵进行 SVD 分解：
上式中酉矩阵 即为投影矩阵 . 由上式可得：
由上式我们可得投影后的矩阵 , 即可直接求出投影后的向量, 而无需先求得投影矩阵 再进行投影计算。而后我们便可以取方差最大的若干维, 从而达到降维的目的。
2. CP 分解
本部分来自于：浅谈张量分解（五）：稀疏张量的 CP 分解
一般而言，给定张量 ，其 CP 分解可以写成如下形式，即
其中，矩阵 被称为因子矩阵（factor matrices），符号 “” 表示张量积，对于向量而言，这里的张量积与外积是等价的。张量 任意位置 上的元素估计值为
若将该逼近问题转化为一个无约束优化问题，且目标函数为残差的平方和，即
知道了要优化的目标函数后，我们就能够通过梯度下降法训练出一个合理的分解结构。另外，对梯度下降法有所了解的读者都知道，梯度下降法的原理很简单，我们只需要掌握高等数学中的求导就可以了。
接下来，我们来看看如何对目标函数 求偏导，并给出决策变量的梯度下降更新公式元素级和矩阵化。
1. 元素级的梯度下降更新公式
将张量 𝒳 被观测到的元素相应的索引集合记为 ，前面的目标函数可以改写为
对目标函数中的决策变量 求偏导数，则我们能够很容易地得到
其中，需要特殊指出的是，求和符号下面的 分别表示矩阵 被观测到的元素其索引构成的集合。进一步，决策变量 的更新公式可以分别写成：
在这些更新公式中， 为梯度下降的学习率。
接下来，我们来看看在运算程序时更为有效的一种梯度下降更新策略，即 “矩阵化” 的梯度下降更新公式。
2. 矩阵化的梯度下降更新公式
上面给出的更新公式是以 “元素级” 的形式，熟悉 MATLAB 的读者可能也知道，这种形式的更新公式在运算相应的程序时效率是很低的，且不能发挥出 MATLAB 自身在矩阵计算方面的优势。不过，值得庆幸的是，这些更新公式都具有 “矩阵化” 的数学表达式。
定义一个与张量 大小相同的张量 ，当 时，，否则 ；再令 ，则决策变量 的更新公式分别为
其中，运算符 “” 表示点乘（element-wise multiplication），若大小均为 的张量 和 进行点乘，即 ，则 ；运算符 “” 表示 Khatri-Rao 积。
以因子矩阵 A 的更新公式为例，令梯度 ，由于
故矩阵 的第 行：
由于 ，故该矩阵的第 列为：
综上，我们可以计算出矩阵 的第 行第 列元素为：
从而，我们可以发现，上述 “矩阵级” 的更新公式表达式与 “元素级” 等价。
3. 更高阶稀疏张量的 CP 分解
给定一个大小为 的张量 ，并将其 CP 分解写成如下形式：
其中， 分别是大小为 的因子矩阵，采用梯度下降，令 ，则决策变量 的更新公式可以分别写成
到这里，我们已经介绍完了稀疏张量的 CP 分解，有兴趣的读者此时就可以设计实验了，不过，需要额外说明的是，CP 分解中的 一般表示张量的秩（tensor rank），由于对于张量的秩的求解往往是一个 NP-hard 问题，所以读者在设计实验时要预先给定 的值。
4. CP 分解：加速神经网络的方法
下图展示了使用微调的 CP 分解加速神经网络的方法。在原来的四维张量上，在每个维度上都做类似 的卷积，转化为第二行的形式，在每一个维度上都用很小的卷积核去做卷积。在空间维度上，大部分都是 的卷积，所以空间的维度很小，可以转化成第三行的形式，在输入和输出通道上做低维分解，但是在空间维度上不做分解，类似于 MobileNet。即先用 普通卷积进行降维，然后用 的 depthwise conv，最后用 的普通卷积进行升维。然而，tucker 分解用的是 的普通卷积。
3. Tucker 分解
一般来说，张量分解有各种各样的分解结构，而且对于每种结构其求解的算法也不唯一（常见的做法是采用 ALS（alternating least squares）框架），并且在实际应用中，我们需要用到的张量分解通常是用来解决稀疏张量的填补问题。由于 Tucker 分解为张量分解提供了一个优美的分解结构，下面我们来介绍如何用梯度下降方法实现稀疏张量的 Tucker 分解，为了便于理解，同时，保证大家能够很轻松地编写出张量分解的算法，这里将不会提到不必要且繁琐的数学表达式。
以第 3 阶张量为例，假设 是大小为 的张量，进行 Tucker 分解后的表达式可以写成
其中，张量 的大小为 ，也称为核心张量（core tensor），矩阵 的大小为 ，矩阵 的大小为 ，矩阵 的大小为 。这条数学表达式可能对很多只熟悉矩阵分解但却没有接触过张量分解的读者来说有点摸不着头脑，但完全不用担心，实际上，这条数学表达式等价于如下这个简洁的表达式，即
与上面逼近问题的目标函数类似，我们在这里可以很轻松地写出逼近问题的优化模型：
对目标函数 中的 、、 和 求偏导数，得
再根据梯度下降方法， 、、 和 在每次迭代过程中的更新公式为
其中，更新公式中的求和项下标 、 和 分别表示矩阵 、 和 上所有非零元素的位置索引构成的集合。至此，我们已经完成了用梯度下降来进行 Tucker 张量分解的大部分工作，有了这些更新公式，我们就可以很轻松地编写程序来对稀疏张量进行分解，并最终达到对稀疏张量中缺失数据的填补。
Tucker 分解：解决 SVD 分解中输入的通道 S 大的问题。
为了解决 SVD 分解过程中通道 S 比较大的问题，我们从另一个角度出发，沿着输入的方向对 S 做降维操作，这就是下图展示的 Tucker 分解的思想。具体操作过程是：原来的卷积，首先在 S 维度上做一个低维的表达，再做一个正常的 3×3 的卷积，最后再做一个升维的操作，即先用 1x1 普通卷积进行降维，然后再用 3x3 普通卷积（通道数是降维后的），最后用一个 1x1 普通卷积进行升维。然而，CP 分解用的是 3x3 depthwise 卷积。
4. SVD 分解、Tucker 分解与 CP 分解的区别与联系
- Tucker 分解与 CP 分解算法可以看做是张量奇异值分解的高阶扩展：CP 分解将张量分解为秩 - 张量之和，Tucker 分解是 PCA 的高阶形式。
- CP 分解可认为是 Tucker 分解的特例。
那么，如何理解 Tucker 分解与 CP 分解之间的异同呢？两种分解的数学表达式为：
- Tucker 分解：
- CP 分解：
其中，张量 𝒳 的大小为 ，在 Tucker 分解中，核心张量 的大小为 ，矩阵 的大小分别是 ；在 CP 分解中，矩阵 大小分别为 ，运算符号 “” 表示外积（outer product），如向量 ，向量 ，则 。
张量 在位置索引 上对应的元素为
- Tucker 分解：
- CP 分解：
从这两个数学表达式不难看出，CP 分解中 构成的向量替换了 Tucker 分解中 构成的核心张量，即 CP 分解是 Tucker 分解的特例，CP 分解过程相对于 Tucker 分解更为简便，但 CP 分解中 的选取会遇到很多复杂的问题，如张量的秩的求解是一个 NP-hard 问题等，这里不做深入讨论。
参考
- [^](https://zhuanlan.zhihu.com/p/490455377#ref_1_0)SVD 奇异值分解的数学涵义及其应用实例 https://zhuanlan.zhihu.com/p/57803955
- [^](https://zhuanlan.zhihu.com/p/490455377#ref_2_0) 奇异值分解（SVD） https://zhuanlan.zhihu.com/p/29846048
- [^](https://zhuanlan.zhihu.com/p/490455377#ref_3_0) 深入理解 | CP、Tucker 分解 https://zhuanlan.zhihu.com/p/302453223
- [^](https://zhuanlan.zhihu.com/p/490455377#ref_4_0) 神经网络压缩 剪枝 量化 嵌入式计算优化 NCNN mobilenet squeezenet shufflenet https://blog.csdn.net/xiaoxiaowenqiang/article/details/80946522
- [^](https://zhuanlan.zhihu.com/p/490455377#ref_5_0) 浅谈张量分解（一）：如何简单地进行张量分解？ https://zhuanlan.zhihu.com/p/24798389
- [^](https://zhuanlan.zhihu.com/p/490455377#ref_6_0) 浅谈张量分解（五）：稀疏张量的 CP 分解 https://zhuanlan.zhihu.com/p/25067269