鲁棒低秩张量恢复问题的非凸算法研究

Tensor-based modeling and computation have emerged and drawn a lot of attentions with the advent of big data era and the demands for high dimensional data processing. Robust low-rank tensor recovery problem, also known as tensor or higher order robust principle component analysis, is one kind of tensor optimization problems which recovers tensors with low-rank and sparse structure from limited measurements. It has a wide range of applications in data mining, machine learning, image processing, collaborative filtering, computer vision and so on. This project aims to study the non-convex algorithms for robust low-rank tensor recovery problem, which mainly includes the following three parts: The first is to introduce the non-convex relaxation models for robust low-rank tensor recovery problem, and design highly efficient and robust algorithms for the obtained large scale non-convex tensor optimization problem. The second is to establish the convergence analysis for the proposed algorithms, as well as the exact recovery theory of the non-convex relaxation models for recovering low-rank and sparse tensors. The third is to conduct numerical experiments on synthetic data, and apply the proposed algorithms in image processing, computer vision and other practical problems. The project is of important significance in both academic researches and practical applications, since it not only gives a new idea to the study on algorithms for robust low-rank tensor recovery problem, promotes the developments of tensor computation, tensor optimization and non-convex programming, but also provides theoretical and methodological support for solving the practical problems in real-world applications.

随着大数据时代的来临及处理高维数据的实际需求，基于张量的建模与计算应运而生并受到广泛关注。鲁棒低秩张量恢复问题作为一类刻画张量低秩性及稀疏性的张量优化问题，在数据挖掘、机器学习、图像处理、协同过滤和计算机视觉等领域都具有重要的应用。本项目将考察该问题的非凸算法研究，主要内容包括：第一是针对鲁棒低秩张量恢复问题构建非凸松弛模型，并设计高效稳定、适合求解大规模问题的数值算法；第二是针对所提的算法建立收敛性分析，及针对相关的非凸松弛模型建立精确恢复理论；第三是进行数值实验，并根据实际问题的特性将所获的研究成果应用到图像处理、计算机视觉等应用领域。本项目不仅为鲁棒低秩张量恢复问题的算法研究提供了新的思路，而且能够促进张量计算、张量优化与非凸规划的发展，并为相关应用领域中实际问题的研究提供有效的理论支撑和求解保障，具有重要的学术研究意义和实际应用价值。

项目以结构张量相关优化问题为中心进行了一系列的相关研究。研究的主要内容为低秩张量恢复问题的非凸算法及其收敛性分析、张量互补问题的解集理论及其稀疏解和极小元解的快速求解算法与理论分析。第一，项目在Tucker秩框架下建立了张量鲁棒主成分分析的非凸模型，设计邻近交替线性极小化算法和参数自适应学习的非凸交替方向法，并进行理论分析与数值实验。第二，项目建立了闭凸锥上共正张量互补问题解的可行性与可解性之间的等价条件，并弱化了该问题的可解性条件；提出求解隐式Z张量互补问题的单调下降迭代算法，并建立其全局线性收敛率；设计具有有限终止性的低维方法求解广义Z张量定义的齐次多项式不等式组的极小元，并建立极小元的存在性结果等。