矩阵论-lecture 6-LS

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}}
  • 证明草图：
  1. 让 \mathrm{x}^{\star} 成为 \min 的解。\ell_{0}范数问题。 令 \mathrm{e}=\overline{\mathrm{x}}-\mathrm{x}^{\star}.
  2. \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}。
  3. 假设\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
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} .
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 213,558评论 6赞 492
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 91,002评论 3赞 387
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 159,036评论 0赞 349
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 57,024评论 1赞 285
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 66,144评论 6赞 385
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 50,255评论 1赞 292
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,295评论 3赞 412
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 38,068评论 0赞 268
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,478评论 1赞 305
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,789评论 2赞 327
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,965评论 1赞 341
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 34,649评论 4赞 336
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,267评论 3赞 318
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,982评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,223评论 1赞 267
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 46,800评论 2赞 365
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 43,847评论 2赞 351

推荐阅读更多精彩内容