矩阵论-lecture 6-LS

2021-12-11 本文已影响0人吃核桃用手夹

ENGG5781 矩阵分析和计算

第 6 课：重新审视最小二乘法

马永健
2020–2021 第一学期
电子工程系
香港中文大学

第 6 课：重新审视最小二乘法

第一部分：正则化
第二部分：稀疏性
1） $\ell_{0}$ 最小化
2）贪婪的追求， $\ell_{1}$ 最小化，和变化
3）用于 $\ell_{2} - \ell_{1}$ 最小化的凸优化（majorization-minimization）
4）字典学习
第三部分：LS 在 A 中的错误
– LS整体
– 稳健的 LS，及其与正则化的等价

第一部分：正则化

对噪音的敏感性

问题：当有噪声时，LS 解决方案的灵敏度如何？
模型:
$\mathbf{y}=\mathbf{A} \overline{\mathbf{x}}+\boldsymbol{\nu},$
其中 $\overline{\mathbf{x}}$ 是真实结果； $\mathbf { A} \in$ $\mathbb{R}^{m \times n}$ 具有完整的列秩; $\boldsymbol{\nu}$ 是噪声，建模作为具有均值零和协方差 γ 的随机向量 $\gamma ^ {2}$ $\mathbf {I}$ .
均方误差 (MSE) 分析：根据 $\mathbf{x}_{\mathrm{LS}}=\mathbf{A}^{\dagger} \mathbf{y}=\overline{\mathbf{x}}+\mathbf{A}^{\dagger} \boldsymbol{\nu}$ 我们可以得到
$\begin{aligned} \mathrm {E}\left[\left\|\mathbf {x}_{\mathrm {LS}}-\overline{ \mathrm {x}} \right\|_{2}^{2}\right] &=\mathrm{E}\left[\left\|\mathbf{A}^{\dagger} \boldsymbol{\nu}\right\|_{2}^{2}\right]=\mathrm{E}\left[\operatorname{tr}\left(\mathbf{A}^{\dagger} \boldsymbol{\nu} \boldsymbol{\nu}^{T}\left(\mathbf{A}^{\dagger}\right)^{T}\right)\right]=\operatorname{tr}\left(\mathbf{A}^{\dagger} \mathrm{E}\left[\boldsymbol{\nu} \boldsymbol{\nu}^{T}\right]\left(\mathbf{A}^{\dagger}\right)^{T}\right] \\ &=\gamma^{2} \operatorname{tr}\left(\mathbf{A}^{\dagger}\left(\mathbf{A}^{\dagger}\right)^{T}\right)=\gamma^{2} \operatorname{tr}\left(\left(\mathbf{A}^{T} \mathbf{A}\right)^{-1}\right) \\ &=\gamma^{2} \sum_{i=1}^{n} \frac{1}{\sigma_{i}^{2}(\mathbf{A})} \end{aligned}$
观察：如果某些 $\sigma_{i}(\mathbf{A})$ 接近于零，则 MSE 变得非常大。

玩具演示：曲线拟合

image.png

与第 2 课中的曲线拟合示例相同。“真实”曲线是模型阶数 n = 4 的真实 f(x)。实际上，模型阶数可能未知，我们可能不得不猜测。上面的拟合曲线由 LS 完成，猜测的模型阶数为 n = 16。

$\ell_{2}$ -正则化 LS

直觉：替换 $\mathbf {x}_{\mathrm{LS}}=\left(\mathbf{A}^{T} \mathbf {A}\right)^{-1} \mathbf{A}^{T} \mathbf{y}$ by
$\mathbf {x} _ {\mathrm {RLS}}=\left(\mathbf { A}^{T} \mathbf{A}+\lambda \mathbf{I}\right)^{-1} \mathbf {A}^{T} \mathbf{y}$
对于某些 $\lambda>0$ , 添加项 $\lambda \mathbf {I}$ 以改善系统调节，从而尝试降低噪声敏感性。
我们如何理解这样的修改？
$\ell_{2}$ -正则化 LS: 找到一个可以解决的 $\mathrm{x}$
$\min _ {\mathbf{x} \in \mathbb{R}^{n}}\|\mathbf{A} \mathbf{x}-\mathbf{y}\|_{2}^{2}+\lambda\|\mathbf{x}\|_{2}^{2}$
对于某些预先确定的 $\lambda>0$ .
解决方案是唯一给出的 $\mathbf {x}_{\mathrm {RLS}}=\left(\mathbf {A}^{T} \mathbf{A}+\lambda \mathbf{I}\right)^{-1} \mathbf{A}^{T} \mathbf{y}$
公式说我们试图最小化两者 $\|\mathbf {y}-\mathbf {A x}\| _ {2}^{2}$ 和 $\|\mathbf{x}\|_{2}^{2}$ , 和 $\lambda$ 控制在最小化中应该更强调哪一个

image.png

拟合曲线由 $\ell_{2}$ -正则化 LS 完成，猜测模型阶数为 n = 18，λ = 0.1。

第二部分：稀疏性

稀疏恢复问题

问题：给定 ${\mathbf {y} \in \mathbb{R} ^{m}}$ ， ${\mathbf {A} \in \mathbb {R} ^ {m*n}}$ ，m<n，找一个最稀疏的 ${\mathbf{x} \in \mathbb{R} ^{n}}$ ，使得y = Ax。

image.png

最稀疏，我们的意思是 x 应该有尽可能多的零元素。

稀疏优化公式

让
$\|\mathbf{x}\|_{0}=\sum_{i=1}^{n} \mathbb{1}\left\{x_{i} \neq 0\right\}$
表示基数函数
通常称为" $\ell_{0}$ 规范", 尽管它不是规范。
最小 $\ell_{0}$ 范数公式:
$\begin{aligned} &\min _ {\mathbf {x} \in \mathbb{R}^{n}}\|\mathbf{x}\|_{0} \\ &\text { s.t. } \mathbf{y}=\mathbf{A} \mathbf{x} \end{aligned}$
问题：假设 $\mathbf {y}=\mathbf {A} \overline{\mathbf{x}}$ , 其中 $\overline{\mathbf{x}}$ 是我们寻求恢复的向量。可以最小。 $\ell_{0}$ 规范问题以精确和独特的方式恢复 $\overline{\mathrm{x}}$ 。
答案在于火花的概念，它可以被视为对秩的强定义

火花

火花： $\mathbf {A}$ 的火花，用 $\operatorname{spark}(\mathbf{A})$ 表示，是 $\mathbf {A}$ 的最小线性相关列数。

令 $\operatorname {spark}(\mathbf{A})=k$ . 则 $k$ 是最小的数，使得存在线性相关的 $\left\{\mathbf{a}_{i_{1}}, \ldots, \mathbf{a}_{i_{k}}\right\}$ ，其中 $\left\{i_{1}, \ldots, i_{k}\right\} \subseteq\{1, \ldots, n\}^{1}$ .
令 $\operatorname{spark}(\mathbf{A})=r+1$ . 那么 $\left\{\mathbf{a}_{i_{1}}, \ldots, \mathbf{a}_{i_{r}}\right\}$ 对于任何 $\left\{i_{1}, \ldots, i_{r}\right\} \subseteq\{1, \ldots, n \}$
简单地说， $\mathbf {A}$ 的 $r$ 列的任何集合都是线性无关的。
与秩比较: 令 $\operatorname{rank}(\mathbf{A})=r$ (与上面的 $r$ 不同). 那么，对于某些 $\left\{\mathbf{a}_{i_{1}}, \ldots, \mathbf{a}_{i_{r}}\right\}$ ，存在线性无关的 $\left\{i_{1}, \ldots, i_{r}\right\} \subseteq\{1, \ldots, n\} .$
Kruskal 秩: 这是等级的另一种定义。T $\mathbf {A}$ ,的克鲁斯卡尔秩，用 $\operatorname {krank}(\mathbf{A})$ 表示，其定义等价于 $\operatorname {krank}(\mathbf{A})=\operatorname{spark}(\mathbf{A})-1$ 。
如果 $m$ 属于 $\left\{\mathbf{a}_{1}, \ldots, \mathbf{a}_{n}\right\} \subseteq \mathbb{R}^{m}$ , with $n>m$ ，线性无关, 那么
$\operatorname {spark} (\mathbf{A})=m+1, \quad \operatorname{rank}(\mathbf{A})=m$
一个例子是具有不同根的范德蒙德矩阵
一些专门设计的基地也有这个属性
但也存在排名和火花非常不同的情况
令 $\left \{\mathbf{v}_{1}, \ldots, \mathbf{v}_{r}\right\} \in \mathbb{R}^{m}$ 线性无关，令 $\mathbf{A}=\left[\mathbf{v}_{1}, \ldots, \mathbf{v}_{r}, \mathbf{v}_{1}\right]$ .
我们有 $\operatorname{rank}(\mathbf{A})=r$ ，但是 $\operatorname{spark}(\mathbf{A})=2$
总而言之，spark 可以被视为对等级的更强定义，并且
$\operatorname{spark}(\mathbf{A})-1 \leq \operatorname{rank}(\mathbf{A})$

最小的完美恢复保证- $\ell_{0}$ 范数问题

定理 6.1。假设 $\mathbf {y}=\mathbf{A} \overline{\mathbf{x}}$ 。那么， $\overline{\mathbf{x}}$ 是最小 $\ell_{0}$ 范数问题的唯一解，
$\|\overline{\mathbf{x}}\|_{0}<\frac{1}{2} \operatorname{spark}(\mathbf{A}) .$

含义：如果 $\overline{\mathrm{x}}$ 足够稀疏，那么最小 $\ell_{0}$ 范数问题完美地恢复了 $\overline{\bar{x}}$
证明草图：

让 $\mathrm{x}^{\star}$ 成为 $\min 的解。\ell_{0}$ 范数问题。令 $\mathrm{e}=\overline{\mathrm{x}}-\mathrm{x}^{\star}$ .
$\mathbf {0}=\mathbf{A} \overline{\mathbf{x}}-\mathbf{A} \mathbf{x}^{\star}=\mathbf{A e} ;\|\mathbf{e}\|_{0} \leq\|\overline{\mathbf{x}}\|_{0}+\left\|\mathbf{x}^{\star}\right\|_{0} \leq 2\|\overline{\mathbf{x}}\|_{0}$ 。
假设 $\mathbf{e} \neq \mathbf{0}$ 。然后， $\mathbf {A e}=\mathbf{0},\|\mathbf{e}\|_{0} \leq 2\|\overline{\mathbf{x}}\|_{0} \Longrightarrow \operatorname{spark}(\mathbf{A}) \leq 2\|\overline{\mathbf{x}}\|_{0}$

最小的完美恢复保证。 $\ell_{0}$ 范数问题

相干性： $\mathbf{A}$ 的相干性定义为
$\mu(\mathbf{A})=\max _{j \neq k} \frac{\left|\mathbf{a}_{j}^{T} \mathbf{a}_{k}\right|}{\left\|\mathbf{a}_{j}\right\|_{2}\left\|\mathbf{a}_{k}\right\|_{2}}$

衡量 $\mathbf{A}$ 的列在最坏情况下的相似程度。
定理 6.1 的弱版本：
推论 6.1。假设 $\mathbf {y}=\mathbf{A} \overline{\mathbf{x}}$ 。那么， $\overline{\mathbf{x}}$ 是最小 $\ell_{0}$ 范数问题的唯一解，如果
$\|\overline{\mathbf {x}}\|_{0}<\frac{1}{2}\left(1+\mu(\mathbf{A})^{-1}\right) .$
含义：完美的恢复可能取决于 $\mathbf{A}$ 的不连贯程度。
证明思路：证明 $\operatorname {spark}(\mathbf{A}) \geq 1+\mu(\mathbf{A})^{-1}$

关于求解最小 $\ell_{0}$ 范数问题

问题：我们应该如何解决最小 $\ell_{0}$ 范数问题
$\begin{aligned} &\min _{x}\|x\|_{0} \\ &\text { s.t. } y=A x \end{aligned}$
还是可以有效解决？

$\ell_{0}$ 范数最小化不会像 2 范数那样产生简单的解决方案。
最小的 $\ell_{0}$ 范数问题通常是 NP-hard。
这意味着什么？

给定任何 $\mathbf {y},\mathbf {A}$ ，该问题不太可能在多项式时间内完全解决（即，复杂性为 $\mathcal{O}\left(n^{p}\right)$ 对于任何 $p>0$ )

暴力搜索最小值 $\ell_{0}$ 范数问题

符号： $\mathbf{A}_{\mathcal{I}}$ 表示 $\mathbf{A}$ 的子矩阵，通过保留 $\mathcal{I}$ 指示的列获得
我们可以通过蛮力搜索解决 $\ell_{0}$ 范数最小化问题：

输入： $\mathbf{A}, \mathbf{y}$
对于所有 $\mathcal{I} \subseteq\{1,2, \ldots, n\}$ 做
$\quad$ 如果 $\mathbf{y}=\mathbf{A}_{\mathcal{I}} \tilde{\mathbf{x}}$ 有一些 $\tilde {\mathbf{x}} \in \mathbb{R}^{|\mathcal{I}|}$
$\quad$ $\quad$ 记录 $(\tilde{\mathbf{x}}, \mathcal{I})$ 作为候选解决方案之一
输出：一个候选解 $(\tilde{\mathbf{x}}, \mathcal{I})$ 其中 $|\mathcal{I}|$ 是最小的

例如：对于 $n=3$ ，我们测试 $\mathcal{I}=\{1\}, \mathcal{I}=\{2\}, \mathcal{I}=\{3\}, \mathcal{I}=\{1,2\}, \mathcal{I}=$ $\{2,3\}, \mathcal{I}=\{1,3\}, \mathcal{I}=\{1,2,3\}$
可以用非常小的 $n$ 来管理，即使是中等 $n$ 也太贵了
搜索较少的贪婪搜索怎么样？

贪婪的追求

考虑称为正交匹配追踪 (OMP) 的贪婪搜索

算法: OMP
输入: $\mathbf{A}, \mathbf{y}$
set $\mathcal{I}=\emptyset, \hat{\mathbf{x}}=\mathbf{0}$
repeat
$\quad \mathbf{r}=\mathbf{y}-\mathbf{A} \hat{\mathbf{x}}$
$k=\arg \max _{j \in\{1, \ldots, n\}}\left|\mathbf{a}_{j}^{T} \mathbf{r}\right| /\left\|\mathbf{a}_{j}\right\|_{2}$
$\mathcal{I}:=\mathcal{I} \cup \{k\}$
$\hat{\mathbf{x}}: =\arg _{\mathbf{x} \in \mathbb{R}^{n},} \min _{x_{i}=0 \forall i \notin \mathcal{I}}\|\mathbf{y}-\mathbf{A x}\|_{2}^{2}$
直到满足停止规则，例如 $\|\mathbf{y}-\mathbf{A x}\|_{2}$ 足够小
输出： $\hat{\mathbf{x}}$

注意：还有许多其他贪婪搜索策略

贪婪追击的完美恢复保障

再次，一个关键问题是 OMP 承认完全恢复的条件
有很多这样的理论条件，不仅对于OMP，对于其他贪婪算法也有
一个这样的结果如下：
定理 6.2。假设 $y=A \bar{x}$ 。然后，OMP 恢复 $\bar{x}$ 如果
$\| \overline {\mathbf {x} }\|_{0}< \frac {1}{2}\left( 1 + \mu(\mathbf {A})^{-1}\right)$
证明思路：证明 OMP 保证在每个阶段选择正确的列。

凸面收缩

另一种近似方法是将 $\|\mathrm{x}\|_{0}$ 替换为凸函数：
$\begin{aligned} &\min _{\mathbf{x}}\|\mathbf{x}\|_{1} \\ &\text { s.t. } \mathbf{y}=\mathbf{A} \mathbf{x} \end{aligned}$

在文献中也称为基础追求
凸，线性规划
没有封闭形式的解决方案（而最小 2 范数问题有）
但是这个最小 1 范数问题在理论和实践中的成功激发了大量的计算效率算法的工作

1-范数几何图解

image.png

图 A 显示了 $\mathbb{R}^{2}$ 中半径为 $r$ 的 1-范数球。请注意，1 范数球沿轴是“尖的”。
图 B 显示了 1-范数恢复解决方案。点 $\overline{\mathbf{x}}$ 是一个“稀疏”向量；行 $\mathcal{ H}$ 是所有满足 $\mathbf{y}=\mathbf{A} \mathbf{x}$ 的 $\mathbf{x}$ 的集合。

1-范数几何图解

image.png

1-范数恢复问题是在 $\mathcal{ H}$ 中挑出一个具有最小 1-范数的点。我们可以看到 $\overline{\mathbf{x}}$ 就是这样一个点。
图 C 显示了使用 2 范数时的几何形状。我们可以看到解 $\hat{\mathbf{x}}$ 可能不是稀疏的。

最小的完美恢复保证。 1-范数问题

再次，研究人员研究了最小 1-范数问题允许完美恢复的条件
这是一个令人兴奋的话题，具有许多可证明的条件，例如受限等距特性 (RIP)、零空间特性 (NSP)、...
有关详细信息，请参阅文献，这里有一个：[Yin'13]
一个简单的如下：
定理 6.3。假设 $y=A \bar{x}$ 。那么， $\bar{x}$ 是最小 1-范数问题的唯一解，如果
$\|\overline{\mathbf {x}}\|_{0}<\frac{1}{2}\left(1+\mu(\mathbf{A})^{-1}\right)$

玩具演示：稀疏信号重建

稀疏向量 $\mathbf {x} \in \mathbb{ R}^{n}$ 其中 $n=2000$ 和 $\|\mathbf{x}\|_{0}=50$ 。
$m=400$ $\mathbf{y}=\mathbf{A x} 的无噪声观测，a_{i j}$ 是随机生成的。

image.png

应用：压缩传感 (CS)

考虑一个信号 $\tilde{\mathbf {x}} \in \mathbb{R}^{n}$ 具有稀疏表示 $\mathbf {x} \in \mathbb { R}^{n}$ in $\boldsymbol{\Psi} \in \mathbb{R}^{n \times n}$ （例如 DCT 或小波）的域，即，
$\tilde{\mathbf{x}}=\Psi \mathbf{x}$
其中 $\mathbf{x}$ 是稀疏的。

image.png

左：原始图像 $\tilde{\mathbf {x}}$ 。右：小波域中对应的系数 $\mathrm{x}$ ，是稀疏的。资料来源：[Romberg-Wakin'07]

应用：CS

为了获得 $\mathbf{x}$ ，我们使用感知矩阵 $\boldsymbol{\Phi} \in \mathbb{R}^{m \times n}$ 来观察 $\mathbf{x}$
$y=\Phi \tilde{x}=\Phi \Psi x$
在这里，我们有 $m \ll n$ ，即比 no 少得多的观察值。未知数
这样的 y 将有利于压缩、传输和存储。
$\tilde{\mathbf {x}}$ 通过恢复 $\mathrm{x}$ 来恢复：
$\begin{aligned} &\min \|\mathrm{x}\|_{0} \\ &\text { s.t. } \mathrm{y}=\mathrm{Ax} \end{aligned}$
其中 $\mathbf{A}=\mathbf{\Phi} \boldsymbol{\Psi}$
如何选择 $\Phi$ ？ CS 研究表明 i.i.d. 随机 $\Phi$ 会很好用！

image.png

变化

当 $\mathbf{y}$ 被噪音污染时，或者当 $\mathbf {y}=\mathbf{A x}$ 不完全成立时，前一分钟的一些变体。可以考虑使用 1范数公式：
基础追求去噪：给定 $\epsilon>0$ ，求解
$\min _{\mathbf{x}}\|\mathbf{x}\|_{1} \quad \text { s.t. }\|\mathbf{y}-\mathbf{A} \mathbf{x}\|_{2}^{2} \leq \epsilon$
$\ell_{1}$ -regularized LS：给定 $\lambda>0$ ，求解
$\min _{\mathbf{x}}\|\mathbf{y}-\mathbf{A} \mathbf{x}\|_{2}^{2}+\lambda\|\mathbf{x}\|_{1}$
套索：给定 $\tau>0$ ，求解
$\min _{\mathbf{x}}\|\mathbf{y}-\mathbf{A} \mathbf{x}\|_{2}^{2} \quad \text { s.t. }\|\mathbf{x}\|_{1} \leq \tau$
当 $\mathbf{y}$ 中存在异常值时（即 $\mathbf{y}$ 的某些元素严重损坏），我们还希望残差 $\mathbf{r}=\mathbf{y}-\mathbf {A x}$ 是稀疏的；所以，
$\min _{\mathbf{x}}\|\mathbf{y}-\mathbf{A} \mathbf{x}\|_{1}+\lambda\|\mathbf{x}\|_{1} .$

矩阵论-lecture 6-LS

ENGG5781 矩阵分析和计算

第 6 课：重新审视最小二乘法

第 6 课：重新审视最小二乘法

第一部分：正则化

对噪音的敏感性

玩具演示：曲线拟合

$\ell_{2}$ -正则化 LS

第二部分：稀疏性

稀疏恢复问题

稀疏优化公式

火花

最小的完美恢复保证- $\ell_{0}$ 范数问题

最小的完美恢复保证。 $\ell_{0}$ 范数问题

关于求解最小 $\ell_{0}$ 范数问题

暴力搜索最小值 $\ell_{0}$ 范数问题

贪婪的追求

贪婪追击的完美恢复保障

凸面收缩

1-范数几何图解

1-范数几何图解

最小的完美恢复保证。 1-范数问题

玩具演示：稀疏信号重建

应用：压缩传感 (CS)

应用：CS

变化

猜你喜欢

热点阅读

矩阵论-lecture 6-LS

ENGG5781 矩阵分析和计算

第 6 课：重新审视最小二乘法

第 6 课：重新审视最小二乘法

第一部分：正则化

对噪音的敏感性

玩具演示：曲线拟合

-正则化 LS

第二部分：稀疏性

稀疏恢复问题

稀疏优化公式

火花

最小的完美恢复保证- 范数问题

最小的完美恢复保证。 范数问题

关于求解最小范数问题

暴力搜索最小值 范数问题

贪婪的追求

贪婪追击的完美恢复保障

凸面收缩

1-范数几何图解

1-范数几何图解

最小的完美恢复保证。 1-范数问题

玩具演示：稀疏信号重建

应用：压缩传感 (CS)

应用：CS

变化

猜你喜欢

热点阅读

$\ell_{2}$ -正则化 LS

最小的完美恢复保证- $\ell_{0}$ 范数问题

最小的完美恢复保证。 $\ell_{0}$ 范数问题

关于求解最小 $\ell_{0}$ 范数问题

暴力搜索最小值 $\ell_{0}$ 范数问题