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

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

Формулировка задачи

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

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

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

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

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

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

$n$ номер текущей входной выборки

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

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

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

$\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}$

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

$d(n)=y(n)+\nu (n)$

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

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

Идея

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

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

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

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

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

Вывод

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

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

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

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

$\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\}$

где $\nabla$ это градиента оператор

$\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)$

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

Сейчас, $\nabla C(n)$ – вектор, указывающий на самый крутой подъем функции стоимости. Чтобы найти минимум функции стоимости, нам нужно сделать шаг в направлении, противоположном $\nabla C(n)$. Выражая это математическими терминами

${\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\}$

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

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

Упрощения

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

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

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

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

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

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

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

Краткое описание алгоритма LMS

Алгоритм LMS для $p$Фильтр-го порядка можно резюмировать как

Параметры:	$p=$ порядок фильтра
	$\mu =$ размер шага
Инициализация:	${\hat {\mathbf {h} }}(0)=\operatorname {zeros} (p)$
Расчет:	Для $n=0,1,2,...$
	$\mathbf {x} (n)=\left[x(n),x(n-1),\dots ,x(n-p+1)\right]^{T}$
	$e(n)=d(n)-{\hat {\mathbf {h} }}^{H}(n)\mathbf {x} (n)$
	${\hat {\mathbf {h} }}(n+1)={\hat {\mathbf {h} }}(n)+\mu \,e^{*}(n)\mathbf {x} (n)$

Сходимость и стабильность в среднем

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

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

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

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

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

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

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

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

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

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

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

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

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

Параметры:	$p=$ порядок фильтра
	$\mu =$ размер шага
Инициализация:	${\hat {\mathbf {h} }}(0)=\operatorname {zeros} (p)$
Расчет:	Для $n=0,1,2,...$
	$\mathbf {x} (n)=\left[x(n),x(n-1),\dots ,x(n-p+1)\right]^{T}$
	$e(n)=d(n)-{\hat {\mathbf {h} }}^{H}(n)\mathbf {x} (n)$
	${\hat {\mathbf {h} }}(n+1)={\hat {\mathbf {h} }}(n)+{\frac {\mu \,e^{*}(n)\mathbf {x} (n)}{\mathbf {x} ^{H}(n)\mathbf {x} (n)}}$

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

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

$\mu _{opt}=1$

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

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

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

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

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

$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]$

$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]$

Позволять $\mathbf {\delta } ={\hat {\mathbf {h} }}(n)-\mathbf {h} (n)$ и $r(n)={\hat {y}}(n)-y(n)$

$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]$

$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]$

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

$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]$

$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)}}$

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

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

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

См. также

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

Ссылки

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

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

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