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

Эта статья включает в себя список общих ссылок , но он остается в значительной степени непроверенным, поскольку в нем отсутствует достаточное количество соответствующих встроенных ссылок . Пожалуйста, помогите улучшить эту статью, добавив более точные цитаты. ( Январь 2019 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

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

Постановка проблемы [ править ]

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

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

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

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

Определение символов [ править ]

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

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

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

Поскольку алгоритм 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 состоит в том, что он чувствителен к масштабированию входных данных . Это делает очень трудным (если не невозможным) выбор скорости обучения , гарантирующей стабильность алгоритма (Хайкин, 2002). Фильтр Нормализованного минимум среднего квадратов (NLMS) представляет собой вариант LMS алгоритм , который решает эту проблему путем нормализации с силой входного сигнала. Алгоритм NLMS можно резюмировать как:${\displaystyle x(n)}$ ${\displaystyle \mu }$

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

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

Можно показать, что при отсутствии помех ( ) оптимальная скорость обучения для алгоритма 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 
• Бернард Уидроу, Сэмюэл Д. Стернс: адаптивная обработка сигналов, Прентис-Холл, 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