信息处理 - 构建数据的稀疏性和残差之间是否有任何权衡？ - 吾爱随笔录

构建数据的稀疏性和残差之间是否有任何权衡？

信息处理压缩传感

2022-02-06 07:16:42

我将测试一个具有不同参数的稀疏促进算法来解决 $Ax=b$ 获得稀疏模型 $x$ . 我必须测试不同的参数，我的算法会针对这些参数得出不同的答案 $x$ .

与不同 $x$ 有不同的 $Ax=\hat{b}$ 的。为了进行更好的比较，我强制我的算法在 $\left\|Ax-b\right\|^2<\epsilon$ .

现在我获得了所有的，我如何确定哪个模型更好？我知道我正在寻找一个更稀疏且更适合的模型，但我认为我必须以某种方式考虑在稀疏度和残差之间进行权衡。 $x$ $\left\|Ax-b\right\|^2<\epsilon$ $x$ $b$

3个回答

方法的问题是它不平滑且不凸。凸近似是使用来促进稀疏性。有 3 个基本等效的常见公式 - 如果参数选择正确（LASSO、基础追踪去噪 (BPDN) 和二次问题）。 $l_0$ $l_1$

公式为：

L A S S O : min_{x} | | A x - b | |_{2} s . t . | | x | |_{1} \leq τ

$LASSO:\qquad \min_x ||Ax-b||_2 \qquad s.t. \quad ||x||_1 \leq \tau$

B P D N : min_{x} | | x | |_{1} s . t . | | A x - b | |_{2} \leq σ

$BPDN:\qquad \min_x ||x||_1 \qquad s.t. \quad ||Ax-b||_2 \leq \sigma$

Q P : min_{x} | | A x - b | |_{2}^{2} + λ | | x | |_{1}

$QP: \qquad \min_x ||Ax-b||^2_2 +\lambda ||x||_1$

要查看稀疏与拟合的权衡，请检查中的极端选择。在系统欠定的情况下，即存在多个解。如果，则解是正常的最小二乘解，它往往在所有向量分量中都有很多小分量，即往往是非稀疏变化的，但拟合是精确的。在另一种情况下，如，则拟合变得毫无意义，并且解决方案只是可能的最稀疏向量，即。如此直观地，值的选择在解向量的拟合和稀疏性之间进行权衡。 $\lambda$ $Ax=b$ $\lambda = 0$ $x$ $\lambda \rightarrow \infty$ $x=0$ $\lambda$

这种关系在上面给出的其他公式中有点难以看出，但它们是等价的问题。

您可以将问题重新表述为最小化问题：

P 1 : min_{x} ‖ A x - b ‖_{2}^{2} + λ ‖ x ‖_{o}

$P1: \min_x \|Ax -b\|_2^2 + \lambda \|x\|_o$

其中是 x 的范数，其中它是非零元素的数量。寻找 p1 的解决方案本质上是寻找最能解释模型同时具有稀疏系数。问题是 NP 非凸 NP 难，极难优化。另一种方法是使用范数的最佳凸包络，即范数。 $\|x\|_o$ $\ell_o$ $\|Ax -b\|$ $\ell_o$ $\ell_1$

P 2 : min_{x} ‖ A x - b ‖_{2}^{2} + λ ‖ x ‖_{1}

$P2: \min_x \|Ax -b\|_2^2 + \lambda \|x\|_1$

在 A 上的某些条件下，这两个问题实际上是等价的，因为它们具有相同的全局最优解。P2 有许多有效的求解器，包括 ADMMS、随机方法、ISTA 和 FISTA。

要在 MATLAB 中解决 P2，SPAMS是您的朋友。

我知道您可能已经有一组近似解（“现在我获得了所有 ”），并寻找“最佳”稀疏解。计数度量（不是范数，也不是拟定数）是最自然和同质的（对于），但在计算上不易于处理，并且非常对噪音敏感。在比较稀疏性度量中设计了其他度量来解决此问题。在这些提案中，基尼指数和 $x$ $\ell_0$ $\ell_0(\alpha x) =\ell_0( x)$ $\alpha\neq 0$ $\ell_1/\ell_2$ 规范比率非常有希望（它们也是同质的，与规范相反）。例如，后者已被用作稀疏源分离算法中的停止标准。它甚至可以用作稀疏诱导惩罚，例如，参见出租车中的 Euclid：Sparse Blind Deconvolution with Smoothed Regularization $\ell_1/\ell_2$ 。

其它你可能感兴趣的问题

上一篇如何简化此序列下一篇确定涉及积分的系统是时变的还是时不变的