CS205A Lecture 4 Designing linear systems (incl. least-squares); special structure (Cholesky, sparsity)

课程主页:https://graphics.stanford.edu/courses/cs205a-13-fall/schedule.html

这次回顾第四讲,这一讲结束了LU分解的内容,介绍敏感性和病态性。

Chapter 3 设计和分析线性系统

回归

假设我们的函数有如下形式

如果我们有$m$个观测值,那么可以得到如下线性系统:

我们的任务是求解$(a_1,…,a_m)^T$,在继续之前,来看两个具体例子:

多项式回归

如果

那么此时称为多项式回归,对应的线性系统为:

Mini-Fourier

另一种常见的形式为

最小二乘法

考虑上述问题,我们自然希望

这等价于

最小化上述问题等价于最小化

化简可得

对上式关于$\vec x ​$求梯度可得

令上式为$0$可得

该方程被称为正规方程,下面对$A^TA​$这个矩阵做更多的讨论。

(半)正定矩阵和Cholesky分解

讨论之前先介绍一些基本概念:

对称性

显然$A^TA$是对称矩阵。

(半)正定性

注意到

所以$A^TA$是半正定矩阵,事实上,如果$A$可逆,那么$A^TA$是正定矩阵。

有了这些准备工作,考虑正定对称系统$C\vec x = \vec d$的求解,假设$C\in \mathbb R^{n\times n}$且$C$是对称矩阵,将$C$写为分块形式:

其中$\vec v \in \mathbb R^{n-1}, \tilde C \in\mathbb R^{(n-1)\times (n-1)} $。由$C​$的定义,不难得到:

其中最后一个不等号是因为正定性。回顾高斯消元法,这说明我们不需要对第一列选主元,那么使用高斯消元法,我们可以找到forward substitution矩阵$E​$,其中

使得

其中$ D \in\mathbb R^{(n-1)\times (n-1)} $。接着,由$C$的对称性,考虑使用列变换:

不难发现$D$也是正定对称矩阵,对$D$重复这个过程,最终不难得到

那么

注意到上述$L$并不唯一——对于正交矩阵$Q$,我们有

所以上述分解有无数种形式,特别的,如果我们取$L$为下三角矩阵,那么

被称为Cholesky分解,下面推导Cholesky分解的具体形式。

由定义,我们有

考虑$C_{ij}$,我们有

所以

以及

所以,对$i,j​$做循环即可计算得到$L_{ij}​$,伪代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// Takes as input an n-by -n matrix A[i,j]
// Edits A in place to obtain the Cholesky factorization in its lower triangle
for i from 1 to n {
// Back - substitute to find l_i
for j from 1 to i -1 { // element j of l_i
sum = 0;
for k from 1 to j -1
sum += A[i,k]*A[j,k];
A[i,j] = (A[i,j]-sum )/A[j,j];
}
// Apply the formula for l_kk
normSquared = 0
for k from 1 to i -1
normSquared += A[i,k ]^2;
A[i,i] = sqrt (A[i,i] - normSquared );
}

本文标题:CS205A Lecture 4 Designing linear systems (incl. least-squares); special structure (Cholesky, sparsity)

文章作者:Doraemonzzz

发布时间:2019年03月20日 - 22:26:00

最后更新:2019年03月24日 - 00:42:33

原始链接:http://doraemonzzz.com/2019/03/20/CS205A Lecture 4 Designing linear systems (incl. least-squares); special structure (Cholesky, sparsity)/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。