机器算法验证 - 压缩感知与 L1 正则化的关系 - 吾爱随笔录

压缩感知与 L1 正则化的关系

机器算法验证套索疏

2022-04-04 00:51:37

我知道压缩感知可以找到最稀疏的解决方案

y = A x

$y = Ax$ 在哪里

x \in R^{D}

$x \in \mathbb{R}^D$ ,

A \in R^{k \times D}

$A \in \mathbb{R}^{k \times D}$ ，和

y \in R^{k}

$y \in \mathbb{R}^{k}$ ,

k << D

$k << D$ .

这样我们就可以重构 $x$ （原文）使用 $y$ （压缩），相当快。我们说 $x$ 是最稀疏的解决方案。稀疏性可以理解为 $l_0$ -向量的范数。

我们也知道， $l_1$ -norm（可使用线性规划求解）是 $l_0$ -norm（对于大型向量来说是 NP-hard）。所以 $x$ 也是最小的 $l_1$ 解决方案 $Ax=y$

我读过压缩感知类似于带有套索惩罚的回归（ $l_1$ ）。我也看到了对此的几何解释，但我还没有在数学上建立联系。

除了最小化 $l_1$ 规范，压缩和套索之间的关系（数学上）是什么？

1个回答

基本上没有区别。这只是统计学家的术语与电气工程师的术语。

压缩感知（更准确地说，基础追踪去噪[1]）就是这个问题：

$\text{arg min}_x \frac{1}{2}\|Ax - b\| + \lambda \|x\|_1$

而 Lasso[2] 就是这个问题

$\text{arg min}_{\beta} \frac{1}{2}\|y - X\beta\| + \lambda \|\beta\|_1$

既然有区别，那就是在压缩传感应用程序中，您（工程师）可以选择 $A$ 要“表现得很好”，而对于 Lasso，您（统计学家）无法选择 $X$ 并且必须处理任何数据（而且它们很少“好”......）。因此，许多随后的压缩感知文献都集中在选择 $A$ 尽可能“高效”，而随后的许多统计文献都集中在对仍然适用的套索的改进上 $X$ 那个“打破”套索。

[1] SS Chen, DL Donoho, MA Saunders。“通过基础追踪进行原子分解。” SIAM 科学计算杂志 20(1), p.33-61, 1998. https://doi.org/10.1137/S1064827596304010

[2] R. Tibshirani “通过套索的回归收缩和选择”。皇家统计学会杂志：B 系列 58(1)，第 267-88 页，1996 年。JSTOR 2346178。

其它你可能感兴趣的问题

上一篇回归输出中的 .hat 是什么下一篇正则化逻辑回归的随机梯度下降