通过一种新颖的非凸极小极大p-th阶凹函数惩罚方法实现张量补全

《Pattern Recognition》：Tensor completion via a novel non-convex minimax p -th order concave penalty method

　　张洪兵|郑兵
兰州大学数学与统计学院，兰州730000，中国

**摘要**
低秩张量补全（LRTC）问题旨在从部分观测数据中重建张量，在模式识别和计算机视觉等各种实际应用中引起了广泛关注。在为LRTC开发的各种技术中，非凸松弛方法因其在处理张量奇异值方面的有效性而受到了广泛研究，这些奇异值在准确恢复张量中起着关键作用。尽管极小极大凹罚函数（MCP）非凸松弛方法在解决LRTC问题方面取得了有希望的结果并得到了广泛应用，但它仍然存在一个显著的限制——在处理奇异值时对小奇异值的惩罚不足，导致张量恢复效果不佳。为了解决这个问题并提高恢复性能，本文提出了一种新的极小极大p阶凹罚函数（MPCP）。基于这种新函数，提出了一种张量p阶τ范数作为张量秩逼近的非凸松弛方法，从而建立了一个基于MPCP的LRTC模型。此外，还严格证明了所提方法的收敛性。在多个真实数据集上进行的广泛数值实验表明，所提出的方法在视觉质量和定量指标上均优于现有方法。代码可在以下链接获取：https://github.com/zhbyhww/MPCP

**引言**
张量因其能够捕获多模态和多关系数据中的内在结构信息而受到广泛认可，这使得张量处理成为图像和视频处理、磁共振成像数据恢复[1]、模式识别[2][3]、机器学习[4][5]和计算机视觉[6][7]等多个领域的重要组成部分。然而，在实际应用场景中，由于不可预测或不可避免的干扰，真实世界中的张量数据经常被损坏，因此对张量补全技术的需求不断增加，以恢复多维数据的完整性。
张量秩最小化已在许多领域得到广泛应用，例如低秩张量补全（LRTC）[5][7]、张量鲁棒主成分分析（TRPCA）[3][7]、子空间聚类[8][9]、图结构学习[10][11]等。例如，Yang等人[7]提出了一种基于加权张量Schatten-p准范数的方法来从LRTC和TRPCA问题中恢复低秩张量。[8]利用自动编码器学习低秩子空间表示，而Wang等人[10]采用拉普拉斯秩约束来促进清晰的结构关系。然而，张量秩的定义并不唯一。主流的张量秩定义包括基于CP分解的CANDECOMP/PARAFAC（CP）秩[12]、基于Tucker分解的Tucker秩[13]以及由张量奇异值分解（t-SVD）[15]得到的tubal秩[14]。不过，直接求解CP秩是NP难的[16]。Tucker秩需要对张量进行矩阵化，这可能会破坏它们的内在结构信息，而张量tubal秩的计算则避免了矩阵化，从而更好地保留和利用了张量的内部结构。随后，张等人[17]提出了基于张量tubal秩的张量核范数（TNN）来解决LRTC问题，并取得了更好的张量恢复效果。最近，郑等人[18]提出了一种新的秩形式，即N-tubal秩，它基于张量tubal秩，并采用了一种新的展开策略，可以将高阶张量转换为三阶张量。这种方法使得t-SVD可以应用于高阶张量。尽管TNN方法已成为解决LRTC问题的常用方法，但它对所有奇异值施加相同的惩罚，这通常会导致次优解。相比之下，非凸松弛方法因能更有效地处理张量奇异值而受到越来越多的关注。为了实现非凸松弛，研究人员采用了各种函数和方法，包括对数函数[19]、极小极大凹罚函数（MCP）[20][21]和t-Schatten-p范数[22]。这些方法采用不同的非凸惩罚机制，提供了更大的灵活性来处理张量奇异值，从而提高了张量恢复性能。
最近，作为代表性的非凸松弛方法，MCP函数在解决LRTC问题方面取得了有希望的结果[23][24][25][26]。在[21]的工作中，使用不同参数设置的MCP函数对不同的奇异值进行惩罚，从而提高了整体恢复性能。然而，随着问题规模的增加，为每个奇异值确定适当的参数变得极其具有挑战性。在[26]中提出的双变量等效MCP方法允许迭代更新参数，从而显著提高了恢复性能。Chen等人[23]提出了一种截断MCP方法来惩罚奇异值，通过调整截断率和相应的MCP参数取得了改进的结果。尽管有这些进展，但仍存在一个根本限制：这些方法仍然依赖于精心设计的参数调整策略才能达到满意的性能。然而，MCP函数的一个固有限制——对小奇异值的惩罚不足——在上述方法中仍未得到解决。为了解决这个问题，提出了一种新的极小极大p阶凹罚函数（MPCP）。所提出的MPCP函数不仅保留了MCP函数保护大奇异值的 desirable 属性，还对小奇异值施加了更强的惩罚。MPCP函数中引入的参数p允许对小奇异值进行更强的惩罚，从而有效抑制噪声和异常值，同时保留重要的结构细节，最终提高了恢复性能。具体来说，本文的主要贡献如下：
首先，提出了一种新的MPCP函数，以克服MCP函数对小奇异值惩罚不足的局限性。系统地分析了MPCP函数的关键数学性质并进行了理论证明。为了促进LRTC应用中的高效优化，推导出了其近端算子。此外，还深入研究了MPCP函数对张量奇异值的扩展，包括张量p阶τ范数的定义及其性质的全面分析。
其次，开发了一个基于MPCP的LRTC模型，并通过交替方向乘子法（ADMM）实现了优化算法。提供了严格的理论收敛性分析，以确保算法的数值稳定性和可靠性。实验结果进一步表明，所提出的方法收敛迅速并且恢复性能稳定。
第三，在包括三阶、四阶和五阶张量在内的多维数据集上进行了广泛实验，以评估所提方法的泛化能力。实验结果表明，基于MPCP的方法明显优于现有方法。特别是与基于MCP的变体进行比较分析后，进一步验证了所提出的MPCP框架的优越性能，这与理论分析完全一致。

**本文的其余部分组织结构如下**：第2节介绍了张量的基本概念和背景。第3节提出了与所提出的MPCP函数相关的定义和理论结果。第4节描述了主要贡献，包括基于MPCP的模型和相应的优化算法。第5节提供了所提方法的收敛性分析。第6节报告了实验结果和讨论。第7节得出了结论。我们方法的流程图见图1。

**预备知识**
在本节中，我们介绍了本文中使用的基本符号和定义。通常，小写字母表示向量b，大写字母表示矩阵B。书法风格的大写字母B∈R^J_1×J_2×?×J_N表示一个N阶张量，B_{j_1,j_2,…,j_N表示其(j_1,j_2,…,j_N)元素。张量的Frobenius范数定义为‖B‖_F=(∑_{j_1,j_2,…,j_N}B_{j_1,j_2,…,j_N}^2)^{1/2}。对于一个三阶张量B∈R^J_1×J_2×J_3，我们使用MATLAB符号B(k,:,:)、B(:,i:)和B(:,:)。

**极小极大p阶凹罚函数**
在本节中，为了克服MCP函数的局限性，提出了MPCP函数。
**定义3.1 MPCP函数**
设τ>1, 0τ^1/p。
与MCP函数相比，所提出的MPCP函数引入了一个额外的参数p。显然，当p=1时，MPCP函数退化为MCP函数；而当p<1时，它表现出不同的行为，表明MPCP函数具有更广泛的定义。

**基于MPCP的模型和求解算法**
LRTC问题旨在从不完整的观测张量中估计缺失元素。考虑一个N阶观测张量O∈R^J_1×J_2×?×J_N，LRTC问题可以表述为
min Brank(B) s.t. PΩ(B)=PΩ(O)，
其中B表示原始完整张量，运算符PΩ(B)是仅保留索引集Ω对应条目的投影运算符，并将所有其他条目设置为零。

**收敛性分析**
在本节中，为了严格证明所提算法1的理论收敛性，我们首先引入以下引理，作为后续证明和分析的基础结果。
**引理5.1 [32]的命题6.2**
假设F: R^I_1×I_2→R表示为F(X)=f°σ(X)，其中X∈R^I_1×I_2，SVD : X=Udiag(σ_1,…,σ_R)VT，R=min{I_1,I_2}，且f是可微的。F(X)在X处的梯度为?F(X)?X=Udiag(θ)VT，θ=?f(y)?y|y=σ(X)。
**引理5.2**
算法1生成的序列{T_q^k}_{q=1}^N(N?1)/2是有界的。

**实验**
使用多种质量指标评估了所提出的MPCP方法的性能，包括峰值信噪比（PSNR）值、结构相似度（SSIM）值[33]、特征相似度（FSIM）值[34]和合成全局误差（ERGAS）值[35]。在这些指标中，较高的PSNR、SSIM和FSIM值表示更好的性能，而较低的ERGAS值更受青睐。所有实验都在Windows 11平台上使用MATLAB进行。

**结论**
本文提出了一种新的非凸函数，称为MPCP函数。MPCP函数在有效保留大奇异值的同时，对小奇异值施加了较强的惩罚，从而克服了MCP函数在惩罚小奇异值方面的关键限制。理论和实验结果均证实了MPCP函数优于MCP函数。作为LRTC问题的非凸松弛方法，推导出了张量p阶τ范数。我们进一步...

**作者贡献声明**
张洪兵：撰写——原始稿件、软件、方法学、数据整理。
郑兵：撰写——审阅与编辑、监督、资金获取。

**利益冲突声明**
作者声明他们没有已知的竞争性财务利益或个人关系可能会影响本文报告的工作。

**致谢**
本工作得到了国家自然科学基金（项目编号12471353）的支持。