ECCV2022 中小型矩阵的批量高效(batch-efficient)特征分解

会员服务 ·

ECCV2022 中小型矩阵的批量高效(batch-efficient)特征分解

2022 年 7 月 16 日 极市平台

↑ 点击蓝字关注极市平台

作者丨LiteAI@知乎（已授权）

来源丨https://zhuanlan.zhihu.com/p/540968272

编辑丨极市平台

极市导读

今天分享一篇对于Efficient Training和边缘/移动端部署友好的关键技术——特征分解（EigenDecomposition）的文章。新算法主要解决了批处理矩阵中的ED问题，显著降低时间复杂度，对于Pytorch SVD方法取得了有竞争力的表现。 >>加入极市CV技术交流群，走在计算机视觉的最前沿

文章链接： https://arxiv.org/abs/2207.04228

项目链接： https://github.com/KingJamesSong/BatchED

概要

特征分解 (EigenDecomposition，ED) 是许多计算机视觉算法和应用程序的核心。限制其使用的一个关键瓶颈是昂贵的计算成本，特别是对于深度神经网络中的mini-batch矩阵。在本文中，我们提出了一种专用于计算机视觉应用场景的基于 QR 的 ED 方法。 我们提出的方法完全通过mini-batch矩阵/向量乘法来执行 ED，它同时处理所有矩阵，从而充分利用 GPU 的能力。我们的技术基于双Wilkinson位移的 Givens 旋转的显式 QR 迭代。通过几种加速技术，QR 迭代的时间复杂度从 O( ) 降低到 O( )。

数值测试表明，对于中小型mini-batch矩阵（例如，dim<32），我们的方法可以比 Pytorch SVD 函数快得多。视觉识别和图像生成的实验结果表明，我们的方法也取得了有竞争力的表现。

简介

特征分解 (ED) 或奇异值分解 (SVD) 将矩阵显式分解为特征值和特征向量矩阵，这是计算机视觉和深度学习的基本工具。最近，许多算法将 SVD 作为元层集成到他们的模型中，以执行期望的频谱变换 [34、33、31、5、23、9、45、24、8、13、47、46、38]。应用全局协方差池化 [31、44、38]、去相关批量归一化 (BN) [23、45、24、39]、Perspective-n-Points (PnP) 问题 [5、8、13] 和Whitening和Ciloring变换 (WCT) [32, 9, 47]是不同的。

ED在计算机视觉中的问题设置与其他领域有很大不同。在科学计算等其他社区中，很少出现mini-batch矩阵，而 ED 通常用于处理单个矩阵。然而，在深度学习和计算机视觉中，模型将mini-batch矩阵作为输入，这提高了对有效处理mini-batch矩阵的 ED 求解器的要求。此外，可微分 ED 作为构建块工作，需要在训练和推理期间处理数百万次mini-batch矩阵。这对 ED 求解器的效率提出了巨大挑战，甚至可能由于大量时间消耗而阻碍人们在模型中添加 ED 元层（见图 1）。

在当前的深度学习框架中，例如 Pytorch [37] 或 TensorFlow [1]，ED 求解器主要采用线性代数库（例如 LAPACK [3] 和 Intel MKL [43]）中的 SVD 实现。这些求解器可以有效地处理单个矩阵，但不能很好地支持 GPU 上的批处理矩阵。大多数实现都基于分治 (Divide-and-Conquer, DC) 算法 [11, 21]。该算法将一个矩阵划分为多个小的子矩阵，并对每个子矩阵同时执行 ED。借助并行和分布式计算的强大功能，其速度仅受矩阵维度的轻微影响，并且对于单个矩阵来说可以非常快。DC 算法的核心是特征多项式 det(λI−A)=0，可以通过各种方法求解，例如secular方程 [21] 和spectral division [35]。然而，求解多项式需要同时定位每个单独矩阵的所有特征值区间。尽管单个矩阵的效率很高，但这些 DC 算法不能扩展到批处理矩阵。

除了 DC 算法，一些 ED 求解器会使用 QR 迭代。QR 迭代有许多实现方法，一个特定的batch高效选择是通过 Givens 旋转。Givens 旋转可以通过矩阵-矩阵乘法来实现，这自然会扩展到批处理矩阵。在 QR 迭代期间，连续应用 Givens 旋转以消除非对角线entries，直到矩阵变为对角线。限制 QR 迭代使用的主要缺点是 O( ) 时间成本，这使得该方法仅适用于微小矩阵（例如，dim<9）。为了缓解这个问题，现代基于 QR 的 ED 实现应用了deflation技术 [2, 6, 7]，即将矩阵划分为许多子矩阵。deflation技术可以大大提高 QR 迭代的速度，但仅适用于单个矩阵。对于 QR 迭代，收敛速度与相邻特征值比有关。对于 mini-batch 中的多个矩阵，每个矩阵的非对角线元素收敛到零，速度不一致，每个矩阵可以划分的位置不同。因此，deflation技术也不适用于批处理矩阵。举一个具体的例子，在一个batch中考虑 2 个大小为 8×8 的矩阵。假设deflation会将一个矩阵分成两个 3×3 和 5×5 矩阵，而另一个矩阵可能会分成两个 4×4 矩阵。在这种情况下，由于矩阵大小不一致，分区矩阵不能作为小批量有效地处理。

为了获得一种批处理友好且 GPU 高效的 ED 方法，专门用在视觉领域，我们提出了一种基于 QR 的 ED 算法，该算法通过mini-batch矩阵/向量乘法执行 ED。ED 算法的每一步都经过仔细考虑，以实现最佳的批处理效率和计算成本。我们首先执行一系列批处理 Householder reflector，通过批处理矩阵向量乘法对矩阵进行三对角化。之后，通过矩阵旋转和双Wilkinson位移 [48] 进行显式 QR 迭代，以对矩阵进行对角化。所提出的移位使批处理矩阵的最后两个对角线entries具有一致的收敛速度。因此，收敛速度加快，矩阵维数可以在 QR 迭代期间逐渐缩小。

除了降维，我们还提出了一些基于复杂度分析的经济计算方法。QR 的时间复杂度因此从 O( ) 降低到 O( )。数值测试表明，对于维度小于 24 的矩阵，我们的 Pytorch 实现始终比任何批处理的默认 SVD routine快得多。对于较大尺寸的矩阵（例如，dim=32 或 36），当批量大小相应较大时，我们的方法也可能具有优势（见图 1）。我们验证了我们的方法在可微 SVD 的几个应用中的有效性，包括去相关 BN、视觉Transformer的协方差池化和神经风格迁移。我们的批处理 ED 实现了与 SVD 有竞争力的性能。

本文的贡献总结为三方面：

我们提出了一种用于batch中中小型矩阵的 ED 算法，该算法专用于计算机视觉的许多应用场景。ED 的每一步都经过精心设计，旨在实现最佳batch效率。
我们为我们的批量 ED 算法提出了专门的加速技术。在迭代过程中，提出了渐进式维度收缩来减小矩阵大小，同时还开发了一些基于复杂性分析的经济计算方法。
我们的批处理高效 ED 算法在可微分 SVD 的多个应用中得到验证。视觉识别和图像生成实验表明，我们的方法与封装在当前深度学习平台中的 SVD 相比，具有非常有竞争力的性能。

方法论

在本节中，我们将介绍执行批处理 ED 的方法。我们的算法是通过顺序批处理 Householder 反射器来实现矩阵的三对角化和批处理 QR 迭代来对角化三对角矩阵。这两个过程都是 GPU 友好和批处理高效的。现在我们详细说明每个过程。请注意，每个步骤都应用于批处理矩阵以获得最佳效率。

1. 基于Householder反射的批量三对角化

给定Hermitian矩阵A，三对角化过程定义为：

其中T是三对角矩阵，P是正交矩阵。为了执行这样的正交相似变换，我们可以将 P 分解为 n-2 个 Householder 反射器。这有重新表示：

每个反射器都是正交的 ( =I) 和unitary(H= )。反射器是使用向量构造的：

矩阵 H 沿垂直于与 u 正交的超平面的方向反映向量 u。此属性可用于通过顺序反映每一行和每一列来对对称矩阵进行三对角化。Householder 反射通过以下方式计算：

其中临时变量 q、p 和 K 定义为：

可以看出，等式 (4) 实际上在 A 上定义了一个对称的 rank-2 更新。通过对等式（4）的一些推论，每个 Householder 反射器可以设计为在一行和一列中引入零entries（见图 2）。为简洁起见，我们省略了向量的推导，并在此处给出结果：

其中表示 A 在第 i 行第 j 列的entry，通常 σ 表示 sign( ) 以减少舍入误差。通过这种结构，只需 n-2 次反射即可将对称矩阵转换为三对角化形式。每个householder反射需要 2 次矩阵-矩阵乘法，这需要 O(2 ) 复杂度。然而，如等式 (4) 和等式 (5)所示，计算可以简化为一次矩阵-矩阵乘法和两次矩阵-向量乘法，需要O( +2 )的复杂度。

当需要特征向量时，我们可以通过累加 Householder 反射器来计算 P：

计算需要 (n-2) 个矩阵乘法，其中每次乘法的复杂度为 O( )。我们注意到这一步可以通过以下方式进一步加速：

依靠这个定理，我们可以划分积累Hn...H4H3 成(n-2)/m 个子序列并并行计算它们。每个子序列需要 O((m-1) +(n-2)m) 时间来计算 WY 表示，并且需要 O( m) 时间来计算 I-2W 。合并所有子序列需要额外的时间 O( /m）。这可以进一步降低计算 P 的复杂度O((n-3) ) 到 O((m-1) +(n-2)m+ m+ /m)。当 n 很大时，计算开销节省会很大。

2. 基于 QR 迭代的批量对角化

在获得三对角矩阵 T 后，我们使用 Givens 旋转来执行 QR 迭代，这可以通过批量矩阵乘法高效地实现。在普通 QR 迭代的基础上，我们进一步应用了几种技术来加速收敛并节省计算预算。

Givens 旋转的基本 QR 迭代

给定三对角矩阵 T，QR 迭代采用以下迭代更新：

其中表示正交矩阵，是上三角矩阵。用替换使得重新表示等式 (8) :

可以看出，单次 QR 迭代等效于执行正交相似度变换。通过执行迭代，次对角线和超对角线元素逐渐减少，直到矩阵变为对角线。对于每次 QR 迭代，我们使用 Givens 旋转从左上角移动到右下角逐渐构造正交变换。2×2 Givens 旋转及其 n×n 扩展定义为：

其中 θ 是旋转角度，旋转矩阵是正交的但不是对称的（即 R=I 和 R）。如图 3 所示，通过旋转角度的设计，在 T 上应用连续 Givens 旋转可以保持三对角形式但减少非对角元素的大小。沿对角线移动的顺序 Givens 旋转形成一次 QR 迭代：

其中表示从左上角开始的第 i 次旋转。对于第 i 次 QR 迭代中的正交矩阵，我们可以很容易地发现

将 Householder 三对角化和 Givens 对角化结合在一起，我们的批量高效 ED 算法可以正式定义为：

其中k是QR迭代的迭代次数，Λ是特征值矩阵，P ... 是特征向量矩阵。对于收敛，我们有：

这个定理研究的主要结果是收敛速度取决于相邻特征值比，对于 i>j。QR 迭代通常需要 2n 次迭代才能得到矩阵对角线结果[16]。考虑每次迭代都需要 (n−1) 个 Givens 旋转的事实，计算开销将是巨大的。为了推导特征值，我们需要 4n(n-1) 次，而计算特征向量需要 2n(n-2) +(2n-1) 的复杂度。

QR 迭代的时间复杂度是矩阵维数 n 的五倍，这将使该方法仅适用于微小矩阵 (<9)。现有的用于加速计算的deflation技术 [6, 7] 不能应用于我们的批处理矩阵。为了解决这个问题，我们提出了以下技术：

双Wilkinson移位

如定理 2 所示，QR 迭代的收敛速度取决于比率，其中 i>j。一种自然的加速计算收敛方法是将矩阵移动 T−µI 使得收敛速度变成。一个优选的移位系数应该是 u= ，因为这可以帮助矩阵快速收敛： =∞。这对于batch中的矩阵，因为可以通过移位使速度保持一致。

由于每个 Givens 旋转都会影响前一个旋转的区域，只有最后的 2×2 Givens 旋转不会受到影响，即可以局部估计最后一个块的两个特征值。因此，我们建议从右下角的 2×2 块中提取移位系数：

其中 [n-2:n] 表示的最后一个 2×2 块，和是从该块计算的两个特征值。这些移位系数被称为Wilkinson移位[48]。获得移位后，我们可以用双移位重新构造 QR 迭代：

伴随着移位，积分迭代由两个连续的 QR 迭代组成，分别偏移了特征值和。

渐进式维度收缩

Wilkinson 移位带来的一个直接好处是，对于 batch 中的所有矩阵，最后两个对角线元素可以快速收敛到相应的特征值，并且非对角线元素可以收敛到零：

我们可以利用这一性质通过逐渐减小矩阵维数来加快计算速度，即在一次迭代后将矩阵缩小 T∈ →T∈ 。如图 4 所示，当最后一个子对角线entries低于给定的小阈值（例如，1e-5）时，我们可以通过删除最后一行和最后一列来缩小矩阵。这样做时，矩阵大小在 QR 迭代期间逐渐减小。通过降维，一次 QR 迭代将需要 (n−1−r) 个 Givens 旋转，其中 r 是降维次数。

经济特征值计算

对于 Givens 旋转，它只影响相邻的 4×4 块。我们可以通过在邻域的 4×4 旋转区域上应用矩阵乘法来节省计算预算。这将旋转的时间从 O(2 ) 减少到 O(2× )=O(128)，这使得每次旋转消耗恒定的时间成本。考虑到上述降维，QR 迭代需要 O(256n(n−1−r)) 时间来导出特征值。

经济特征向量计算

配备渐进式降维，QR 迭代中的正交变换定义为：

每次迭代都需要 (n−2−r) 次旋转。下面定理可以潜在地简化计算：

这个定理意味着，不需要显式 QR 迭代，正交变换 Q 和变换矩阵 B 都可以隐式计算。但是，它假定 B 的子对角线元素为正。在我们的例子中，Givens 旋转可以轻松地将最后两个子对角线entries归零。因此，直接使用该定理会导致较大的舍入误差和数据溢出。虽然这个定理不能直接应用，但它允许我们简化特征向量计算。如定理所示，第 i 次旋转只会影响第 i 行和第 i 列之后区域上的正交矩阵 Q。我们可以通过只涉及矩阵的一部分来减少计算，并简化等式(17) 中的计算如：

其中 [i:] 表示排除前 i 行和列的矩阵部分。通过这样做，计算的时间复杂度可以降低到：

与原始时间成本 O((n-2-r) ) 相比，对于较大的 n 和 r，节省的开销是可观的。

3. 计算复杂度总结

表 1 总结了基于 QR 的基本 ED 求解器和我们提出的专用于批处理矩阵的 ED 求解器的时间复杂度。采用最高阶项进行更简单的分析，我们的 ED 求解器将计算特征值的时间从 O(4 ) 减少到 O( )，并将计算特征向量的时间从 O(2 ) 减少到 O( ) 。此外，根据减少时间 r，复杂性可以进一步降低，特征值使用 -256(1+r)n 项，特征向量使用 -(2r+1) 项。

表1 基于QR的ED求解器和我们的ED求解器对于batch矩阵的时间复杂度比较。

4. 收敛和误差界限

对于三对角化过程，使用 n-2 个 Householder 反射器保证收敛。误差只与机器精度和数据精度有关，可以充分忽略。对于 QR 迭代，收敛主要取决于相邻特征值比和位移。在某些情况下，当两个特征值接近时（ ≈1)，收敛速度很慢，剩余项成为误差。另一个误差来自降维的容差 ϵ。让 ¯Λ 表示精确的特征值，Λ 表示我们的 ED 求解器计算的特征值。那么错误的范围是：

其中是由 =LU 计算的 L 的entry，并且移位 µ 每次 QR 迭代都会改变。由于 Q 是正交的，所以的大小通常非常小。考虑到的幅度很小和额外的移位技术，我们的方法的准确性不会受到影响。

实验

在本节中，我们首先执行一个数值测试，将我们的方法与 SVD 对不同维度和批量大小的矩阵进行比较。随后，我们评估了所提出的方法在三种计算机视觉应用中的有效性：去相关 BN、二阶视觉Transformer和神经风格迁移。

1. 数值测试

图 5 描述了我们的批处理 ED 针对不同矩阵尺寸和批量大小的 SVD 的计算时间。SVD 的时间成本几乎随着批量大小线性增长，而我们的批量 ED 的时间消耗对于不同的批量大小只有轻微的变化。对于维度小于 24 的矩阵，我们的批处理 ED 对于任何批量大小都始终比 SVD 快。当矩阵维度为 32 时，我们的方法比批量大小为 256 的 SVD 更快。 我们的批处理 ED 的速度对于较小的矩阵尺寸和较大的批量大小更有利。

图5 batch ED和TORCH.SVD对于不同batch大小和矩阵维度的速度比较。

2. 去相关BN

继[39]之后，我们首先对ZCA白化任务进行了实验。在白化过程中，协方差的反平方根乘以特征以消除各个维度之间的相关性。我们将 ZCA 白化元层插入 ResNet-18 [22] 架构，并评估 CIFAR10 和 CIFAR100 [28] 上的验证误差。表 2 比较了我们的批处理 ED 与 SVD 的性能。根据组的数量，我们的方法可以比 SVD 快 2 倍、10 倍甚至 28 倍。此外，我们的方法在 CIFAR10 上的所有指标上都优于 SVD。使用 CIFAR100，性能也相当。

3. 二阶视觉Transformer

我们转向关于二阶视觉Transformer (So-ViT) [49] 的全局协方差池化任务的实验。为了利用嵌入在视觉tokens中的丰富语义，视觉tokens的协方差平方根用于辅助分类任务。由于全局协方差矩阵通常是非常病态的 [38]，这项任务对 ED 算法的稳定性提出了巨大挑战。我们选择了不同深度的 So-ViT 架构，并在 ImageNet [14] 上验证了性能。从表 3 中可以看出，我们的批处理 ED 具有与标准 SVD 有竞争力的性能。此外，对于不同大小的协方差，我们的方法比 SVD 快 44% 和 27%。

4. 通用风格迁移

现在我们在 WCT 中应用我们的批量 ED 进行神经风格迁移。给定内容特征和风格特征，WCT 逐步执行白化和着色迁移目标风格。我们按照 [32, 47] 使用 LPIPS 距离和用户偏好作为评估指标。

表4 Artworks数据集上迁移图像和内容图像和用户偏好（%）之间的LPIPS距离。

表 4 给出了与不同组的定量比较。我们的批处理 ED 实现了极具竞争力的性能并在速度上占主导地位。举一个具体的例子，当组数为 64 时，我们的方法比默认的 SVD 快大约 35 倍。

图 6 显示了视觉比较示例。在这个特定示例中，我们的批处理 ED 生成的图像具有更好的视觉吸引力。

与 [9] 中的发现类似，我们还观察到组的数量影响风格迁移的程度。如图 7 所示，当使用更多组时，迁移图像中的风格变得更加可区分，细节也得到了更好的保留。由于组的数量决定了划分通道的数量和协方差大小，因此更多的组对应于较小的协方差，这可能有助于更好地捕获局部结构。尽管有这种表面的猜想，但给出更全面、更严谨的分析还是值得进一步研究的。

总而言之，我们的 ED 求解器展示了卓越的批处理效率，适用于各种实际实验和数值测试中的小矩阵。对大矩阵的限制表明了关键区别：我们的方法更加batch-efficient，而 torch.eig/svd 更加dimension-efficient。

公众号后台回复“项目实践”获取50+CV项目实践机会～

△点击卡片关注极市平台，获取最新CV干货