1 概念与定义
1.1 向量L0范数的形式定义
设向量 \(x=(x_1,\dots,x_n)\)。其 \(L0\) “范数”定义为 \[
| \|x\|_0=\#\{i: x_i\neq 0\}, |
|---|
\]
| 即向量中非零元素的个数。该量直接刻画“稀疏程度”：非零分量越少，\(\|x\|_0\) 越小。 |
|---|
1.2 矩阵情形：逐元素与按结构计数
对矩阵 \(X\in \mathbb{R}^{m\times n}\)，常见的 \(L0\) 扩展有两类视角：
| 1）逐元素计数：\(\|X\|_0\) 表示矩阵中所有非零元素的个数，即对 \((i,j)\) 逐一计数。 |
|---|
| 2）按结构计数：在需要强调组稀疏、块稀疏或按列/按行选择时，会将“是否为零”从单个元素提升到更高层级的结构单元，例如“非零列的数量”。这种做法通常不再严格等同于逐元素的 \(\|X\|_0\)，但仍可视为与“非零计数”思想同源的度量。 |
1.3 与“稀疏度”的关系：为何它度量非零个数
| 稀疏度强调“信息是否集中在少数分量上”。在许多建模中，系数为零表示相应特征/分量未被选用；而 \(\|x\|_0\) 正是对“被选用的分量数量”的直接计数。因此它与特征选择、稀疏表示的目标高度一致：希望用尽量少的非零项解释数据。 |
|---|
1.4 与范数公理的关系：为什么常被称为“准范数”
| \(\|x\|_0\) 在满足非负性、仅当 \(x=0\) 时取零等方面类似范数，但其也存在与范数公理不相容的点，尤其是齐次性和三角不等式不一般成立。例如，若对标量乘子 \(a\)，当 \(a\neq 0\) 时 \(\|ax\|_0=\|x\|_0\)，而当 \(a=0\) 时变为 0，这与范数要求 \(\|ax\|= | a | \|x\|\) 的线性缩放规律不同。由于这些不满足点，它常被称为“准范数”或“伪范数”，名称虽沿用“范数”，但含义更偏向“稀疏度度量”。 |
|---|
2 性质与等价表述
2.1 基本性质：非负性、离散性与单位变换效应
| - 非负性：\(\|x\|_0\ge 0\)，且 \(\|x\|_0=0\) 当且仅当 \(x=0\)。 |
|---|
- 离散性：该量只能取整数值，反映其对“是否为零”的敏感性，而非对幅值的连续变化敏感性。
| - 单位变换效应：对任意非零标量 \(a\)，\(\|ax\|_0=\|x\|_0\)，因为非零分量仍保持非零；这使得它对缩放不敏感，但对“恰好为零”的结构极其敏感。 |
|---|
2.2 计算视角：支持集（support）大小
令支持集 \[ \operatorname{supp}(x)=\{i: x_i\neq 0\}, \] 则 \[
| \|x\|_0= | \operatorname{supp}(x) | . |
|---|
\] 从计算角度，问题“最小化 \(L0\)”等价于“让支持集尽可能小”，即减少被激活的坐标集合。
2.3 几何解释：对应的集合族分段结构
| 由于 \(\|x\|_0\) 只关心哪些坐标为零，其值在坐标空间中呈现分段、离散的结构。特别地，固定支持集大小为 \(k\) 时，满足 \(\|x\|_0\le k\) 的向量集合可以理解为一族低维子空间的并：每个子空间对应于某个大小不超过 \(k\) 的支持集，其余坐标恒为零。因此从几何上看，\(\|x\|_0\) 的“等值/亚水平集”往往由多块子空间拼接而成，缺乏连续凸曲面那种良好性质。 |
|---|
2.4 与其他度量的对比：L1、L2、L∞的区别
| - 与 \(L1\)：\(L1\) 度量 \(\sum_i | x_i | \)，对缩放与幅值变化连续响应；同时它常被用作 \(L0\) 的替代，因为在很多场景下能鼓励稀疏。 |
|---|
- 与 \(L2\)：\(L2\) 度量 \(\sum_i x_i^2\)，更关注能量或均方意义，通常不会直接等同于稀疏。
| - 与 \(L\infty\)：\(L\infty\) 度量 \(\max_i | x_i | \)，强调最大分量的幅值；对“非零个数”本身不直接敏感。 |
|---|---|---|
| 总体而言，\(\|x\|_0\) 是“计数型”的度量，而 \(L1/L2/L\infty\) 是“幅值型”的连续度量。 |
3 在优化与算法中的作用
3.1 稀疏优化问题的典型形式
常见形式包括：
| - 稀疏回归：在拟合误差可控的情况下，最小化 \(\|x\|_0\)。例如希望找到尽量少的非零系数，使得 \(Ax\) 能近似观测 \(y\)。 |
|---|
- 稀疏表示：给定字典 \(D\) 和信号 \(y\)，寻找稀疏系数 \(x\)，使得 \(y\approx Dx\)。
- 稀疏解约束：在满足线性等式约束（或不等式约束）时，寻找最小非零个数的解。
3.2 L0最小化的难点：非凸性与组合性质
| 由于 \(\|x\|_0\) 是对“是否为零”的指示计数，它导致优化目标通常非凸，并且带有明显的组合性：你需要决定哪些坐标保持为零，哪些允许为非零。支持集的选择相当于在离散集合之间搜索，通常复杂度高，理论与计算上都较难直接求全局最优。 |
|---|
3.3 约束与惩罚的常见写法
在实际建模中，常将“拟合质量”和“稀疏性”组合：
| - 约束型：例如在误差不超过阈值时最小化 \(\|x\|_0\)。 |
|---|
| - 惩罚型：将 \(\|x\|_0\) 乘以权重加入目标函数，使其在优化过程中自然平衡稀疏与拟合。 |
这种写法为后续使用近似或替代目标提供了结构化入口。
3.4 可解替代：L1近似与稀疏正则化框架
由于 \(L0\) 的硬计数不可直接优化，常用的替代思想包括：
| - \(L1\) 正则化：用 \(\|x\|_1\) 替代 \(\|x\|_0\)，得到相对容易求解的凸问题（在合适约束下）。 |
|---|
- 稀疏正则化框架：通过选择不同的正则项（如 \(L1\) 或其他更平滑的近似），使优化目标在数值上可处理，同时仍尽量促使大部分分量变为零或接近零。
这类替代的核心是用“可连续优化”的方式逼近“计数型稀疏”的效果。
3.5 近似/贪心思路：从“数非零”到“找稀疏”
在算法层面，常见策略包括：
- 迭代选择支持集：先假设某些坐标为非零，求解在该支持集上的子问题；再根据残差或准则更新支持集。
- 阈值化/截断思想：对中间解进行筛选，例如保留绝对值最大的若干分量，把其余设为零；再在被保留的坐标上重新优化。
这些方法不保证全局最优，但往往在工程上有效，并与“最小化非零个数”的直觉相对应。
4 理论联系与应用场景
4.1 压缩感知与稀疏重建的直观对应
压缩感知常以“低稀疏度信号可由少量测量重建”为中心论题。直观上，若信号在某个表示系数上很稀疏，那么用 \(L0\) 最小化寻找最少非零解释项，能在理想条件下对应到正确的稀疏结构。由于 \(L0\) 难求，实际算法往往转向 \(L1\) 重建或其它可计算近似，以保留理论上的可行性和稳定性。
4.2 特征选择与模型稀疏性
在机器学习与统计建模中，稀疏系数常被用作“自动筛选变量”的机制：
- 系数为零（或被压到非常小）意味着对应特征不进入最终模型；
- 将模型的复杂度与非零项数量直接关联，有助于解释性与泛化能力。
| 因此，\(\|x\|_0\) 的思想天然适配“少量特征解释数据”的目标。 |
|---|
4.3 离散选择问题的编码视角（与0-1决策的关联）
| 最小化 \(\|x\|_0\) 可以通过引入指示变量把“是否为零”变成离散决策：例如定义 \(z_i\in\{0,1\}\) 表示第 \(i\) 个分量是否被允许为非零，再通过约束把 \(z_i\) 与 \(x_i\) 的非零性连接。这样一来，优化问题就呈现为“选择集合 + 连续变量求解”的混合结构，与组合优化或 0-1 决策问题在形式上相近。这也是其计算困难的重要来源。 |
|---|
4.4 在数值实现中避免“硬计数”的策略
数值求解通常不直接处理 \(L0\) 的硬计数，而是采用以下缓解手段：
- 使用连续近似，使“接近零”能逐步影响目标；
- 采用凸松弛（如 \(L1\)）以获得更稳定的算法性质；
- 采用分阶段策略（先近似、再裁剪）以兼顾计算效率与稀疏效果。
这些做法的共同点是把“非零计数”转化成可迭代、可导或至少更易处理的准则。
4.5 常见实践经验：何时用L0想法，何时转向L1
经验上可以概括为：
- 当明确追求“最少非零项”，且问题规模较小或可容忍组合搜索时，\(L0\) 的思想常能提供清晰目标。
- 当面对高维数据或需要稳定可扩展的求解时，通常转向 \(L1\) 或其它近似，因为它们更容易实现并具有更好的优化性质。
- 在实际工程中也常出现折中：用 \(L1\) 得到候选稀疏结构，再通过阈值化或精炼步骤接近 \(L0\) 的目标。
总体而言，\(L0\) 更像“稀疏选择的理想准则”，而 \(L1\) 等方法更像“可计算的实现路径”。