3-应用案例-稀疏优化

知识点：稀疏优化

知识点概述

稀疏优化旨在从众多可行解中寻找一个非零元素最少的“稀疏解”。它在信号处理、压缩感知和机器学习等领域有广泛应用，通常通过L1范数松弛来求解。

教材原文

考虑线性方程组求解问题： $Ax=b$ … 其中… $mlessn$ 。… 真正有用的解是所谓的“稀疏解”，即原始信号中有较多的零元素。… 我们可以通过求解稀疏优化问题把 $u$ 与方程组 (1.2.1) 的其他解区别开。这类技术广泛应用于压缩感知…

$$\begin{array}{l}{\min }_{x\in {\mathbb{R}}^n}\Vert x{\Vert }_0,\\ \begin{array}{ll}\text{s . t .}& Ax=b.\end{array}\end{array}\text{\hspace{1em}(1.2.2)}$$

… 由于 $\Vert x{\Vert }_0$ 是不连续的函数… 问题(1.2.2)实际上是NP难的… 若定义 ${\ell }_1$ 范数： $\Vert x{\Vert }_1={\sum }_{i=1}^n|x_i|$ ，并将其替换到问题(1.2.2)当中，我们得到了另一个形式上非常相似的问题…

$$\begin{array}{l}{\min }_{x\in {\mathbb{R}}^n}\Vert x{\Vert }_1,\\ \begin{array}{ll}\text{s . t .}& Ax=b.\end{array}\end{array}\text{\hspace{1em}(1.2.3)}$$

详细解释

• 背景: 在许多实际问题中，如信号恢复和特征选择，我们先验地知道有意义的解是稀疏的。
• 核心问题 (L0范数): 直接最小化非零元素个数（$el{l}_0$范数）是组合优化问题，计算上非常困难（NP难）。
• 凸松弛 (L1范数): 核心思想是用$el{l}_1$范数替代$el{l}_0$范数。$el{l}_1$范数是凸函数，它能诱导出稀疏解，且对应的优化问题（如基追踪）是凸优化问题，可以被高效求解。
• 几何直观: $el{l}_1$范数球的“尖角”恰好位于坐标轴上，这使得它与可行域（如超平面 $Ax=b$）的交点很可能在坐标轴上，从而产生稀疏解。而$el{l}_2$范数球是光滑的，交点通常不具有稀疏性。

学习要点

• 理解“稀疏”的含义。
• 了解为什么直接求解$el{l}_0$最小化是困难的。
• 掌握使用$el{l}_1$范数作为凸代理来促进稀疏性的核心思想。
• 熟悉基追踪 (Basis Pursuit) 和 LASSO 模型。

实践应用

• 压缩感知: 从远少于奈奎斯特采样率的样本中重建信号。
• 机器学习特征选择: 在回归模型中加入$el{l}_1$正则项（LASSO），可以使得不重要的特征对应的系数变为0，从而实现自动特征选择。

关联知识点

• 前置知识: 1-核心概念-最优化问题的一般形式, 14-核心概念-向量范数
• 后续知识: 4-应用案例-低秩矩阵恢复, 44-核心概念-复合优化问题, 59-理论方法-次梯度算法
• 相关知识: 10-核心概念-凸和非凸优化