Фильтр наименьших средних квадратов

Статистический алгоритм

Алгоритмы наименьших средних квадратов ( LMS ) представляют собой класс адаптивных фильтров, используемых для имитации желаемого фильтра путем нахождения коэффициентов фильтра, которые относятся к получению наименьшего среднего квадрата сигнала ошибки (разницы между желаемым и фактическим сигналом). Это метод стохастического градиентного спуска , в котором фильтр адаптируется только на основе ошибки в текущий момент времени. Он был изобретен в 1960 году профессором Стэнфордского университета Бернардом Уидроу и его первым аспирантом Тедом Хоффом на основе их исследований однослойных нейронных сетей ( ADALINE ). В частности, они использовали градиентный спуск, чтобы обучить ADALINE распознавать шаблоны, и назвали алгоритм « дельта-правилом ». Затем они применили правило к фильтрам, в результате чего появился алгоритм LMS.

Формулировка проблемы

На рисунке показаны различные части фильтра. — входной сигнал, который затем преобразуется неизвестным фильтром , который мы хотим сопоставить с помощью . Выход неизвестного фильтра — , который затем интерферирует с шумовым сигналом , производя . Затем вычисляется сигнал ошибки , и он возвращается в адаптивный фильтр для настройки его параметров с целью минимизации среднего квадрата сигнала ошибки . ${\displaystyle x}$ ${\displaystyle h}$ ${\displaystyle {\hat {h}}}$ ${\displaystyle y}$ ${\displaystyle \nu }$ ${\displaystyle d=y+\nu }$ ${\displaystyle e=d-{\hat {y}}=y+\nu -{\hat {y}}}$ ${\displaystyle e}$

Связь с фильтром Винера

Реализация каузального фильтра Винера очень похожа на решение для оценки наименьших квадратов, за исключением области обработки сигнала. Решение наименьших квадратов для входной матрицы и выходного вектора : ${\displaystyle \mathbf {X} }$ ${\displaystyle {\boldsymbol {y}}}$

${\displaystyle {\boldsymbol {\hat {\beta }}}=(\mathbf {X} ^{\mathbf {T} }\mathbf {X} )^{-1}\mathbf {X} ^{\mathbf {T} }{\boldsymbol {y}}.}$

Фильтр наименьших средних квадратов FIR связан с фильтром Винера, но минимизация критерия ошибки первого не зависит от взаимных корреляций или автокорреляций. Его решение сходится к решению фильтра Винера. Большинство задач линейной адаптивной фильтрации можно сформулировать с помощью приведенной выше блок-схемы. То есть, необходимо идентифицировать неизвестную систему, а адаптивный фильтр пытается адаптировать фильтр , чтобы сделать ее максимально близкой к , используя только наблюдаемые сигналы , и ; но , и не являются непосредственно наблюдаемыми. Его решение тесно связано с фильтром Винера . ${\displaystyle \mathbf {h} (n)}$ ${\displaystyle {\hat {\mathbf {h} }}(n)}$ ${\displaystyle \mathbf {h} (n)}$ ${\displaystyle x(n)}$ ${\displaystyle d(n)}$ ${\displaystyle e(n)}$ ${\displaystyle y(n)}$ ${\displaystyle v(n)}$ ${\displaystyle h(n)}$

Определение символов

${\displaystyle n}$номер текущего входного образца

${\displaystyle p}$количество кранов фильтра

${\displaystyle \{\cdot \}^{H}}$( Эрмитово транспонирование или сопряженное транспонирование )

${\displaystyle \mathbf {x} (n)=\left[x(n),x(n-1),\dots ,x(n-p+1)\right]^{T}}$

${\displaystyle \mathbf {h} (n)=\left[h_{0}(n),h_{1}(n),\dots ,h_{p-1}(n)\right]^{T},\quad \mathbf {h} (n)\in \mathbb {C} ^{p}}$

${\displaystyle y(n)=\mathbf {h} ^{H}(n)\cdot \mathbf {x} (n)}$

${\displaystyle d(n)=y(n)+\nu (n)}$

${\displaystyle {\hat {\mathbf {h} }}(n)}$оцененный фильтр; интерпретировать как оценку коэффициентов фильтра после n выборок

${\displaystyle e(n)=d(n)-{\hat {y}}(n)=d(n)-{\hat {\mathbf {h} }}^{H}(n)\cdot \mathbf {x} (n)}$

Идея

Основная идея фильтра LMS заключается в приближении к оптимальным весам фильтра путем обновления весов фильтра таким образом, чтобы они сходились к оптимальному весу фильтра. Это основано на алгоритме градиентного спуска. Алгоритм начинается с предположения малых весов (в большинстве случаев нулевых) и на каждом шаге, находя градиент среднеквадратической ошибки, веса обновляются. То есть, если градиент MSE положительный, это означает, что ошибка будет продолжать увеличиваться положительно, если тот же вес используется для дальнейших итераций, что означает, что нам нужно уменьшить веса. Точно так же, если градиент отрицательный, нам нужно увеличить веса. Уравнение обновления веса имеет вид ${\displaystyle (R^{-1}P)}$

${\displaystyle W_{n+1}=W_{n}-\mu \nabla \varepsilon [n],}$

где представляет собой среднеквадратичную ошибку, а — коэффициент сходимости. ${\displaystyle \varepsilon }$ ${\displaystyle \mu }$

Отрицательный знак показывает, что мы идем вниз по наклону ошибки, чтобы найти веса фильтра, которые минимизируют ошибку. ${\displaystyle \varepsilon }$ ${\displaystyle W_{i}}$

Среднеквадратическая ошибка как функция весов фильтра является квадратичной функцией, что означает, что она имеет только один экстремум, который минимизирует среднеквадратичную ошибку, которая является оптимальным весом. Таким образом, LMS приближается к этим оптимальным весам, поднимаясь/спускаясь вниз по кривой среднеквадратической ошибки против веса фильтра.

Вывод

Идея фильтров LMS заключается в использовании скорейшего спуска для нахождения весов фильтров , которые минимизируют функцию стоимости . Начнем с определения функции стоимости как ${\displaystyle {\hat {\mathbf {h} }}(n)}$

${\displaystyle C(n)=E\left\{|e(n)|^{2}\right\}}$

где — ошибка в текущей выборке n , а — ожидаемое значение . ${\displaystyle e(n)}$ ${\displaystyle E\{\cdot \}}$

Эта функция стоимости ( ) является среднеквадратической ошибкой, и она минимизируется LMS. Отсюда LMS и получила свое название. Применение наискорейшего спуска означает взятие частных производных по отдельным элементам вектора коэффициента фильтра (веса) ${\displaystyle C(n)}$

${\displaystyle \nabla _{{\hat {\mathbf {h} }}^{H}}C(n)=\nabla _{{\hat {\mathbf {h} }}^{H}}E\left\{e(n)\,e^{*}(n)\right\}=2E\left\{\nabla _{{\hat {\mathbf {h} }}^{H}}(e(n))\,e^{*}(n)\right\}}$

где находится оператор градиента ${\displaystyle \nabla }$

${\displaystyle \nabla _{{\hat {\mathbf {h} }}^{H}}(e(n))=\nabla _{{\hat {\mathbf {h} }}^{H}}\left(d(n)-{\hat {\mathbf {h} }}^{H}\cdot \mathbf {x} (n)\right)=-\mathbf {x} (n)}$

${\displaystyle \nabla C(n)=-2E\left\{\mathbf {x} (n)\,e^{*}(n)\right\}}$

Теперь, — это вектор, который указывает на самый крутой подъем функции стоимости. Чтобы найти минимум функции стоимости, нам нужно сделать шаг в противоположном направлении от . Чтобы выразить это в математических терминах ${\displaystyle \nabla C(n)}$ ${\displaystyle \nabla C(n)}$

${\displaystyle {\hat {\mathbf {h} }}(n+1)={\hat {\mathbf {h} }}(n)-{\frac {\mu }{2}}\nabla C(n)={\hat {\mathbf {h} }}(n)+\mu \,E\left\{\mathbf {x} (n)\,e^{*}(n)\right\}}$

где — размер шага (константа адаптации). Это означает, что мы нашли алгоритм последовательного обновления, который минимизирует функцию стоимости. К сожалению, этот алгоритм не реализуем, пока мы не узнаем . ${\displaystyle {\frac {\mu }{2}}}$ ${\displaystyle E\left\{\mathbf {x} (n)\,e^{*}(n)\right\}}$

Обычно ожидание выше не вычисляется. Вместо этого, чтобы запустить LMS в онлайн-среде (обновляя после получения каждого нового образца), мы используем мгновенную оценку этого ожидания. См. ниже.

Упрощения

Для большинства систем функция ожидания должна быть аппроксимирована. Это можно сделать с помощью следующей несмещенной оценки ${\displaystyle {E}\left\{\mathbf {x} (n)\,e^{*}(n)\right\}}$

${\displaystyle {\hat {E}}\left\{\mathbf {x} (n)\,e^{*}(n)\right\}={\frac {1}{N}}\sum _{i=0}^{N-1}\mathbf {x} (n-i)\,e^{*}(n-i)}$

где указывает количество образцов, которые мы используем для этой оценки. Самый простой случай — ${\displaystyle N}$ ${\displaystyle N=1}$

${\displaystyle {\hat {E}}\left\{\mathbf {x} (n)\,e^{*}(n)\right\}=\mathbf {x} (n)\,e^{*}(n)}$

Для этого простого случая алгоритм обновления выглядит следующим образом:

${\displaystyle {\hat {\mathbf {h} }}(n+1)={\hat {\mathbf {h} }}(n)+\mu \mathbf {x} (n)\,e^{*}(n)}$

По сути, это и есть алгоритм обновления фильтра LMS.

Резюме алгоритма LMS

Алгоритм LMS для фильтра порядка можно обобщить следующим образом: ${\displaystyle p}$

Сходимость и устойчивость в среднем

Поскольку алгоритм LMS не использует точные значения ожиданий, веса никогда не достигнут оптимальных весов в абсолютном смысле, но возможна конвергенция в среднем. То есть, даже если веса могут изменяться на небольшие величины, они изменяются относительно оптимальных весов. Однако, если дисперсия, с которой изменяются веса, велика, конвергенция в среднем будет вводящей в заблуждение. Эта проблема может возникнуть, если значение размера шага выбрано неправильно. ${\displaystyle \mu }$

Если выбрано большим, то величина, на которую изменяются веса, сильно зависит от оценки градиента, и поэтому веса могут измениться на большую величину, так что градиент, который был отрицательным в первый момент, может теперь стать положительным. А во второй момент вес может измениться в противоположном направлении на большую величину из-за отрицательного градиента и, таким образом, будет продолжать колебаться с большой дисперсией вокруг оптимальных весов. С другой стороны, если выбрано слишком малым, то время сходимости к оптимальным весам будет слишком большим. ${\displaystyle \mu }$ ${\displaystyle \mu }$

Таким образом, необходима верхняя граница , которая задается как , ${\displaystyle \mu }$ ${\displaystyle 0<\mu <{\frac {2}{\lambda _{\mathrm {max} }}}}$

где — наибольшее собственное значение матрицы автокорреляции . Если это условие не выполняется, алгоритм становится неустойчивым и расходится. ${\displaystyle \lambda _{\max }}$ ${\displaystyle {\mathbf {R} }=E\{{\mathbf {x} }(n){\mathbf {x} ^{H}}(n)\}}$ ${\displaystyle {\hat {h}}(n)}$

Максимальная скорость сходимости достигается, когда

${\displaystyle \mu ={\frac {2}{\lambda _{\mathrm {max} }+\lambda _{\mathrm {min} }}},}$

где — наименьшее собственное значение . Учитывая, что меньше или равно этому оптимуму, скорость сходимости определяется , причем большее значение дает более быструю сходимость. Это означает, что более быстрая сходимость может быть достигнута, когда близка к , то есть максимально достижимая скорость сходимости зависит от разброса собственных значений . ${\displaystyle \lambda _{\min }}$ ${\displaystyle {\mathbf {R} }}$ ${\displaystyle \mu }$ ${\displaystyle \lambda _{\min }}$ ${\displaystyle \lambda _{\max }}$ ${\displaystyle \lambda _{\min }}$ ${\displaystyle {\mathbf {R} }}$

Сигнал белого шума имеет автокорреляционную матрицу, где — дисперсия сигнала. В этом случае все собственные значения равны, а разброс собственных значений минимален по всем возможным матрицам. Поэтому общепринятая интерпретация этого результата заключается в том, что LMS быстро сходится для белых входных сигналов и медленно для цветных входных сигналов, таких как процессы с низкочастотными или высокочастотными характеристиками. ${\displaystyle {\mathbf {R} }=\sigma ^{2}{\mathbf {I} }}$ ${\displaystyle \sigma ^{2}}$

Важно отметить, что указанная выше верхняя граница обеспечивает только устойчивость в среднем, но коэффициенты могут все еще расти бесконечно большими, т.е. расхождение коэффициентов все еще возможно. Более практичная граница ${\displaystyle \mu }$ ${\displaystyle {\hat {h}}(n)}$

${\displaystyle 0<\mu <{\frac {2}{\mathrm {tr} \left[{\mathbf {R} }\right]}},}$

где обозначает след . Эта граница гарантирует , что коэффициенты не расходятся (на практике значение не следует выбирать близким к этой верхней границе, поскольку оно несколько оптимистично из-за приближений и предположений, сделанных при выводе границы). ${\displaystyle \mathrm {tr} [{\mathbf {R} }]}$ ${\displaystyle {\mathbf {R} }}$ ${\displaystyle {\hat {h}}(n)}$ ${\displaystyle \mu }$

Нормализованный фильтр наименьших средних квадратов (NLMS)

Главным недостатком «чистого» алгоритма LMS является его чувствительность к масштабированию входных данных . Это делает очень сложным (если не невозможным) выбор скорости обучения , гарантирующей устойчивость алгоритма (Haykin 2002). Нормализованный фильтр наименьших средних квадратов (NLMS) — это вариант алгоритма LMS, который решает эту проблему путем нормализации с учетом мощности входных данных. Алгоритм NLMS можно обобщить следующим образом: ${\displaystyle x(n)}$ ${\displaystyle \mu }$

Оптимальная скорость обучения

Можно показать, что если помехи отсутствуют ( ), то оптимальная скорость обучения для алгоритма NLMS равна ${\displaystyle v(n)=0}$

${\displaystyle \mu _{opt}=1}$

и не зависит от входа и реального (неизвестного) импульсного отклика . В общем случае с помехами ( ) оптимальная скорость обучения равна ${\displaystyle x(n)}$ ${\displaystyle \mathbf {h} (n)}$ ${\displaystyle v(n)\neq 0}$

${\displaystyle \mu _{opt}={\frac {E\left[\left|y(n)-{\hat {y}}(n)\right|^{2}\right]}{E\left[|e(n)|^{2}\right]}}}$

Приведенные выше результаты предполагают, что сигналы и не коррелируют друг с другом, что обычно и происходит на практике. ${\displaystyle v(n)}$ ${\displaystyle x(n)}$

Доказательство

Пусть смещение фильтра определяется как , тогда мы можем вывести ожидаемое смещение для следующего образца как: ${\displaystyle \Lambda (n)=\left|\mathbf {h} (n)-{\hat {\mathbf {h} }}(n)\right|^{2}}$

${\displaystyle E\left[\Lambda (n+1)\right]=E\left[\left|{\hat {\mathbf {h} }}(n)+{\frac {\mu \,e^{*}(n)\mathbf {x} (n)}{\mathbf {x} ^{H}(n)\mathbf {x} (n)}}-\mathbf {h} (n)\right|^{2}\right]}$

${\displaystyle E\left[\Lambda (n+1)\right]=E\left[\left|{\hat {\mathbf {h} }}(n)+{\frac {\mu \,\left(v^{*}(n)+y^{*}(n)-{\hat {y}}^{*}(n)\right)\mathbf {x} (n)}{\mathbf {x} ^{H}(n)\mathbf {x} (n)}}-\mathbf {h} (n)\right|^{2}\right]}$

Пусть и ${\displaystyle \mathbf {\delta } ={\hat {\mathbf {h} }}(n)-\mathbf {h} (n)}$ ${\displaystyle r(n)={\hat {y}}(n)-y(n)}$

${\displaystyle E\left[\Lambda (n+1)\right]=E\left[\left|\mathbf {\delta } (n)-{\frac {\mu \,\left(v(n)+r(n)\right)\mathbf {x} (n)}{\mathbf {x} ^{H}(n)\mathbf {x} (n)}}\right|^{2}\right]}$

${\displaystyle E\left[\Lambda (n+1)\right]=E\left[\left(\mathbf {\delta } (n)-{\frac {\mu \,\left(v(n)+r(n)\right)\mathbf {x} (n)}{\mathbf {x} ^{H}(n)\mathbf {x} (n)}}\right)^{H}\left(\mathbf {\delta } (n)-{\frac {\mu \,\left(v(n)+r(n)\right)\mathbf {x} (n)}{\mathbf {x} ^{H}(n)\mathbf {x} (n)}}\right)\right]}$

Предполагая независимость, имеем:

${\displaystyle E\left[\Lambda (n+1)\right]=\Lambda (n)+E\left[\left({\frac {\mu \,\left(v(n)+r(n)\right)\mathbf {x} (n)}{\mathbf {x} ^{H}(n)\mathbf {x} (n)}}\right)^{H}\left({\frac {\mu \,\left(v(n)+r(n)\right)\mathbf {x} (n)}{\mathbf {x} ^{H}(n)\mathbf {x} (n)}}\right)\right]-2E\left[{\frac {\mu |r(n)|^{2}}{\mathbf {x} ^{H}(n)\mathbf {x} (n)}}\right]}$

${\displaystyle E\left[\Lambda (n+1)\right]=\Lambda (n)+{\frac {\mu ^{2}E\left[|e(n)|^{2}\right]}{\mathbf {x} ^{H}(n)\mathbf {x} (n)}}-{\frac {2\mu E\left[|r(n)|^{2}\right]}{\mathbf {x} ^{H}(n)\mathbf {x} (n)}}}$

Оптимальная скорость обучения находится при , что приводит к: ${\displaystyle {\frac {dE\left[\Lambda (n+1)\right]}{d\mu }}=0}$

${\displaystyle 2\mu E\left[|e(n)|^{2}\right]-2E\left[|r(n)|^{2}\right]=0}$

${\displaystyle \mu ={\frac {E\left[|r(n)|^{2}\right]}{E\left[|e(n)|^{2}\right]}}}$

Смотрите также

• Рекурсивный метод наименьших квадратов
• Для получения информации о статистических методах, относящихся к фильтру LMS, см. раздел Наименьшие квадраты .
• Сходства между Wiener и LMS
• Многоблочный адаптивный фильтр частотной области с несколькими задержками
• Эквалайзер с нулевым форсированием
• Адаптивный фильтр ядра
• Соответствующий фильтр
• фильтр Винера

Ссылки

• Монсон Х. Хейс: Статистическая цифровая обработка сигналов и моделирование, Wiley, 1996, ISBN  0-471-59431-8
• Саймон Хейкин: Теория адаптивного фильтра, Prentice Hall, 2002, ISBN 0-13-048434-2 
• Саймон С. Хайкин, Бернард Уидроу (редактор): Адаптивные фильтры с наименьшими квадратами, Wiley, 2003, ISBN 0-471-21570-8 
• Бернард Уидроу, Сэмюэл Д. Стернс: Адаптивная обработка сигналов, Prentice Hall, 1985, ISBN 0-13-004029-0 
• Вэйфэн Лю, Хосе Принсипе и Саймон Хейкин: Kernel Adaptive Filtering: A Comprehensive Introduction, John Wiley, 2010, ISBN 0-470-44753-2 
• Пауло С. Р. Диниц: Адаптивная фильтрация: алгоритмы и практическая реализация, Kluwer Academic Publishers, 1997, ISBN 0-7923-9912-9 

Внешние ссылки

• Алгоритм LMS в адаптивных антенных решетках www.antenna-theory.com
• Демонстрация шумоподавления LMS www.advsolned.com