1. 课程导入与问题定义

在信号处理、压缩感知、机器学习特征选择和系统辨识中，我们经常遇到同一类问题：观测数据有限，而待求参数很多。用线性代数的语言说，就是求解方程

A x = b,   A ∈ R^(m×n),  m < n

其中 A 是已知的观测矩阵（或字典、设计矩阵），b 是长度为 m 的观测向量，x 是长度为 n 的未知参数向量。由于方程个数少于未知数个数，矩阵 A 的零空间非平凡，满足方程的 x 有无穷多个，这类问题称为欠定线性方程。若 A 还是病态的，即便 m ≥ n，解也会对噪声极其敏感。

无穷多解意味着“方程本身”不足以确定答案，必须引入额外信息。L1 正则化的出发点正是这样一个先验假设：真实的 x 是稀疏的，即绝大多数分量为零，只有少数非零项。例如在压缩感知中，一幅图像在小波基下只有少量大系数；在特征选择中，上百个候选特征里往往只有几个真正影响输出。此时我们不再追求“满足方程的任意解”，而是寻找“满足方程且最稀疏的解”。

为什么是 L1，而不是 L0 或 L2

最直接的稀疏度量是 L0 范数，即非零元素个数。但 L0 最小化是组合优化问题，规模稍大就无法穷举。L2 正则化（岭回归）虽然易解，却倾向于把能量摊薄到所有分量上，得到稠密解，不具备稀疏性。L1 范数 ‖x‖₁ = Σ|xᵢ| 是 L0 的凸松弛：它的等值面是菱形（二维）或多面体，带有尖角，最优解容易落在坐标轴上，从而产生精确的零分量。同时 L1 问题是凸优化问题，可以高效求解。这就是 L1 被称为“稀疏性的最佳凸代理”的原因。

本课程采用的优化形式为

min_x  (1/2)‖A x − b‖₂² + λ‖x‖₁

第一项是数据保真项，衡量解与观测的拟合程度；第二项是正则项，惩罚非零分量；λ > 0 是正则化参数，控制两者的权衡。λ 越大，解越稀疏但拟合越差；λ 越小，拟合越好但稀疏性减弱。当 λ 超过某个阈值时，解会退化为全零向量，这个阈值与 Aᵀb 的无穷范数直接相关。

参数恢复的评价标准

求解出 x̂ 之后，如何判断“恢复得好不好”？不能只看目标函数值，因为目标函数包含正则项，不同 λ 下的值不可直接比较。实践中通常从三个层面评价：

• 支撑集恢复：估计解的非零位置集合 supp(x̂) 是否与真实支撑集一致。这是稀疏恢复最核心的指标，常用支撑集精确恢复率、召回率和误报数衡量。若位置找错，即使数值再接近也失去了稀疏建模的意义。
• 幅度误差：在支撑集正确的前提下，比较非零分量的数值偏差，常用相对 L2 误差 ‖x̂ − x*‖₂ / ‖x*‖₂，或逐分量相对误差。注意这里比较的是真实参数 x*，在仿真实验中才可得；真实数据中只能用交叉验证等间接手段。
• 拟合与稳定性：残差 ‖Ax̂ − b‖₂ 应与噪声水平相当，过小说明过拟合噪声，过大说明模型不足；同时观察在轻微扰动观测或更换随机种子时解是否稳定。

整体学习路径

本课程围绕“为什么稀疏、如何刻画稀疏、如何求解、如何验证”展开。首先建立欠定方程与稀疏先验的基本认识，明确 L1 作为凸松弛的地位；接着从几何与优化两个角度理解 L1 产生稀疏解的机制，包括菱形等值面、次梯度与坐标轴解的关系；然后进入求解算法，覆盖近端梯度法、软阈值算子、坐标下降与 ADMM 等主流方法，并讨论收敛性与计算复杂度；随后处理正则化参数选择、字典相干性、恢复条件（如 RIP、互相干性）等理论保证问题；最后通过参数恢复实验，把支撑集恢复率、幅度误差与残差放在一起判读，形成完整的“建模—求解—评价”闭环。

需要强调的是，L1 并非万能。当字典列之间高度相关时，L1 可能选错变量；当真实信号不够稀疏时，稀疏假设本身就不成立。因此后续章节也会讨论这些失效情形及改进方向，例如加权 L1、非凸惩罚与重加权策略。学习时请始终把“稀疏假设是否合理”作为第一问，再谈算法与调参。

下面给出一个最小可运行的示例，帮助建立直觉。设 n = 10、m = 5，真实 x* 只有第 2、7 个分量非零，取值分别为 1.5 和 −0.8，其余为零；A 取标准高斯随机矩阵并按列归一化，b = Ax* + ε，ε 为小方差高斯噪声。用近端梯度法求解 L1 问题，观察不同 λ 下 x̂ 的非零位置与数值。你会发现：λ 很小时解接近最小二乘解，几乎全为非零；λ 适中时非零位置恰好落在 2 和 7 附近；λ 过大时解变为全零。这个“由稠密到稀疏再到全零”的过程，正是后续章节要精确刻画的核心现象。

# 示例参数（仿真假设，非实测）
n, m, k = 10, 5, 2
x_true = zeros(n); x_true[2] = 1.5; x_true[7] = -0.8
A = randn(m, n); A = A ./ norm.(eachcol(A))'   # 列归一化
b = A * x_true + 0.01 * randn(m)
# 对 λ 网格扫描，记录 supp(x̂) 与相对误差

从这一节起，请带着三个问题阅读后续内容：稀疏假设在当前问题中是否成立？所选 λ 与算法是否让解落在正确的支撑集上？用什么指标证明恢复成功？把这三个问题贯穿始终，L1 正则化的学习就不会停留在公式记忆，而能落到可复现的参数恢复实践中。