基于Tensor Train分解的两类张量优化问题的研究及其应用

Tensor Train decomposition is one of the most efficient form to express high-order data. Due to the separable structure, this kind of decomposition brings great convenience for solving large-scale tensor optimization problems. In this project, based on Tensor Train decomposition, we consider two kinds of tensor optimization problems: tensor eigenvalue complementarity problem and tensor completion problem. By integrating tensor analysis (e.g. decomposition, spectral theory) and optimization techniques (e.g. duality, relaxation), we carry out the theoretical analysis and algorithm design from the perspective of alternating optimization and Riemannian optimization, respectively. The main research content includes: 1) For tensor eigenvalue complementarity problem, we analyze the properties of the solutions and propose efficient algorithms with convergence analysis by combining the alternating direction method and projection technique. 2) For tensor completion problem, we establish corresponding tensor optimization model, analyze the properties (e.g. semismooth, strongly semismooth) of objective function on the Riemannian manifold of tensors with fixed TT-ranks, and propose efficient Riemannian gradient method. 3) We apply our proposed methods to practical problems, such as MIMO system simulation and machine learning, in order to check the feasibility and efficiency of our methods.

Tensor Train分解是表示高阶数据有效的分解形式之一，其可分离的结构特点对大规模张量优化问题的求解带来极大便利。在本项目中，我们将基于Tensor Train分解，围绕张量优化中特征值互补和张量完备化这两类重要的问题展开研究，采用张量分析(如分解、谱理论等)与优化方法(如对偶、松弛等)相结合的技术，分别从交替优化和Riemannian优化的角度对所研究的问题进行理论分析和算法设计。内容包括：1)建立张量特征值互补问题解的性质，采用交替方向法和投影技术相结合思路，设计有效算法并进行收敛性分析；2)针对张量完备化问题，建立相应的张量优化模型，分析目标函数在固定张量TT秩所构成的Riemannian流形上的性质(包括半光滑、强半光滑等)，并设计有效的Riemannian投影梯度型算法；3)将所提出的算法应用到MIMO系统仿真、机器学习等实际问题，进一步检验算法的可行性和有效性。

张量优化是最优化研究领域一个新兴研究分支，近年来，基于Tensor Train分解的优化问题的研究越来越引起人们的关注，而目前国内对相关张量优化问题的研究还处于起步阶段。在此背景下，本项目在Tensor Train分解的框架下系统研究张量特征值互补、多项式分类器等问题，同时结合实际问题的特点，设计出有效的求解方法并提供严格可靠的理论依据。在本项目的资助下，取得的主要成果如下：1）张量特征值互补问题是一类重要的非线性优化问题，在固体力学、动力系统等领域具有广泛的应用。本项目研究一类广义张量特征值互补问题，得到其解的性质，包括存在性、唯一性等。在对称情形下，研究其相应优化问题等价形式，得到互补问题解的最优性条件及可解的充分条件，并提出自适应的梯度投影算法，给出收敛性分析。2）模式识别是机器学习中一类非常重要的监督学习问题，其中多项式分类器是一类广泛使用且有效的模型之一。针对传统的多项式分类器在处理高维问题时出现的维数灾难，提出基于Tensor Train分解的学习框架，进一步结合Tensor Train分解的结构特点，提出两种快速可并行的学习算法，并在USPS和MNIST数据集上验证了算法的有效性。3）张量函数表示论是固体力学中基本理论之一，具有重要的理论和实际意义。本项目研究了三阶对称张量和四阶对称无迹张量的各向同性不可约函数基。基于Olive-Auffray整基，首次对三阶三维对称张量的各向同性不变量进行了完整刻画。针对四阶三维对称无迹张量，证明Smith-Bao整基构成不可约函数基，并给出一组新的不可约函数基，并证明其不被任何最小整基包含。