稀疏优化

稀疏优化 (Sparse Optimization)

稀疏优化（Sparse Optimization）是一类以产生稀疏性（少数非零元素）为目标的最优化理论与方法体系。其核心思想是在优化目标中引入稀疏性诱导机制，使得求解结果中的大部分分量为零，仅保留少量关键分量。稀疏优化是现代信号处理、压缩感知（Compressed Sensing）、机器学习和统计建模中的基石性工具，为高维数据的高效表征与处理提供了理论保证。

数学形式化

稀疏优化的一般形式可写为：

其中 $f(\mathbf{x})$ 为数据拟合项（如最小二乘损失 $\|\mathbf{A}\mathbf{x} - \mathbf{b}\|_2^2$），$\Omega(\mathbf{x})$ 为诱导稀疏的正则化项，$\lambda > 0$ 控制稀疏程度。最自然的稀疏度量是 $\ell_0$ 伪范数 $\|\mathbf{x}\|_0 = \#\{i: x_i \neq 0\}$，但该问题为 NP-难组合优化，无法大规模求解。作为凸松弛，L1正则化用 $\|\mathbf{x}\|_1 = \sum |x_i|$ 代替 $\ell_0$ 范数，使问题变为凸优化且可高效求解。经典表述为LASSO回归（Tibshirani, 1996）：

压缩感知理论（Candès–Tao–Donoho）进一步证明，在受限等距性质（Restricted Isometry Property, RIP）条件下，L1松弛能够精确恢复原始的稀疏解。

求解算法

稀疏优化的主流求解算法可分为以下三类：

近端梯度法（Proximal Gradient Method, ISTA）：利用近端算子（Proximal Operator）处理不可微的正则项。对于LASSO问题，近端算子退化为软阈值函数 $S_{\lambda}(z) = \operatorname{sign}(z) \cdot \max(|z| - \lambda, 0)$。ISTA每步迭代为：

快速迭代收缩阈值算法（FISTA, Beck–Teboulle, 2009）在ISTA基础上引入外插加速，收敛速率从 $O(1/k)$ 提升至 $O(1/k^2)$，实际应用中大幅减少迭代次数。

交替方向乘子法（ADMM）：通过引入辅助变量将原问题分解为可独立求解的子问题，特别适合大规模分布式场景。ADMM将LASSO重写为约束形式并构造增广拉格朗日函数，交替更新原始变量和对偶变量，其收敛性由算子分裂理论保证。

应用领域

稀疏优化在以下领域有深远影响：

• 压缩感知与信号处理：从远低于奈奎斯特-香农采样定理要求的观测数中精确重建稀疏信号，应用于MRI加速成像、雷达成像和CT成像。
• 特征选择与高维统计：在高维回归问题（$p \gg n$）中，Lasso回归通过稀疏优化实现变量选择与参数估计的联合求解。
• 图像处理与计算机视觉：图像去噪、超分辨率和图像修复中广泛使用稀疏表示模型，如稀疏表示字典学习方法（KSVD, MOD）。
• 矩阵补全与低秩模型：核范数最小化（矩阵补全）可视为稀疏优化在奇异值上的推广，用于推荐系统和协同过滤。

稀疏优化将组合优化的NP-难问题转化为可高效求解的凸优化问题，其理论与算法持续推动着高维数据分析与智能感知技术的边界。