最小二乘法及其应用幻灯片.ppt

《最小二乘法及其应用幻灯片.ppt》由会员分享，可在线阅读，更多相关《最小二乘法及其应用幻灯片.ppt（76页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、最小二乘法及其应用最小二乘法及其应用第1页，共76页，编辑于2022年，星期六 最小二乘法是求解最优化问题的一种有效而方便的方法。信号处理中有许多问题可归结为最优化问题，因此最小二乘法是信号处理的重要工具之一。希尔伯特空间中线性逼近问题的求解方法称为最小二乘法。通常它有三种不同的表现形式：投影法、求导法和配方法。下面来分别说明。3-1 最小二乘法的三种形式最小二乘法的三种形式第2页，共76页，编辑于2022年，星期六 设X为希尔伯特空间，为X中一组归一化正交元素，x为X中的某一元素。在子空间 中求一元素m。使得（3-1-1）由于M中元素可表为 的线性组合，问题转化成为求 ，使得（3-1-2）第

2、3页，共76页，编辑于2022年，星期六 第二章中的投影定理指出了最优系数 应满足（3-1-3）由此即得 。也就是说，当且仅当 取为x关于归一化正交系 的傅立叶系数时，式(3-1-2)成立。（3-1-4）第4页，共76页，编辑于2022年，星期六 这种求解方法称为投影法，它是最小二乘法的第一种表现形式。第二种方法是求导法，仍以上面的问题为例来说明。记泛函为了能用求导法求此泛函的极小值，将它表为第5页，共76页，编辑于2022年，星期六其中 。于是最优的 应满足即 下面再用第三种方法即配方法来求解：（3-1-5）第6页，共76页，编辑于2022年，星期六 以上三种方法都称为最小二乘法。在实际应用

3、中，他们各有各的优势和缺陷，我们并不能通过简单的比较来说明他们谁优谁劣，因为衡量一种方法好坏的标准是多方面的。因此，在不同的场合根据不同的需要和可能，灵活选择和使用合适的方法，是掌握最小二乘法的关键。第7页，共76页，编辑于2022年，星期六 利用令导数等于零来求函数的极值是一种方便的方法。但是对于多元函数，有时由于变元太多而使表达式相当繁复，为此，本节介绍用向量-矩阵的形式来简化求导过程。下面举例个例子来具体说明。例3-2-1 求矛盾方程组Ax=b的最小二乘 解（可参阅第二章的相关例题）3-2 向量向量-矩阵求导及配方法矩阵求导及配方法第8页，共76页，编辑于2022年，星期六 解：解：求A

4、x=b的最小二乘解就是求 的极小点。由于下面先给出两个需要用到的向量求导公式：（3-2-1）（3-2-2）当A不时对称阵时，式（3-2-10）应该为（3-2-3）第9页，共76页，编辑于2022年，星期六利用式（3-2-1）和（3-2-2）可以立即得到（3-2-4）这就是书中例2-4-1中所得到的法方程若使用配方法，则有：第10页，共76页，编辑于2022年，星期六可以看出，本例中介绍的两个向量求导公式中，提到了对于向量x求导的梯度算符 ,我们还可以引入对矩阵 求导的梯度算符 ：（3-2-5）第11页，共76页，编辑于2022年，星期六需要说明的是，算符 只有作用在关于 的标量函数上才有意义。

5、例如对于二次型由于 ，故（3-2-6）（3-2-7）在课本中，给出了一些常用的向量-矩阵求导公式，在实际应用中可供大家查阅。第12页，共76页，编辑于2022年，星期六 设有如图3-3-1所示的系统T。当输入n个数据 时，输出为y，且有下列线性关系：3-3 应用举例应用举例3-3-1 系统辨识系统辨识（3-3-1）其中 为未知，需要通过对输入输出的观测值来确定这组参数。第13页，共76页，编辑于2022年，星期六 现设进行了m次观测，观测值为 和 图3-3-1 多输入单输出系统则问题成为求 使之满足（3-3-2）第14页，共76页，编辑于2022年，星期六若记 及则方程（3-3-2）成为（3-

6、3-3）当方程（3-3-3）无解时，问题就转化为求矛盾方程组的最小二乘解。可以得到（3-3-4）第15页，共76页，编辑于2022年，星期六进而考察多输入多输出的情形。关系式为其中（3-3-6）（3-3-5）现设输入和输出的第k次观测值分别是 第16页，共76页，编辑于2022年，星期六则系统的辨识问题就是求A使之满足（3-3-8）（3-3-7）其中Y为 矩阵，X为 矩阵。当上述方程无解时，问题就转化成为求A使下列非负定矩阵达到极小：（3-3-9）第17页，共76页，编辑于2022年，星期六问题（3-3-9）可以用配方法来求解：（3-3-10）其中假定 可逆。这个问题不能用求导法来求解，因为目

7、标函数J（A）不是标量而是矩阵。要用求导法来求解该问题，需要引入矩阵范数的概念。第18页，共76页，编辑于2022年，星期六矩阵 的范数定义为（3-3-11）事实上，可以把式（3-3-11）理解成向量 的范数。这样，我们可以把多输入多输出线性系统的辨识问题叙述为求 矩阵A，使得（3-3-12）第19页，共76页，编辑于2022年，星期六式（3-3-12）的形式与（3-3-9）类似，但应注意在此处 是标量函数。她可以完全类似于式（3-3-10）那样来配方而求解，也可体用求导法来求解。由于（3-3-13）利用课本中表3-2-2中的公式5和7，得到（3-3-14）第20页，共76页，编辑于2022年

8、，星期六 数据压缩是指在传输或存储信号时对信号数据量进行压缩。实际中的信号往往都是维数很高的随机数据向量。各种数据间的相关性也很大，简单的随意压缩会导致数据严重失真。按照最优化原则设计的数据压缩技术可以解决通讯和数据传输系统的信道容量不足和计算机存储容量不足的问题，因而是一种从容量方面提高系统使用效率的重要技术。3-3-2 数据压缩数据压缩第21页，共76页，编辑于2022年，星期六下面向大家介绍一种有效的数据压缩方法。其思想是对信号作正交变换，根据失真最小的原则在变幻域进行压缩。其框图如下所示。设 为n维随机变量，n的值很大。经过正交T变换后，得到变幻域的n维向量（3-3-15）第22页，共

9、76页，编辑于2022年，星期六其中变幻矩阵T的列向量为满足（3-3-16）（3-3-17）现在对数据进行压缩，即保留y的m个分量其余的n-m个分量用预先选定的常数 代，替，得到一个新的向量，再由 通过逆变换 得到x的估计第23页，共76页，编辑于2022年，星期六我们的问题是：如何选取变幻矩阵T和常数 ，y的那些分量被压缩掉，才能使 最接近x，即均方误差最小：（3-3-18）下面来注意解决这些问题。由式（3-3-15）和式（3-3-16）可知第24页，共76页，编辑于2022年，星期六由此式可知，要使 达到最小，应有（3-3-19）（3-3-20）即这就使常数 应选取的数值。由此式得（3-3

10、-21）第25页，共76页，编辑于2022年，星期六其中 是随机向量x的协方差阵。由式（3-3-22）可考虑如何选择T的行向量使 达到极小。注意到 是归一化正交的。为求 在条件 下的极值，令代入式（3-3-19），得到（3-3-22）第26页，共76页，编辑于2022年，星期六这表明 是协方差阵 的特征值，而 是相应的特征向量，很显然,T取成x的卡享南-洛厄维变换是最合理的，此时的最小均方误差为则由式（3-3-22），有于是（3-3-23）第27页，共76页，编辑于2022年，星期六根据此式，我们可先把非负定矩阵 的特征值按大小次序排列，然后根据实际问题对均方误差的要求选择m，使得 小于指定的

11、误差（即选择满足此条件的最小的m），把n-m个较小的特征值 所对应的 换成 。（3-3-24）第28页，共76页，编辑于2022年，星期六特别地，如果取Ex=0(通常的信号经过预处理后可满足此条件），则取 ，至此，前面提出的问题便全部解决。在上述解法中，卡享南-洛厄维变换被选用并不是偶然的，因为这种变换消除了原始信号x的诸分量间的相关性，从而使数据压缩能遵循均方误差最小的准则实施。上述数据压缩方法告诉我们应该压缩掉y中那些方差大的分量，这称为数据压缩的方差准则。第29页，共76页，编辑于2022年，星期六 由于卡享南-洛厄维变换需要知道矩阵的特征值和特征向量，其计算量非常大，因此在实际应用中通

12、常都使用固定程式的有限正交变换。尽管这些变换不是最佳的，但实践和理论表明它们也都能在较大程度上消除随机向量诸分量间的相关性，而且由于它们具有快速算法，因而是实用的。卡享南-洛厄维变换是理论上的最佳变换，它可作为理论研究的工具，也可用来衡量其他变换优劣的标准。第30页，共76页，编辑于2022年，星期六 设有随机向量 ，它含有真实信号 及噪声 ，如下述模型所示：3-3-3 维纳滤波维纳滤波（3-3-25）其中H为已知 矩阵，它也表示一种干扰。现在将x输入到一个如下图所示的系统第31页，共76页，编辑于2022年，星期六要使相应的输出 成为真实信号s的最佳估计，即均方差最小：求滤波器矩阵A，其中T

13、是正交变换。（3-3-26）这个问题称为维纳(Wiener)滤波器设计问题。正交变换T的作用是把滤波问题转化到变换域处理。由系统框图知于是（3-3-27）第32页，共76页，编辑于2022年，星期六利用表3-2-2中的公式2和3，得到因此最佳滤波器矩阵A应满足（3-3-28）当 可逆时（3-3-29）第33页，共76页，编辑于2022年，星期六设信号与噪声的均值为零：Ex=0；Ev=0；真实信号与噪声不相关：；并记真实信号s与噪声v的自相关矩阵为则第34页，共76页，编辑于2022年，星期六于是式（3-3-29）便成为这就是维纳滤波器矩阵。（3-3-30）下面再用配方法来解决此问题。为此，用矩

14、阵的迹来表示 是有效的。第35页，共76页，编辑于2022年，星期六又一次得到了式（3-3-29），而且得到了最小误差：（3-3-31）第36页，共76页，编辑于2022年，星期六注意到 的表达式中不出现正交变换T，由此可知维纳滤波与正交变换的选取无关。于是由式（3-3-30）联想到若取T使得矩阵A呈对角型，则将使矩阵乘向量的计算量由 降低到n。这种想法是有实际意义的。如在图象处理中，（3-3-25）是一个典型的失真模型。若选T为傅立叶变换，则A便成为对角型矩阵。这样的维纳滤波器称为对角线维纳滤波器。第37页，共76页，编辑于2022年，星期六 模式识别问题是设计一种分类器，使之能自动地将类别

15、未知的对象进行归类。需要归类的对象称为模式。本节来介绍模式分类器的一种设计方法。一个需要识别的对象可以用向量来表示。下面的分类器的设计是对压缩后的模式向量进行的。3-3-4 模式识别模式识别第38页，共76页，编辑于2022年，星期六分类器的设计是通过下列方式（称为训练或学习）来完成的。被识别的对象共有k类：。首先选取一些类别已知的模式向量（称为训练模式）求属于同一类 的模式向量的平均模式：那么，对于任一类别未知的模式向量x，判决准则是第39页，共76页，编辑于2022年，星期六 称为判决函数。根据判决准则(3-3-33)实现分类的分类器称为最小距离分类器。由于实际问题中属同一类的模式往往分布

16、的很分散和凌乱，直接采用 这种线性函数作为判决界容易造成误判。（3-3-32）由于若记则判决准则等价于若（3-3-33）第40页，共76页，编辑于2022年，星期六为了克服上述缺点，可采用如下所述的最小二乘映射技术。取定k个向量 。希望存在一个线性变换A（矩阵）把属于同一类 的训练模式 ，都变为 ：于是问题转化为求矩阵A，它能够把 都变到 的附近，越近越好。记第41页，共76页，编辑于2022年，星期六则矩阵A关于第i类训练模式的平均偏差为总偏差为于是A的选取应使 ，故A应满足（3-3-34）第42页，共76页，编辑于2022年，星期六因此（3-3-35）求出A以后，对于任一类别未知的模式x，

17、可如下述进行判决归类：（3-3-36）第43页，共76页，编辑于2022年，星期六这种分类判决的实现称为最小二乘最小距离分类器。它的主要思想是利用最小二乘映射把属于同一类的训练模式尽可能地聚集在一起。从而克服了最小距离分类器的缺点。在这里所有 都是可以任意选择的，可以通过选择特殊的 ，简化判决函数的获得过程。在课本中就给出了一种简化方法。其中取 为K维单位向量第44页，共76页，编辑于2022年，星期六 可以看出，最小二乘最小距离分类器的判决函数仅依赖于最优矩阵A。一旦求出A，立即就可实现这种分类器。在实际应用中此方法的设计技巧是选取合适的判决向量 。第45页，共76页，编辑于2022年，星期

18、六 设X为希尔伯特空间，是X中的一组线性无关元（不一定正交）。对某一 ，求 ，使得3-4 法方程法方程（3-4-1）换言之，求系数 ，使得（3-4-2）第46页，共76页，编辑于2022年，星期六这就是最优系数 应满足的方程，它是一个线性代数方程组。具体写出来是利用投影定理，应满足即（3-4-3）（3-4-4）第47页，共76页，编辑于2022年，星期六矩阵Y就是元素组 的格拉姆矩阵。它是非负定的，且当 线性无关时Y可逆。方程（3-4-4）称为Wiener-Hopf方程。一般地，一个最优化解应满足的方程称为该最优化问题的法方程。因此Wiener-Hopf方程是最优化问题（3-4-2）的法方程。

19、或写成矩阵-向量形简洁形式：（3-4-5）第48页，共76页，编辑于2022年，星期六 现设 是最优系数，即满足（3-4-3），这时的最小误差为：（3-4-6）把这个方程合并到方程组（3-4-4）中去，成为第49页，共76页，编辑于2022年，星期六其中detG表示矩阵G的行列式。用克莱姆法则即可求得最小误差为（3-4-7）第50页，共76页，编辑于2022年，星期六 特别地，如果 为归一化正交系，则 为单位矩阵，式（3-4-4）成为 ，式（3-4-7）成为 上述问题利用求导法也可以解。由式（3-4-2），有第51页，共76页，编辑于2022年，星期六利用求导公式，应满足此即式（3-4-5）若

20、用配方法，则有易知它与式（3-4-6）是等价的。第52页，共76页，编辑于2022年，星期六下面，我们再来讨论一个随机序列的预测问题，来进一步说明法方程的意义考虑二阶矩有限的希尔伯特空间 中的序列 。记子空间（3-4-8）现在的问题是：用 中的元素来估计 ，使得均方误差最小。也就是求系数 使第53页，共76页，编辑于2022年，星期六这个问题称为随机序列的预测问题。（3-4-9）根据投影定理，应是 在子空间中的投影，即 满足（3-4-10）根据空间 中的正交性定义，上式即为这就是最佳预测的法方程。第54页，共76页，编辑于2022年，星期六其中 是该平稳序列的自相关。它满足 。（3-4-11）

21、又称为关于平稳序列 预测问题的Yule-Walker方程。其分量形式为如果随机序列 是平稳的，则式（3-4-10）成为（3-4-11）第55页，共76页，编辑于2022年，星期六（3-4-12）相应的预测误差为第56页，共76页，编辑于2022年，星期六把这个方程合并到方程（3-4-12）中去，可以写成记其系数矩阵为 。利用克莱姆法则可得（3-4-13）（3-4-14）第57页，共76页，编辑于2022年，星期六 对于给定的序列x和y，求一个离散时不变系统h，使得当输入为x时相应的输出恰为y。这个问题的数学描述是：给定x和y，求h使得3-4 最小二乘滤波最小二乘滤波（3-5-1）一般来说，这个

22、问题不一定是有解的，因此将问题改成：已知x，y，求h使得（3-5-2）第58页，共76页，编辑于2022年，星期六我们假定x，y，h都是因果的，能量有限的于是x，y，h ，式（3-5-2）中的范数是 意义下的范数。这个问题称为最小二乘滤波问题。我们先用求导法来解。由知目标函数为第59页，共76页，编辑于2022年，星期六于是最优解 应满足即若记它们分别称为x的自相关序列和x与y的互相关序列。则式（3-5-3）成为（3-5-3）第60页，共76页，编辑于2022年，星期六这就是最小二乘滤波的法方程。下面再利用投影法来求解最小二乘滤波问题。在空间 中讨论。对于引入移位算子T：（3-5-4）则第61

23、页，共76页，编辑于2022年，星期六这样，就把卷积表示成 中一组元素 的线性组合，这是应用投影法的关键。记子空间 。问题便转化为求 ，使 ，也就是求y在M中的投影。根据投影定理，应满足 即（3-5-5）第62页，共76页，编辑于2022年，星期六因此式（3-5-5）就是法方程（3-5-4）。接下来我们介绍两个实际应用的例子。其中同理第63页，共76页，编辑于2022年，星期六 仍然考虑因果序列。设 是原始声音信号序列。由于回声的影响，在n时刻接收到的信号 除了 以外还叠加有 时刻之前的回音：例例 3-5-1回声干扰与最小二乘逆滤波（3-5-6）其中r是衰减因子，。现在要求设计一个系统 能够消

24、除这种回声干扰，即（3-5-7）第64页，共76页，编辑于2022年，星期六我们把式（3-5-6）写成卷积形式：其中 为（3-5-8）将式（3-5-8）代入式（3-5-7）得这等价于（3-5-9）其中 是单位脉冲序列。第65页，共76页，编辑于2022年，星期六于是问题转化成给定x，要求设计一个系统h，使之满足式（3-5-9）。这是一个特殊的最小二乘滤波问题，称为最小二乘逆滤波。利用法方程（3-5-4），取 ，即得（3-5-10）而根据序列x的因果性，有第66页，共76页，编辑于2022年，星期六如果把方程（3-5-10）中的m截断到N为止，则成为（3-5-11）这就是最小二乘逆滤波的“N截断

25、”法方程，它适合于实际计算。第67页，共76页，编辑于2022年，星期六 所谓预测就是由 的值预测 的值，其中s为某个自然数。预测滤波问题就是要求设计一个系统h，使得当输入为 时相应的输出为 。这也是一种特殊的最小二乘滤波。根据法方程（3-5-4），只需计算 ：例例 3-5-2最小二乘预测滤波第68页，共76页，编辑于2022年，星期六于是式（3-5-4）成为这就是最小二乘滤波器 应满足的法方程。其N截断形式为（3-5-12）（3-5-13）第69页，共76页，编辑于2022年，星期六进而，考虑这种预测的误差：其中 满足法方程（3-5-12）。为了方便，将上式中的n+s换成n：它又可表为（3-

26、5-14）（3-5-15）其中第70页，共76页，编辑于2022年，星期六这样，对于满足最小二乘滤波器法方程（3-5-13）的 ，当x输入到系统h时，输出为x的将来估计值，而当x输入到系统 时，相应的输出便是这种预测的误差估计。最后，我们研究最小二乘滤波法方程的N截断的收敛性问题。第71页，共76页，编辑于2022年，星期六法方程（3-5-4）的N截断方程为设其解为 ，则显然是y在子空间 中的投影。记 。由于 ，故（3-5-16）第72页，共76页，编辑于2022年，星期六再记 为y在子空间 中的投影：（3-5-17）其中 即为法方程（3-5-4）的解。记由于 ，故存在 使（3-5-18）第73页，共76页，编辑于2022年，星期六由于 是y在 中的最佳逼近元，故令 ，得（3-5-19）再根据式（3-5-17）及 即有（3-5-20）由式（3-5-19）和（3-5-20）有（3-5-21）第74页，共76页，编辑于2022年，星期六我们知道，当误差 时，即 此时，本节开头所提出的问题“给定设计一个系统h，使得当输入为x时，输出为y”必定有解，而N截断方程（3-5-16）的解随着N的增大趋于此理想值。式（3-5-21）表明，在下列意义下N截断方程的解趋于最优解：理想情况第75页，共76页，编辑于2022年，星期六第76页，共76页，编辑于2022年，星期六