KC通过线性变换降维的原理剖析 假设是一个摄像机采集一个物体运动得到的图片，上面的点表示物体运动的位 置，假如我们想要用一条直线去拟合这些点，那我们会选择什么方向的线呢？ 如果把这些点单纯的投影到x轴或者y轴上，最 后在x轴与y轴上得到的方差是相似的（因为这 ignal .2 些点的趋势是在45度左右的方向，所以投影到 x轴或者y轴上都是类似的)，看不出来这些点 真正的方向是什么。但若进行坐标系的变化， 横轴变成了signal的方向，纵轴变成了noisel的 方向，则就很容易发现什么方向的方差大，什 么方向的方差小了。 PCA(Principle Component Analysis)就是对原始的空间中顺序地找一组相互正交 的坐标轴，第一个轴是使得方差最大的，第二个轴是在与第一个轴正交的平 面中使得方差最大的，第三个轴是在与第1、2个轴正交的平面中方差最大的， 这样假设在N维空间中，我们可以找到N个这样的坐标轴，我们取前个去近似 这个空间，这样就从一个N维的空间压缩到维的空间了，但是我们选择的个 坐标轴能够使得空间的压缩使得数据的损失最小。 ynh,cxh @ustc.edu.cn
{ynh,cxh}@ustc.edu.cn 通过线性变换降维的原理剖析 假设是一个摄像机采集一个物体运动得到的图片，上面的点表示物体运动的位 置，假如我们想要用一条直线去拟合这些点，那我们会选择什么方向的线呢？ PCA(Principle Component Analysis)就是对原始的空间中顺序地找一组相互正交 的坐标轴，第一个轴是使得方差最大的，第二个轴是在与第一个轴正交的平 面中使得方差最大的，第三个轴是在与第1、2个轴正交的平面中方差最大的， 这样假设在N维空间中，我们可以找到N个这样的坐标轴，我们取前r个去近似 这个空间，这样就从一个N维的空间压缩到r维的空间了，但是我们选择的r个 坐标轴能够使得空间的压缩使得数据的损失最小。 如果把这些点单纯的投影到x轴或者y轴上，最 后在x轴与y轴上得到的方差是相似的（因为这 些点的趋势是在45度左右的方向，所以投影到 x轴或者y轴上都是类似的），看不出来这些点 真正的方向是什么。但若进行坐标系的变化， 横轴变成了signal的方向，纵轴变成了noise的 方向，则就很容易发现什么方向的方差大，什 么方向的方差小了
MC 什么样的变换是最佳的？ K-L变换 ◆卡洛南-洛伊变换 Karhunen-Loeve Transform ◆定义 ▣以矢量信号X的协方差矩阵Φ的归一化正交特征矢量q所 构成的正交矩阵Q,来对该矢量信号X做正交变换Y=QX, 则称此变换为K-L变换(K-LT或KLT) 口可见，要实现KLT,首先要从信号求出其协方差矩阵Φ， 再由Φ求出正交矩阵Q。Φ的求法与自相关矩阵求法类似。 ◆缺点 ▣无快速算法，且变换矩阵随不同的信号样值集合而不同 12 ynh.cxh @ustc.edu.cn
{ynh,cxh}@ustc.edu.cn 什么样的变换是最佳的？ K-L变换 卡洛南-洛伊变换 Karhunen-Loève Transform 定义 以矢量信号X的协方差矩阵Ф的归一化正交特征矢量q所 构成的正交矩阵Q，来对该矢量信号X做正交变换Y=QX， 则称此变换为K-L变换（K-LT或KLT）。 可见，要实现KLT，首先要从信号求出其协方差矩阵Ф， 再由Ф求出正交矩阵Q。Ф的求法与自相关矩阵求法类似。 缺点 无快速算法，且变换矩阵随不同的信号样值集合而不同 12
KC优化问题(Optimization problems) ◆目标函数 f6x划 Source:《Convex Optimization》,Stephen Boyd Chapter 4 Convex optimization problems ◆不等式约束 f(),i=1,....m ◆等式约束 hx),i=1,…p We use the notation minimize fo(z) subject to f(r)≤0，i=1,.,m (4.1) h(x)=0,i=1,..,p to describe the problem of finding an x that minimizes fo(c)among all r that satisfy the conditions fi(x)≤0，i=1,.,m,andh(x)=0,i=1,.,p.We call x∈R” the optimization variable and the function fo:R"-R the objective function or cost function.The inequalities fi(r)<0 are called inequality constraints,and the corresponding functions fi:R"-R are called the inequality constraint functions. The equations hi(x)=0 are called the equality constraints,and the functions hi:R"-R are the equality constraint functions.If there are no constraints (i.e., m =p=0)we say the problem (4.1)is unconstrained
{ynh,cxh}@ustc.edu.cn 优化问题（Optimization problems） 目标函数 f0 (x) 不等式约束 f i (x), i=1,…,m 等式约束 hi (x) , i=1,…,p Source: 《Convex Optimization》,Stephen Boyd Chapter 4 Convex optimization problems
KC拉格朗日对偶 Source:《Convex Optimization》,Stephen Boyd Chapter 4 Convex optimization problems minimize fo(x) subject to f(c)≤0， i=1,.,m h(c)=0,i=1,.,p, The basic idea in Lagrangian duality is to take the constraints into account by augmenting the objective function with a weighted sum of the constraint functions. L(c,入，w)）=fo(c)+f(c)+∑yh(u) i=1 i=1 The vectors A and y are called the dual variables or Lagrange multiplier vectors associated with the Problem. a=geA=骂(o+ite+2wkae） du.cn
{ynh,cxh}@ustc.edu.cn 拉格朗日对偶 The basic idea in Lagrangian duality is to take the constraints into account by augmenting the objective function with a weighted sum of the constraint functions. The vectors λ and ν are called the dual variables or Lagrange multiplier vectors associated with the Problem. Source: 《Convex Optimization》,Stephen Boyd Chapter 4 Convex optimization problems
MC 什么样的变换是最佳的？ 思路：寻找使数据方差最大的变换 Principle Component Analysis(PCA) Karhunen-Loeve transformation(KL transformation) 找一组合适的变换基，使得变换后的数据有着最大的方差 ◆Let Anxm是数据矩阵，每一行代表一个数据样本 Projection of data along w is Aw. Variance:o2=(Aw)T(Aw)=wTATAw=wTCw where C=ATA is the covariance matrix of the data (A is centered!) c- 1 Task:maximize variance subject to constraint wTw=1. Maximize fwTCw-(wTw-1),A is the Lagrange multiplier ynh,cxh @ustc.edu.cn
{ynh,cxh}@ustc.edu.cn 什么样的变换是最佳的？ 思路：寻找使数据方差最大的变换 Principle Component Analysis (PCA) Karhunen-Loeve transformation (KL transformation) Let An×m 是数据矩阵，每一行代表一个数据样本 Projection of data along w is Aw. Variance: σ 2 w= (Aw)T(Aw) = wTATAw = wTCw where C = ATA is the covariance matrix of the data (A is centered!) Task: maximize variance subject to constraint wTw=1. Maximize f=wTCw - λ(wTw - 1), λ is the Lagrange multiplier 找一组合适的变换基，使得变换后的数据有着最大的方差