非凸稀疏优化的恢复条件与低复杂度算法的研究

项目名称： 非凸稀疏优化的恢复条件与低复杂度算法的研究

项目编号： No.11501569

项目类型： 青年科学基金项目

立项/批准年度： 2016

项目学科： 数理科学和化学

项目作者： 张慧

作者单位： 中国人民解放军国防科技大学

项目金额： 18万元

中文摘要： 稀疏优化研究如何从不定的线性方程系统中寻找特殊结构的解（如稀疏恢复中的稀疏向量解和低秩恢复中的低秩矩阵解），该问题是信号图像处理、压缩感知、机器学习、高维统计、大数据等诸多科学与工程领域中的核心问题。近年来，以压缩感知理论为代表的凸型稀疏优化研究取得了很大进展，而触及到稀疏问题本质的非凸稀疏优化的研究还处于初级阶段。本项目一方面通过开发非凸函数的正则性质，研究非凸稀疏优化中的稀疏恢复解唯一性与稳健性条件；另一方面，通过结合活跃集方法与拟牛顿算法的思想，开发低维子空间中二阶梯度信息，设计全局收敛的低复杂性稀疏优化算法。本项目的研究成果既可为深入理解非凸稀疏优化的内在机制提供基础理论，也可为大规模稀疏优化问题提供高效的求解算法，因此具有理论和应用的双重意义。

中文关键词： 非凸稀疏优化；迭代复杂性；非凸正则性；稀疏恢复条件；；l_p极小化

英文摘要： Sparse optimization studies the problem of seeking special structured solutions, such as sparse vector solution in sparse recovery and low-rank matrix solution in low-rank recovery, from underdetermined linear equation system. This problem becomes a hot topic recently and attracts lots of attention from many fields, including imaging/signal processing, compressive sensing, machine learning, high-dimensional statistics, big data, and more. Although great progress of convex sparse optimization problem has been made during the past decade, non-convex sparse optimization problem which touches the most difficult part of sparse optimization only stays its primary stage. This research project on one hand studies non-convex sparse recovery condition by exploiting the non-convex notion of non-convex functions, on the other hand designs globally convergent sparse optimization algorithms with low-complexity by utilizing the ideas of active set method and qusi-Newton method and exploiting the second order information in low-dimensional subspaces. The research project will provide us not only with a basic theory of non-convex sparse optimization for its deep understanding of internal mechanism, but also with highly efficient algorithms for large-scale sparse optimization problems.

英文关键词： non-convex optimization;iteration complexity;non-convex regular property;sparse recovery condition; l_p minimization