《速下降法》PPT课件.ppt

第二讲 最速下降算法,Y.J.Pang,自适应信号处理,2,最速下降法（method of steepest descent）是一种基于梯度的自适应方法。 最速下降法可用反馈系统来表示，滤波器的计算式一步一步迭代进行的。从该意义上讲，最速下降法是递归的。 在适当条件下，最速下降法的解收敛于维纳解而不需要求输入向量相关矩阵的逆矩阵。,自适应信号处理,3,线性最优滤波：问题综述,自适应信号处理,4,这里滤波器需要两个约束条件： 1.滤波器是线性的 2.滤波器是离散时间的 滤波器的具体实现依赖的两个选择： 1.滤波器的冲激响应选择 （FIR,IIR) 2.统计优化准则的选择问题 1）估计误差的均方值 2）估计误差的绝对值期望值 3）估计误差的绝对值的三阶或高阶期望值,自适应信号处理,5,滤波器问题的本质表示如下： 给定一个输入取样序列u(0),u(1),u(2),设计一个线性离散滤波器其输出y(n)提供了期望响应d(n)的一个估值，使得其估计误差的均方值e(n)定义为期望响应d(n)与实际响应y(n)之差为最小。 两种数学解决方案 1 正交性原理 2误差性能曲面,自适应信号处理,6,正交性原理,n时刻滤波器输出为线性卷积 误差 代价函数均方误差,自适应信号处理,7,使代价函数J获得最小值的充要条件是其对应的估计误差 e(n)于n时刻进入期望响应估计的每个输入样值。,自适应信号处理,8,自适应信号处理,9,2.1 最速下降法的基本思想,无约束最优化的数学表示如下： 其中 是一个代价函数， 是个未知向量 是要寻找的最优解。,自适应信号处理,10,局部迭代下降思想 首先假设一个初始权向量 ，然后产生一系列权向量 能够使代价函数 在算法的每次迭代都是下降的，也就是满足如下表达式 最速下降法其实就是一种简单形式的迭代下降，它主要思想是沿着最速下降方向连续不断调整权向量 。最速下降方向也就是负梯度方向 梯度向量表示如下,自适应信号处理,11,通过以上可得最速下降算法 其中n表示迭代进程， 是步长参数，是正常数。 在从n到n+1的迭代过程中，权向量的调整量为,自适应信号处理,12,证明其满足迭代下降的思想 首先列出一阶泰勒展开式 趋近于无穷小 将代价函数 在 处进行一阶泰勒展开，可得,自适应信号处理,13,假设w为复值向量，那么梯度向量g也是复值向量。所以使用共轭转置（埃尔米特转置）因此上式可变为 从上式可以看出当 为正数时， 因此，随着n的增加，代价函数减小，当 时，代价函数趋于最小值 。,自适应信号处理,14,2.2 最速下降算法应用于维纳滤波器,图2.1 自适应横向滤波器的结构,自适应信号处理,15,通过比较期望响应 及其估计值，可以得到一个估计误差 即 其中 是抽头权向量 与抽头输入向量 的内积 如果抽头输入向量u(n)和期望响应d(n)是联合平稳的，则此时均方误差或者在n时刻的代价函数J(n)是抽头全向量的二次函数。,自适应信号处理,16,横向滤波器的代价函数为 所以展开可得 其中， 是目标函数 的方差 P =抽头输入向量 与期望响应 的互相关向量 R= 抽头输入向量 的相关矩阵,自适应信号处理,17,同时梯度向量可写为,自适应信号处理,18,因此维纳滤波中最速下降法的数学表达式为: 从另一个角度，可以将上公式看做一个反馈模型，信号流图如下,图2.2 最速下降算法的信号流图表示,自适应信号处理,19,2.3 最速下降法的稳定性,影响该算法的稳定性有两个因素： （1）步长参数 （2）抽头输入向量 的相关矩阵R 首先定义n时刻的加权误差向量 其中 是抽头权向量的最优值,自适应信号处理,20,使用特征值分解可得 将R代入上公式可得 两边同时左乘 令v(n)的初始值为：,自适应信号处理,21,对于最速下降法的第k个自然模式，并初始化可以得到 为了满足最速下降法的稳定性或收敛性，对于所有k，我们可以有 因此最速下降法稳定性的充分必要条件是步长因子满足不等式,自适应信号处理,22,从图中可以看出，当迭代次数趋近于无穷时， 趋近于0也就是抽头加权向量 逼近最优解,图2.3 最速下降算法的第k个自然模式随时间变化的情况,自适应信号处理,23,由上图我们可以定义一个时间常数 使得 表示了 衰减到初始值 的 时所需要的迭代次数 初始抽头加权向量 的瞬态特性 两边同时左乘,自适应信号处理,24,因此第i个抽头权值的瞬态特性可以表示为 其中 是第i个抽头权值的最优值， 是第k个特征向量的第i个分量 上式表明，最速下降算法中每一个抽头权值收敛于指数形式 的加权和。 同时定义整个时间常数 则可得任意抽头权值的时间常数的上下界定义如下,自适应信号处理,25,均方误差的瞬态特性 可知误差性能曲面的规范形式 其中 是最小均方误差 从初始值到最终值 的指数衰减的时间常数为,当 较小时,自适应信号处理,26,2.4作为确定性搜索法的最速下降算法,最速下降算法提供了从任意初始点出发寻找误差性能曲面极小点的局部搜索方法。 最速下降算法的运行，取决于三个量： * 起始点：由抽头权向量初始值w(0)规定 *梯度向量：位于误差性能曲面的特殊点，由互相关 向量P和相关向量矩阵R唯一确定 *步长参数 ：控制横向滤波器抽头权向量从算法 的某一次迭代到下一次迭代的增量变化 一旦规定了这三个量，最速下降算法将沿着多维权值空间独特的路径前进，它从初始点w(0)出发，终止于最优解 . 换句话说，在权值空间中最速下降算法是一种确定性的搜索方法。,自适应信号处理,27,2.5 最速下降法的优点与局限性,优点： 简单性，只要给出起始点，梯度向量及步长参数，将沿着权值空间特殊的路径前进，从初始点出发，终止于最优解。也就是说它是一种确定性搜索方法。 局限性：该过程需要大量的迭代，主要原因就是以围绕当前点的误差性能曲面的线性（一阶）为基础。针对这点后来提出来牛顿法，它是围绕当前点记为w(n)进行误差性能曲面的二次（例如二阶）逼近。,自适应信号处理,28,本章小结,两种集平均量 R（抽头输入向量的相关矩阵） P（抽头输入向量和期望响应的互相关向量） 最速下降算法提供了计算维纳滤波器抽头权向量的简化步骤。最速下降算法的一个重要特点就是存在反馈，实质是该算法是递归的。另