结构型优化及其在数据分析中的应用

Recently, with the rapid development of computer science, internet and information technology, the processing of massive data sets has become increasingly important. In applications including compressive sensing, image and signal processing, machine learning and information processing, etc., the data sets need to be processed are frequently extremely large scale. How to process massive amounts of data and find the hidden useful information rapidly and effectively have become a challenge which must be faced by people working in scientific research and engineering technology. This project aims to study the theory and fast algorithms for structured optimization problems and their applications in data analysis, including the aforementioned applications and, more generally, various fields of data science. Very often, high dimensional data sets intrinsically preserve various structures, e.g., some components of the data are sparse or structured sparse under certain transformations, low rank, lie in certain low dimensional linear subspaces or nonlinear manifolds, or approximately so, etc. One of the main research subjects of this project is to fully exploit various structures hidden in high dimensional data through constructing appropriate models. In addition, we study systematically the efficiency of structured optimization models both theoretically and numerically, design high performance numerical algorithms by fully taking into account the structures of both the models and the solutions, and develop highly efficient software packages which are useful broadly in engineering and technology.

近年来，随着计算机科学、因特网与信息技术的快速发展，人们对海量数据的处理需求愈来愈大。在包括压缩感知、图像与信号处理、机器学习、信息处理等诸多应用领域中所产生的数据量往往十分巨大。如何快速高效的从海量数据中找到对生产实践有用的信息是科研与工程技术人员必须面对的挑战。 本项目旨在研究各种结构型优化问题的理论、快速算法及其在数据分析中的应用，包括上述应用，以及更广泛的数据科学。高维数据通常具有内在结构，如某些数据成分在适当的变换下稀疏、结构型稀疏、低秩、位于一个低维线性空间或非线性流形上，或者近似如此等等。通过建立适当的优化模型来挖掘高维数据的内在结构信息是本项目的主要研究内容之一。此外，本项目将通过理论分析与数值实验相结合的方法对各种结构型优化模型的有效性进行系统研究，充分考虑模型与问题解的结构特性来设计高效的数值计算方法，并编写相应的可供工程技术界广泛应用的软件程序。

本项目针对压缩感知、图像处理、鲁棒主成分分析、半定规划、机器学习、信息处理等领域中数据量巨大与问题的结构特点，研究了各种结构型优化问题的理论、快速算法及其应用。提出、分析并测试了惯性原始对偶算法、惯性交替方向法、惯性邻近点算法、非精确交替方向收缩算法，并着重研究了从不完全卷积信息中恢复图像信号、鲁棒主成分分析与半定规划的Gauge对偶理论与可并行化算法。通过挖掘内在结构，包括变换稀疏、结构型稀疏、低秩等，借助理论分析与数值实验相结合的方法系统研究了各种结构型优化模型的有效性，并设计了根据问题结构特殊定制的高效数值计算方法，我们的程序与实验结果可供工程技术界使用。所提出的惯性算法能够提高计算效率，gauge对偶理论可用于设计单步计算量低的算法，用于超大规模矩阵计算。另外，我们还对压缩感知、L1模优化、图像处理中全变差正则化问题的快速算法进行总结与推广。合作者在多块分裂问题上的交替方向法的反例在理论上了说明了多块问题的复杂性，并驱动多块问题的收敛算法研究。另外，指导学生完成的交替惯性邻近点算法具有更好的收缩性质，并引起一些法国学者的广泛关注。