最速下降法

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