【张量｜TRPCA】Tensor Robust Principal Component Analysis with A New Tensor Nuclear Norm

支持我的工作 🎉

📃亲爱的朋友们，感谢你们一直以来对我的关注和支持！
💪🏻 为了提供更优质的内容和更有趣的创作，我付出了大量的时间和精力。如果你觉得我的内容对你有帮助或带来了欢乐，欢迎你通过打赏支持我的工作！

🫰🏻你的一份打赏不仅是对我工作的认可，更是对我持续创作的巨大动力。无论金额多少，每一份支持都让我倍感鼓舞和感激。

📝有关此篇文章的更多详情请见：论文精读，给我一杯咖啡的支持吧！☕️

🔥再次感谢你们的支持和陪伴！

TRPCA 代码分析与实验结果

动机+相关工作+实验

具有新的张量核范数的张量鲁棒主成分分析

初步分析

摘要

本文研究了张量鲁棒主成分分析（TRPCA）问题，目标是精确恢复低秩和稀疏成分。本文基于最近提出的 t-product，严格推导了张量谱范数、张量核范数和张量平均秩，并证明了张量核范数是张量平均秩在张量谱范数单位球内的凸包。利用这些新定义，作者提出了一种凸优化方案解决TRPCA问题，并提供了精确恢复的理论保证。数值实验验证了理论结果，并在图像恢复和背景建模问题中展示了方法的有效性。

动机

• PCA（主成分分析）是数据分析的基础方法，但对大幅度噪声和异常值较为敏感。
• 为此，鲁棒PCA（RPCA）被提出，用以处理矩阵的低秩和稀疏分解。
• 然而，RPCA只能处理二维数据（矩阵），而实际数据通常是多维的（张量），例如彩色图像和视频。将RPCA扩展到张量数据，可以避免信息损失和性能下降。
• 因此，本文动机是将RPCA扩展到张量数据，利用其多维结构实现更高效的数据分解。

贡献

1. 新张量核范数的定义：提出了一个新的张量核范数及相关张量概念，严格推导了这些定义及其关系，确保其与矩阵情况一致。
2. 精确恢复保证：理论证明在一定条件下，凸 TRPCA 模型能够精确恢复低秩和稀疏成分。RPCA的理论保证成为本文的特例。
3. t-SVD 分解和优化方法：提供了t-SVD分解的新证明和更高效的TRPCA求解方法，并通过数值实验验证了这些方法的有效性。

方法

1. 张量-张量积（t-product）：作为张量运算的基础，定义了t-product及相关的张量范数，包括张量谱范数和张量核范数。
2. 凸优化方案：提出了TRPCA问题的凸优化模型，使用新定义的张量核范数和稀疏约束，通过求解凸优化问题实现低秩和稀疏成分的分解。
3. 数值实验：通过合成数据和实际数据（如图像和视频）的数值实验，验证了TRPCA模型在恢复精度和计算效率上的优越性。

实验

数值实验部分主要包括：

1. 合成数据实验：在合成数据上验证 TRPCA 模型的恢复精度和理论结果的一致性。
2. 图像恢复实验：在图像恢复问题中，比较了 TRPCA 和传统 RPCA 的效果，展示了 TRPCA 在处理多维数据上的优势。
3. 背景建模实验：在视频背景建模问题中，证明了 TRPCA 模型的实用性和有效性。

数学模型

关键概念和定义

1. 张量-张量乘积（t-product）：

   • 是矩阵-矩阵乘积在张量中的推广。

   • 对于张量 $\mathbf{A}\in {\mathbb{R}}^{n_1\times n_2\times n_3}$ 和 $\mathbf{B}\in {\mathbb{R}}^{n_2\times l\times n_3}$ ，t-product 定义为：

     $$\mathbf{A}\ast \mathbf{B}=\text{fold}(\text{bcirc}(\mathbf{A})\cdot \text{unfold}(\mathbf{B}))$$

   • 这种操作保持了数据的多维结构。

2. 张量奇异值分解（t-SVD）：

   • 扩展了奇异值分解（SVD）的概念到张量。

   • 对于张量 $\mathbf{A}$ ，t-SVD 表示为：

     $$\mathbf{A}=\mathbf{U}\ast \mathbf{S}\ast {\mathbf{V}}^{\ast }$$

   • 这里， $\mathbf{U}$ 和 $\mathbf{V}$ 是正交张量， $\mathbf{S}$ 是一个对角张量。

3. 张量核范数（TNN）：

   • 定义为张量 t-SVD 的奇异值之和。

   • 对于张量 $\mathbf{A}$ ：

     $$\Vert \mathbf{A}{\Vert }_{\ast }=\sum _{i=1}^{r}S(i,i,1)$$

   • 论文证明了这种范数是在张量谱范数单位球内的张量平均秩的凸包。

TRPCA模型

TRPCA 模型旨在将一个张量 $\mathbf{X}$ 分解为低秩张量 $\mathbf{L}$ 和稀疏张量 $\mathbf{E}$ ：

$$\mathbf{X}=\mathbf{L}+\mathbf{E}$$

为了实现这种分解，需要解决以下凸优化问题：

$$\underset{\mathbf{L},\mathbf{E}}{\min }\Vert \mathbf{L}{\Vert }_{\ast }+\lambda \Vert \mathbf{E}{\Vert }_1\text{s.t}\mathbf{X}=\mathbf{L}+\mathbf{E}$$

其中：

• $\Vert \mathbf{L}{\Vert }_{\ast }$ 是 $\mathbf{L}$ 的张量核范数。
• $\Vert \mathbf{E}{\Vert }_1$ 是稀疏张量 $\mathbf{E}$ 的 ${\ell }_1$-范数。
• $\lambda$ 是平衡两个项的参数。

提出的算法

Algorithm 1 Tensor-Tensor Product

这个算法描述了如何计算两个三维张量的乘积。具体步骤如下：

1. 输入:
   • $\mathbf{A}\in {\mathbb{R}}^{n_1\times n_2\times n_3}$
   • $\mathbf{B}\in {\mathbb{R}}^{n_2\times l\times n_3}$
   • 目标是计算 $\mathbf{C}=\mathbf{A}\ast \mathbf{B}\in {\mathbb{R}}^{n_1\times l\times n_3}$
2. 步骤:

   1. 计算张量的傅里叶变换:

      • 计算张量 $\mathbf{A}$ 和 $\mathbf{B}$ 在第三维度上的傅里叶变换：

        $$\bar{\mathbf{A}}=\text{fft}(\mathbf{A},[],3)\text{and}\bar{\mathbf{B}}=\text{fft}(\mathbf{B},[],3)$$

   2. 计算张量 $\mathbf{C}$ 的每个正面切片:

      • 对每个正面切片 ${\bar{\mathbf{C}}}^{(i)}$ 执行以下操作：

        $${\bar{\mathbf{C}}}^{(i)}=\{\begin{array}{ll}{\bar{\mathbf{A}}}^{(i)}{\bar{\mathbf{B}}}^{(i)},& i=1,\dots ,\lceil \frac{n_3+1}{2}\rceil \\ \text{conj}({\bar{\mathbf{C}}}^{(n_3-i+2)}),& i=\lceil \frac{n_3+1}{2}\rceil +1,\dots ,n_3\end{array}$$

   3. 计算逆傅里叶变换:

      • 计算 $\mathbf{C}$ 的逆傅里叶变换以得到最终结果：

        $$\mathbf{C}=\text{ifft}(\bar{\mathbf{C}},[],3)$$

解释

1. 傅里叶变换：傅里叶变换将张量从时域转换到频域，使得在频域中的乘法操作更加简便和高效。
2. 正面切片计算：算法通过处理张量的正面切片来执行乘法。这些切片是傅里叶变换后的张量表示。
3. 复共轭：在频域中，某些切片是通过取另一个切片的复共轭来获得的，以保证计算的对称性和正确性。
4. 逆傅里叶变换：最终结果通过逆傅里叶变换从频域转换回时域，得到最终的张量乘积结果。

Algorithm 2 T-SVD

这个算法描述了如何对一个三维张量进行奇异值分解。具体步骤如下：

1. 输入:
   • $\mathbf{A}\in {\mathbb{R}}^{n_1\times n_2\times n_3}$
   • 目标是计算 $\mathbf{A}$ 的 $T-SVD$ 组件： $\mathbf{U},\mathbf{S},\mathbf{V}$
2. 步骤:

   1. 计算张量的傅里叶变换:

      • 计算张量 $\mathbf{A}$ 在第三维度上的傅里叶变换：

        $$\bar{\mathbf{A}}=\text{fft}(\mathbf{A},[],3)$$

   2. 计算 $\bar{\mathbf{A}}$ 的每个正面切片的 SVD:

      • 对每个正面切片 ${\bar{\mathbf{A}}}^{(i)}$ 执行以下操作：

        $$[{\bar{\mathbf{U}}}^{(i)},{\bar{\mathbf{S}}}^{(i)},{\bar{\mathbf{V}}}^{(i)}]=\text{SVD}({\bar{\mathbf{A}}}^{(i)})$$

      • 其中， $i=1,\dots ,\lceil \frac{n_3+1}{2}\rceil$

      • 对于剩余的切片，执行以下操作：

        ${\bar{\mathbf{U}}}^{(i)}=\text{conj}({\bar{\mathbf{U}}}^{(n_3-i+2)})$

        ${\bar{\mathbf{S}}}^{(i)}={\bar{\mathbf{S}}}^{(n_3-i+2)}$

        ${\bar{\mathbf{V}}}^{(i)}=\text{conj}({\bar{\mathbf{V}}}^{(n_3-i+2)})$

      • 其中， $i=\lceil \frac{n_3+1}{2}\rceil +1,\dots ,n_3$

   3. 计算逆傅里叶变换:

      • 计算 $\mathbf{U},\mathbf{S},\mathbf{V}$ 的逆傅里叶变换，以得到最终结果：

        $\mathbf{U}=\text{ifft}(\bar{\mathbf{U}},[],3)$

        $\mathbf{S}=\text{ifft}(\bar{\mathbf{S}},[],3)$

        $\mathbf{V}=\text{ifft}(\bar{\mathbf{V}},[],3)$

解释

1. 傅里叶变换：傅里叶变换将张量从时域转换到频域，使得在频域中的计算更加简便和高效。
2. SVD计算：在频域中，对每个正面切片进行奇异值分解（SVD）。对于前一半的切片，直接进行SVD计算；对于后一半的切片，通过前一半的复共轭和对称性来确定。
3. 复共轭：在频域中，通过取另一个切片的复共轭来获得剩余的切片，以保证计算的对称性和正确性。
4. 逆傅里叶变换：最终结果通过逆傅里叶变换从频域转换回时域，得到最终的张量奇异值分解结果。

Algorithm 3 Tensor Singular Value Thresholding (t-SVT)

这个算法描述了如何对一个三维张量进行奇异值阈值化处理。具体步骤如下：

1. 输入:
   • $\mathbf{Y}\in {\mathbb{R}}^{n_1\times n_2\times n_3}$
   • 一个阈值 $\tau >0$
   • 目标是计算张量 $\mathbf{Y}$ 的奇异值阈值化结果 ${\mathcal{D}}_{\tau }(\mathbf{Y})$
2. 步骤:

   1. 计算张量的傅里叶变换:

      • 计算张量 $\mathbf{Y}$ 在第三维度上的傅里叶变换：

        $$\bar{\mathbf{Y}}=\text{fft}(\mathbf{Y},[],3)$$

   2. 对每个正面切片进行矩阵奇异值阈值化（SVT)：【就是消除噪声的过程】

      • 对每个正面切片 ${\bar{\mathbf{Y}}}^{(i)}$ 执行以下操作：

        $$[\mathbf{U},\mathbf{S},\mathbf{V}]=\text{SVD}({\bar{\mathbf{Y}}}^{(i)})$$

        $${\bar{\mathbf{W}}}^{(i)}=\mathbf{U}\cdot (\mathbf{S}-\tau {)}_{+}\cdot {\mathbf{V}}^{\ast }$$

        • 其中 $(\mathbf{S}-\tau {)}_{+}$ 表示对 $\mathbf{S}$ 中的每个奇异值减去阈值 $\tau$ ，并将负值置零。

      • 对于剩余的切片，执行以下操作：

        $${\bar{\mathbf{W}}}^{(i)}=\text{conj}({\bar{\mathbf{W}}}^{(n_3-i+2)})$$

      • 其中， $i=1,\dots ,\lceil \frac{n_3+1}{2}\rceil$ 和 $i=\lceil \frac{n_3+1}{2}\rceil +1,\dots ,n_3$

   3. 计算逆傅里叶变换:

      • 计算 ${\mathcal{D}}_{\tau }(\mathbf{Y})$ 的逆傅里叶变换以得到最终结果：

        $${\mathcal{D}}_{\tau }(\mathbf{Y})=\text{ifft}(\bar{\mathbf{W}},[],3)$$

解释

1. 傅里叶变换：傅里叶变换将张量从时域转换到频域，使得在频域中的计算更加简便和高效。
2. 奇异值阈值化：在频域中，对每个正面切片进行奇异值分解（SVD）。然后，对奇异值进行阈值化处理，即减去阈值 $\tau$ 并将负值置零。
3. 复共轭：对于后半部分的切片，通过前一半的复共轭和对称性来确定，以保证计算的对称性和正确性。
4. 逆傅里叶变换：最终结果通过逆傅里叶变换从频域转换回时域，得到最终的张量奇异值阈值化结果。

Algorithm 4 Solve (5) by ADMM

这个算法描述了如何使用 ADMM（交替方向乘子法）来求解以下优化问题：

$$\underset{\mathbf{L},\mathbf{E}}{\min }\Vert \mathbf{L}{\Vert }_{\ast }+\lambda \Vert \mathbf{E}{\Vert }_1\text{st}\mathbf{X}=\mathbf{L}+\mathbf{E}$$

初始化

在进入迭代过程之前，首先需要初始化一些变量和参数：

• ${\mathbf{L}}_0={\mathbf{S}}_0={\mathbf{Y}}_0=0$ ：所有变量初始化为零。
• $\rho =1.1$ ：一个固定的参数，用于更新乘子。
• ${\mu }_0=1e-3$ ：初始的乘子参数。
• ${\mu }_{\max }=1e10$ ：乘子参数的上限。
• $ϵ=1e-8$ ：收敛条件的阈值。

迭代过程

算法通过一个循环不断更新变量，直到满足收敛条件。具体步骤如下：

1. 更新 ${\mathbf{L}}_{k+1}$ ：

   $${\mathbf{L}}_{k+1}=\arg \underset{\mathbf{L}}{\min }\Vert \mathbf{L}{\Vert }_{\ast }+\frac{{\mu }_k}{2}{\Vert \mathbf{L}+{\mathbf{E}}_k-\mathbf{X}+\frac{{\mathbf{Y}}_k}{{\mu }_k}\Vert }_F^2$$

   这一步是通过最小化核范数（即矩阵的奇异值之和）和 Frobenius 范数（即矩阵元素平方和的平方根）的组合来更新 $\mathbf{L}$。可以想象成在优化一个带有惩罚项的矩阵，使其更符合我们的数据结构。

2. 更新 ${\mathbf{E}}_{k+1}$ ：

   $${\mathbf{E}}_{k+1}=\arg \underset{\mathbf{E}}{\min }\lambda \Vert \mathbf{E}{\Vert }_1+\frac{{\mu }_k}{2}{\Vert {\mathbf{L}}_{k+1}+\mathbf{E}-\mathbf{X}+\frac{{\mathbf{Y}}_k}{{\mu }_k}\Vert }_F^2$$

   这一步是通过最小化 $\mathbf{E}$ 的 ${\ell }_1$ 范数（即矩阵元素的绝对值之和）和Frobenius范数的组合来更新 $\mathbf{E}$。可以想象成在寻找一个稀疏矩阵 $\mathbf{E}$，使其与 ${\mathbf{L}}_{k+1}$ 和 $\mathbf{X}$ 的差异最小。

3. 更新 ${\mathbf{Y}}_{k+1}$ ：

   $${\mathbf{Y}}_{k+1}={\mathbf{Y}}_k+{\mu }_k({\mathbf{L}}_{k+1}+{\mathbf{E}}_{k+1}-\mathbf{X})$$

   这一步是更新乘子 $\mathbf{Y}$ 的值。可以想象成一种累积误差的调整，使得 $\mathbf{L}$ 和 $\mathbf{E}$ 更接近于 $\mathbf{X}$。

4. 更新 ${\mu }_{k+1}$ ：

   $${\mu }_{k+1}=\min (\rho {\mu }_k,{\mu }_{\max })$$

   这一步是更新惩罚参数 $\mu$，逐步增加其值，使得优化过程更快收敛。

5. 检查收敛条件：

   $$\Vert {\mathbf{L}}_{k+1}-{\mathbf{L}}_k{\Vert }_{\infty }\le ϵ,\Vert {\mathbf{E}}_{k+1}-{\mathbf{E}}_k{\Vert }_{\infty }\le ϵ,\Vert {\mathbf{L}}_{k+1}+{\mathbf{E}}_{k+1}-\mathbf{X}{\Vert }_{\infty }\le ϵ$$

   如果所有这些条件都满足，则算法收敛，循环结束。

• ADMM 算法

  在交替方向乘子法（ADMM）中，我们通过增广拉格朗日函数来处理约束优化问题。我们从以下增广拉格朗日函数开始：

  $$L(\mathbf{L},\mathbf{E},\mathbf{Y})=\Vert \mathbf{L}{\Vert }_{\ast }+\lambda \Vert \mathbf{E}{\Vert }_1+⟨\mathbf{Y},\mathbf{X}-\mathbf{L}-\mathbf{E}⟩+\frac{\mu }{2}\Vert \mathbf{X}-\mathbf{L}-\mathbf{E}{\Vert }_F^2$$

  分解拉格朗日乘子项：

  $$⟨\mathbf{Y},\mathbf{X}-\mathbf{L}-\mathbf{E}⟩={\mathbf{Y}}^T(\mathbf{X}-\mathbf{L}-\mathbf{E})$$

  分解增广项：

  $$\frac{\mu }{2}\Vert \mathbf{X}-\mathbf{L}-\mathbf{E}{\Vert }_F^2=\frac{\mu }{2}(\mathbf{X}-\mathbf{L}-\mathbf{E}{)}^T(\mathbf{X}-\mathbf{L}-\mathbf{E})$$

  $$\Rightarrow \frac{\mu }{2}(\Vert \mathbf{X}{\Vert }_F^2-2{\mathbf{X}}^T(\mathbf{L}+\mathbf{E})+\Vert \mathbf{L}+\mathbf{E}{\Vert }_F^2)$$

  结合项：

  $$\begin{array}{rlr}L(\mathbf{L},\mathbf{E},\mathbf{Y})=& \Vert \mathbf{L}{\Vert }_{\ast }+\lambda \Vert \mathbf{E}{\Vert }_1+{\mathbf{Y}}^T\mathbf{X}-{\mathbf{Y}}^T\mathbf{L}-{\mathbf{Y}}^T\mathbf{E}& +\frac{\mu }{2}(\Vert \mathbf{X}{\Vert }_F^2-2{\mathbf{X}}^T(\mathbf{L}+\mathbf{E})+\Vert \mathbf{L}+\mathbf{E}{\Vert }_F^2)\end{array}$$

  提取常数项：

  ${\mathbf{Y}}^T\mathbf{X}$ 和 $\frac{\mu }{2}\Vert \mathbf{X}{\Vert }_F^2$ 是常数项，因为它们不依赖于 $\mathbf{L}$ 和 $\mathbf{E}$。所以将这些常数项分离出来，只关注那些与 $\mathbf{L}$ 和 $\mathbf{E}$ 相关的项：

  $$\begin{array}{rlr}L(\mathbf{L},\mathbf{E},\mathbf{Y})=& \Vert \mathbf{L}{\Vert }_{\ast }+\frac{\mu }{2}\Vert \mathbf{L}{\Vert }_F^2+\frac{\mu }{2}\Vert \mathbf{E}{\Vert }_F^2& +(\mu \mathbf{E}-\mathbf{Y}-\mu \mathbf{X}{)}^T\mathbf{L}+\text{常数项}\end{array}$$

  $$\Rightarrow L(\mathbf{L},\mathbf{E},\mathbf{Y})=\Vert \mathbf{L}{\Vert }_{\ast }+\frac{\mu }{2}\Vert \mathbf{L}{\Vert }_F^2+{\left(\mathbf{E}-\mathbf{X}+\frac{\mathbf{Y}}{\mu }\right)}^T\mu \mathbf{L}+\text{常数项}$$

  $$
  \Rightarrow L(\mathbf{L}, \mathbf{E}, \mathbf{Y}) = |\mathbf{L}|_* + \frac{\mu}{2} |\mathbf{L}|_F^2 +

  \frac{\mu}{2}{(\mathbf{E}^T - \mathbf{X}^T + \frac{\mathbf{Y}^T}{\mu}})*2\mathbf{L}
  $$

  $$
  \Rightarrow L(\mathbf{L}, \mathbf{E}, \mathbf{Y}) = |\mathbf{L}|_* + \frac{\mu}{2} |\mathbf{L}|_F^2 +

  \frac{\mu}{2}{(2\mathbf{E}^T\mathbf{L} - 2\mathbf{X}^T\mathbf{L} + 2\frac{\mathbf{Y}^T }{\mu}}\mathbf{L})
  $$

  $$
  \Rightarrow L(\mathbf{L}, \mathbf{E}, \mathbf{Y}) = |\mathbf{L}|_* + \frac{\mu}{2}
  (

  |\mathbf{L}|_F^2 + {2\mathbf{E}^T\mathbf{L} - 2\mathbf{X}^T\mathbf{L} + 2\frac{\mathbf{Y}^T }{\mu}}\mathbf{L})
  $$

  $$
  \Rightarrow L(\mathbf{L}, \mathbf{E}, \mathbf{Y}) = |\mathbf{L}|_* + \frac{\mu}{2}
  (
  |\mathbf{L}|_F^2 +

  2(\mathbf{E} - \mathbf{X} + \frac{\mathbf{Y}}{\mu})\mathbf{L}^T+

  | \mathbf{E} - \mathbf{X} + \frac{\mathbf{Y}}{\mu} |_F^2

  • | \mathbf{E} - \mathbf{X} + \frac{\mathbf{Y}}{\mu} |_F^2
    )
    $$

  $$
  \Rightarrow L(\mathbf{L}, \mathbf{E}, \mathbf{Y}) = |\mathbf{L}|_* + \frac{\mu}{2}

  | \mathbf{L} + \mathbf{E} - \mathbf{X} +\frac{\mathbf{Y}}{\mu}
  |_F^2

  • \frac{\mu}{2}| \mathbf{E} - \mathbf{X} + \frac{\mathbf{Y}}{\mu} |_F^2

  $$

  整理公式

  最后，我们重新整理公式并只关注与 $\mathbf{L}$ 相关的项：【即省掉了末尾不含 $L$ 的项】

  $$L(\mathbf{L},\mathbf{E},\mathbf{Y})=\Vert \mathbf{L}{\Vert }_{\ast }+\frac{\mu }{2}\Vert \mathbf{L}+\mathbf{E}-\mathbf{X}+\frac{\mathbf{Y}}{\mu }{\Vert }_F^2+\text{常数项}$$

  这就得到了我们要优化的目标函数形式：

  $${\mathbf{L}}_{k+1}=\arg \underset{\mathbf{L}}{\min }\Vert \mathbf{L}{\Vert }_{\ast }+\frac{{\mu }_k}{2}{\Vert \mathbf{L}+{\mathbf{E}}_k-\mathbf{X}+\frac{{\mathbf{Y}}_k}{{\mu }_k}\Vert }_F^2$$!