摘要：稀疏优化问题发展至今，已经广泛应用于压缩感知、图像处理、复杂网络、指数追踪、变量选择等领域，并取得了令人瞩目的成就。稀疏优化问题的求解算法种类繁多，根据算法设计原理的不同，可将其大致分为三类：贪婪算法、凸松弛方法和阈值类算法。本文主要介绍稀疏优化问题算法研究进展及各类算法的优缺点。

关键词：稀疏优化问题；压缩感知；信号重构；优化算法

随着当代社会信息技术的飞速发展，所获取和需要处理的数据量大幅增多，而基于传统的香农奈奎斯特采样定理中要求采样频率不得低于信号最高频率的两倍才可以精确重构信号。2006年，Donoho、Candes等人针对稀疏信号或可稀疏表示的信号提出了新的采集和编解码理论，即压缩感知理论。该理论使得通过少量采样即可准确或近似重构原始信號。信号重构问题是一个非凸稀疏优化问题（问题）。该问题是一个NP-hard问题，所以出现了多种不同的处理模型近似地或在一定条件下等价地求解问题。以下就从压缩感知的信号重构理论出发，分析研究稀疏优化问题的模型和求解算法。

一、压缩感知重构问题

在压缩感知理论中，若信号本身是稀疏的，则原始信号和观测信号之间的表达式为：；若信号本身不是稀疏的，但在基底下具有稀疏表示，即，其中是一个稀疏向量，则原始信号和观测信号之间的表达式为：，此时，重构原始信号只需要得到满足该等式约束的稀疏解，便可通过得到原始信号，其中为测量矩阵，为变换矩阵，为感知矩阵。……