ICCV 2021 | UCLA提出：基于张量CUR的快速鲁棒张量主成分分析算法

本文是对发表于国际计算机视觉大会ICCV的Workshop论文“Fast Robust Tensor Principal Component Analysis via Fiber CUR Decomposition” [1] 的介绍。

该论文由UCLA大学数学系 HanQin Cai, Zehan Chao, Longxiu Huang, and Deanna Needell 共同完成。

论文arXiv链接：https://arxiv.org/abs/2108.10448

我们的研究主要是关于鲁棒张量主成分分析的算法，也可以称做鲁棒张量分解算法。与传统的高维奇异值分解算法(HOSVD)不同，我们的算法是基于【张量CUR分解】和【交替映射法】衍生出的关于张量分解的一套算法。解决同样的张量问题有非常大的时间复杂度优势，同时也不会受限于被稀疏离群值 (sparse outlier)破坏的数据。我们通过大量的模拟数据实验与真实数据实验来验证了算法的可行性与鲁棒性。

主成分分析（PCA）是一种基础的数学分析方法，为对多变量数据进行降维以便更好的分析及可视化。矩阵数据的PCA通常与矩阵分解密切相关，例如一种常见的PCA问题定义为获得矩阵的低秩趋近：

这个问题可以通过矩阵的截断奇异值分解（truncated SVD）来完成。

传统的PCA存在一些公认的缺点，例如对于离群值非常敏感，少数几个离群值会完全扰乱算法的输出。因此在这之上一些研究转向了鲁棒主成分分析 (Robust PCA、RPCA)。RPCA在PCA的基础上增加了对于稀疏离群值的容忍度：

此处，额外的稀疏矩阵S吸收原数据D的离群值，从而使得输出结果L更加鲁棒。

张量（Tensor）是比矩阵更广义的结构，可以看作多维度版本的矩阵；同样，矩阵可以定义为二维的张量。在各种关于数据科学的研究中，张量被认为可以比矩阵更好地保存原数据的结构，从而产生了各类对张量的研究。其中，张量的鲁棒主成分分析，即鲁棒分解问题，就是我们算法处理的主要问题。即：

注意，张量的秩存在多种不同的定义。在此文中，我们着重研究张量的多线性秩(multilinear rank)，也称为塔克秩 (Tucker rank)。

最初的CUR分解属于矩阵分解的一种，与LU分解，SVD分解类似：

其中，C指的是原矩阵提取的列，R指的是原矩阵提取的行，U 是 C和R的交叉部分。CUR分解总是成立的当U的秩等于A的秩（详细内容可参考论文[2]）。

将这个概念拓展到高维张量里，我们就有了张量版本的CUR分解（张量CUR有Chidori CUR和 Fiber CUR两个版本，本文使用Fiber CUR。详细内容可参考论文[3]）

在此之上，结合交替映射算法的概念，我们开发了称之为鲁棒张量CUR (Robust Tensor CUR、RTCUR)的算法：

其中，第5行的resample是可以在每个迭代中进行也可以始终统一，进而演化成了两种算法，RTCUR-R与RTCUR-F。这两种算法的区别在于，Resample的算法(RTCUR-R)在处理更密的离群值数据时比Fixed index算法(RTCUR-F)要稳定一些，但RTCUR-F算法因为每次迭代中不用重新选择张量中的数据，在运行时间上稍有优势，以及RTCUR-F只需要取原张量中非常小的一部分数据，从而对数据缺失有更高的容忍度。

首先，我们研究RTCUR算法的采样系数（Sampling Constant）与离群值密度的相变图。我们生成固定秩的三维张量，然后加入不同密度的离群值，运行不同采样系数RTCUR算法进行检测。从而根据RTCUR算法是否可以准确恢复原低秩张量L来画出如下相变图：

从相变图中可以看到，在采样系数取在3~5之间时，我们可以获得较高的离群值容忍度同时保持算法的较快运行。

接着，我们生成了不同尺寸的低秩三维张量和随机稀疏离群值来测试各种算法的运行时间与结果准确性。实验结果发现，基本所有的算法对于 20%的离群值都可以准确地分离出低秩部分与稀疏离群值部分。从时间对比图上也可以看到处理张量鲁棒分解问题时，RTCUR拥有巨大的时间优势：

我们又测试了不同的真实数据集，其中一项任务是彩色视频的背景分离。比如在一段行人走在街上的视频，彩色的低秩背景街道可以视为张量， 而移动中的行人则可视为离群值。通过几段不同的视频测试，我们的RTCUR算法都可以获得很好的分离效果：

当然，不同算法的效果略有差异，但总体都成功的分离了背景与前景。在这之上，RTCUR算法对于真实数据同样有明显的时间优势（见Table 1）。

本文针对张量鲁棒主成分分析问题提出了一个基于张量CUR的快速算法。从模拟数据和真实数据来看，我们的算法在准确有效的同时极大地提升了速度。我们未来会在算法的理论方面探讨一些思路和可能性。

期刊扩展版会很快推出，欢迎大家关注我们后续的工作。      

雷锋网雷锋网雷锋网