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

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.

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

在压缩感知和稀疏优化的背景下，课题组从非光滑优化问题的几何条件、梯度型算法的收敛性理论、基于Lasso模型和Dantzig模型的稀疏恢复的充要条件、以及相位恢复问题开展研究。主要取得了如下代表性成果：1. 构建了研究限制强凸性、误差界条件、二次增长条件以及Kurdyka-Łojasiewicz 性质的理论框架；2. 提出了统一的梯度型算法的收敛理论；3. 解决了Lasso模型和Dantzig模型的一个关于稀疏恢复充要条件的公开问题；4. 提出了相位恢复的（稀疏）迭代重加权算法。相关理论成果Google学术引用70余次，引用者包括Lagrange 奖得主Adrian Lewis教授和Farkas奖得主Zhiquan Luo教授等著名学者。