高阶张量的低秩恢复问题研究

The low-rank recovery of higher order tensor is a minimization problem,which is a basic problem in optimization and tensor computation, and is also frontier issue in signal processing, image processing and other disciplines in applied sciences. Generaly speaking, this problem is a generalization of the vector sparse solution and the matrix low-rank minimization, which are NP-hard to solve. However, this problem cannot be solved via the method of dealing with the problems of vector sparse solution and the matrix low-rank minimization, due to the essential difference between tensor and matrix, vector. In this project, the low-rank recovery of higher order tensor will be studied in the following aspects. Firstly, the properties of multilinear rank of higher order tensor are studied, by which a new equivalent form of the considered problem is presented as well as the relaxed one. Then a numerical algorithm for the relaxed problem is given. Secondly, the low symmetric CP-rank minimization of the symmetric tensor is transformed as a vector sparse solution problem with polynomial constraints. From this, the relaxed problem is investigated, whose optimization theory and numerical algorithms are established. Then, the obtained theories are extened to those for general CP-rank minimization. Thirdly, the exact sparse recovery conditions of two kinds of relaxed low-rank recovery problems are discussed. Then, the approximation solution theory will be studied. Finally, the numerical algorithms applicable to large-scale compulations will be designed and then the practical soft programming will be presented. In a word, this project can not only facilitate the theory on optimization theory and tensor computation, but also provide theoretical support to the technical sciences.

高阶张量的低秩恢复问题是一类极小化问题，它是信号处理、图像处理等应用学科的前沿问题,也是最优化与张量计算领域的基本问题。该问题是向量稀疏解问题与矩阵极小秩问题的高阶推广，它们都是NP-难的。由于张量与矩阵、向量的本质区别，使得我们无法套用向量稀疏解问题与矩阵极小秩问题的研究思路来研究该问题。本项目拟从以下方面对该问题展开研究。首先，研究张量的多线性秩性质，建立该问题新的等价形式及相应松弛问题，并对松弛问题提出有效数值算法。其次，研究对称张量空间上的对称CP秩极小化问题,将问题转化为带有多项式约束的向量稀疏解问题并进行松弛，建立松弛问题的优化理论并提出有效算法，且推广所建理论到一般张量的CP秩极小化问题。再次，讨论两种低秩恢复模型松弛问题的精确恢复条件及逼近解理论。最后，设计适合于大规模计算的数值算法并编制有效的实用软件。该研究不仅能够推动优化理论与张量计算的理论与算法，而且有一定的实际价值

近四年来，本项目主要研究了高阶张量低秩恢复相关理论与算法，项目负责人及参与人研究结果如下： 建立了对称高阶张量秩与对称秩的关系，我们证明在一定条件下，对称张量的秩等于其对称秩，这部分的解决了Comon猜想。建立了可分离矩阵与正映射判定的数值算法，算法对于可分离矩阵给出一种分解形式，对于不可分离矩阵给出数值证明；对于给定映射能够有效判定其是否为正映射。将SDP松弛理论多次成功运用到相关各种张量计算问题，如协正张量的判定、非对称张量所有特征值的计算等。本项目目前资助发表SCI论文15篇，其中多篇为顶级期刊。本项目资助召开学术研讨会1次，参加国内外学术会议多次。