Рекурсивный фильтр наименьших квадратов

Алгоритм адаптивного фильтра для цифровой обработки сигналов

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

Мотивация

RLS был открыт Гауссом , но оставался неиспользованным или игнорировался до 1950 года, когда Плакетт заново открыл оригинальную работу Гаусса 1821 года. В общем, RLS можно использовать для решения любой проблемы, которую можно решить с помощью адаптивных фильтров . Например, предположим, что сигнал передается по эхо- шумному каналу , из-за чего он принимается как ${\displaystyle d(n)}$

${\displaystyle x(n)=\sum _{k=0}^{q}b_{n}(k)d(n-k)+v(n)}$

где представляет собой аддитивный шум . Целью RLS-фильтра является восстановление полезного сигнала с помощью КИХ - фильтра с отводом : ${\displaystyle v(n)}$ ${\displaystyle d(n)}$ ${\displaystyle p+1}$ ${\displaystyle \mathbf {w} }$

${\displaystyle d(n)\approx \sum _{k=0}^{p}w(k)x(n-k)=\mathbf {w} ^{\mathit {T}}\mathbf {x} _{n}}$

где вектор - столбец , содержащий самые последние образцы . Оценка восстановленного полезного сигнала равна ${\displaystyle \mathbf {x} _{n}=[x(n)\quad x(n-1)\quad \ldots \quad x(n-p)]^{T}}$ ${\displaystyle p+1}$ ${\displaystyle x(n)}$

${\displaystyle {\hat {d}}(n)=\sum _{k=0}^{p}w_{n}(k)x(n-k)=\mathbf {w} _{n}^{\mathit {T}}\mathbf {x} _{n}}$

Цель состоит в том, чтобы оценить параметры фильтра , и каждый раз мы ссылаемся на текущую оценку как и на адаптированную оценку методом наименьших квадратов как . также является вектор-столбцом, как показано ниже, а транспонирование , , является вектором-строкой . Матричный продукт (который является скалярным произведением и ) является скаляром. Оценка считается «хорошей» , если она мала по величине в некотором смысле метода наименьших квадратов . ${\displaystyle \mathbf {w} }$ ${\displaystyle n}$ ${\displaystyle \mathbf {w} _{n}}$ ${\displaystyle \mathbf {w} _{n+1}}$ ${\displaystyle \mathbf {w} _{n}}$ ${\displaystyle \mathbf {w} _{n}^{\mathit {T}}}$ ${\displaystyle \mathbf {w} _{n}^{\mathit {T}}\mathbf {x} _{n}}$ ${\displaystyle \mathbf {w} _{n}}$ ${\displaystyle \mathbf {x} _{n}}$ ${\displaystyle {\hat {d}}(n)}$ ${\displaystyle {\hat {d}}(n)-d(n)}$

С течением времени желательно избегать полного повторения алгоритма наименьших квадратов для нахождения новой оценки для , в терминах . ${\displaystyle \mathbf {w} _{n+1}}$ ${\displaystyle \mathbf {w} _{n}}$

Преимущество алгоритма RLS заключается в том, что нет необходимости инвертировать матрицы, что позволяет сэкономить вычислительные затраты. Еще одним преимуществом является то, что он обеспечивает интуитивное понимание таких результатов, как фильтр Калмана .

Обсуждение

Идея фильтров RLS заключается в минимизации функции стоимости путем соответствующего выбора коэффициентов фильтра и обновления фильтра по мере поступления новых данных. Сигнал ошибки и полезный сигнал определены на схеме отрицательной обратной связи ниже: ${\displaystyle C}$ ${\displaystyle \mathbf {w} _{n}}$ ${\displaystyle e(n)}$ ${\displaystyle d(n)}$

Ошибка неявно зависит от коэффициентов фильтра посредством оценки : ${\displaystyle {\hat {d}}(n)}$

${\displaystyle e(n)=d(n)-{\hat {d}}(n)}$

Таким образом, взвешенная функция ошибок метода наименьших квадратов — функция стоимости, которую мы хотим минимизировать, — также зависит от коэффициентов фильтра: ${\displaystyle C}$ ${\displaystyle e(n)}$

${\displaystyle C(\mathbf {w} _{n})=\sum _{i=0}^{n}\lambda ^{n-i}e^{2}(i)}$

где - «фактор забывания», который придает экспоненциально меньший вес более старым образцам ошибок. ${\displaystyle 0<\lambda \leq 1}$

Функция стоимости минимизируется путем взятия частных производных для всех элементов вектора коэффициентов и установки результатов равными нулю. ${\displaystyle k}$ ${\displaystyle \mathbf {w} _{n}}$

${\displaystyle {\frac {\partial C(\mathbf {w} _{n})}{\partial w_{n}(k)}}=\sum _{i=0}^{n}2\lambda ^{n-i}e(i)\cdot {\frac {\partial e(i)}{\partial w_{n}(k)}}=-\sum _{i=0}^{n}2\lambda ^{n-i}e(i)\,x(i-k)=0\qquad k=0,1,\ldots ,p}$

Далее заменяем на определение сигнала ошибки ${\displaystyle e(n)}$

${\displaystyle \sum _{i=0}^{n}\lambda ^{n-i}\left[d(i)-\sum _{\ell =0}^{p}w_{n}(\ell )x(i-\ell )\right]x(i-k)=0\qquad k=0,1,\ldots ,p}$

Перестановка уравнения дает

${\displaystyle \sum _{\ell =0}^{p}w_{n}(\ell )\left[\sum _{i=0}^{n}\lambda ^{n-i}\,x(i-l)x(i-k)\right]=\sum _{i=0}^{n}\lambda ^{n-i}d(i)x(i-k)\qquad k=0,1,\ldots ,p}$

Эту форму можно выразить через матрицы

${\displaystyle \mathbf {R} _{x}(n)\,\mathbf {w} _{n}=\mathbf {r} _{dx}(n)}$

где – взвешенная выборочная ковариационная матрица для и – эквивалентная оценка перекрестной ковариации между и . На основе этого выражения находим коэффициенты, минимизирующие функцию стоимости: ${\displaystyle \mathbf {R} _{x}(n)}$ ${\displaystyle x(n)}$ ${\displaystyle \mathbf {r} _{dx}(n)}$ ${\displaystyle d(n)}$ ${\displaystyle x(n)}$

${\displaystyle \mathbf {w} _{n}=\mathbf {R} _{x}^{-1}(n)\,\mathbf {r} _{dx}(n)}$

Это главный результат дискуссии.

Выбор λ

Чем меньше , тем меньше вклад предыдущих выборок в ковариационную матрицу. Это делает фильтр более чувствительным к последним выборкам, что означает большие колебания коэффициентов фильтра. Этот случай называется алгоритмом RLS растущего окна . На практике обычно выбирается от 0,98 до 1. ^[1] Используя оценку максимального правдоподобия типа II, оптимальное значение можно оценить на основе набора данных. ^[2] ${\displaystyle \lambda }$ ${\displaystyle \lambda =1}$ ${\displaystyle \lambda }$ ${\displaystyle \lambda }$

Рекурсивный алгоритм

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

${\displaystyle \mathbf {w} _{n}=\mathbf {w} _{n-1}+\Delta \mathbf {w} _{n-1}}$

где – поправочный коэффициент во времени . Мы начнем вывод рекурсивного алгоритма с выражения перекрестной ковариации через ${\displaystyle \Delta \mathbf {w} _{n-1}}$ ${\displaystyle {n-1}}$ ${\displaystyle \mathbf {r} _{dx}(n)}$ ${\displaystyle \mathbf {r} _{dx}(n-1)}$

где вектор размерных данных ${\displaystyle \mathbf {x} (i)}$ ${\displaystyle {p+1}}$

${\displaystyle \mathbf {x} (i)=[x(i),x(i-1),\dots ,x(i-p)]^{T}}$

Аналогично выражаем через ${\displaystyle \mathbf {R} _{x}(n)}$ ${\displaystyle \mathbf {R} _{x}(n-1)}$

Чтобы сгенерировать вектор коэффициентов, нас интересует обратная детерминированная автоковариационная матрица. Для этой задачи пригодится матричное тождество Вудбери . С

Матричное тождество Вудбери следует

Чтобы соответствовать стандартной литературе, мы определяем

где вектор усиления ${\displaystyle g(n)}$

Прежде чем двигаться дальше, необходимо привести в другой вид ${\displaystyle \mathbf {g} (n)}$

Вычитание второго члена в левой части дает

При рекурсивном определении искомой формы следует ${\displaystyle \mathbf {P} (n)}$

${\displaystyle \mathbf {g} (n)=\mathbf {P} (n)\mathbf {x} (n)}$

Теперь мы готовы завершить рекурсию. Как обсуждалось

Второй шаг следует из рекурсивного определения . Далее мы объединяем рекурсивное определение вместе с альтернативной формой и получаем ${\displaystyle \mathbf {r} _{dx}(n)}$ ${\displaystyle \mathbf {P} (n)}$ ${\displaystyle \mathbf {g} (n)}$

Когда мы приходим к уравнению обновления ${\displaystyle \mathbf {w} _{n-1}=\mathbf {P} (n-1)\mathbf {r} _{dx}(n-1)}$

где априорная ошибка . Сравните это с апостериорной ошибкой; ошибка, рассчитанная после обновления фильтра: ${\displaystyle \alpha (n)=d(n)-\mathbf {x} ^{T}(n)\mathbf {w} _{n-1}}$

${\displaystyle e(n)=d(n)-\mathbf {x} ^{T}(n)\mathbf {w} _{n}}$

Это значит, что мы нашли поправочный коэффициент

${\displaystyle \Delta \mathbf {w} _{n-1}=\mathbf {g} (n)\alpha (n)}$

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

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

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

Рекурсия для следует алгебраическому уравнению Риккати и, таким образом, проводит параллели с фильтром Калмана . ^[3] ${\displaystyle P}$

Решетчатый рекурсивный фильтр наименьших квадратов (LRLS)

Адаптивный фильтр решеточно-рекурсивного метода наименьших квадратов связан со стандартным RLS, за исключением того, что он требует меньшего количества арифметических операций (порядок N ). ^[4] Он предлагает дополнительные преимущества по сравнению с традиционными алгоритмами LMS, такие как более высокая скорость сходимости, модульная структура и нечувствительность к изменениям разброса собственных значений входной корреляционной матрицы. Описанный алгоритм LRLS основан на апостериорных ошибках и включает нормализованную форму. Вывод аналогичен стандартному алгоритму RLS и основан на определении . В случае прямого прогнозирования мы имеем входной сигнал в качестве самой последней выборки. Случай обратного прогнозирования : где i — индекс выборки в прошлом, которую мы хотим предсказать, а входной сигнал — самая последняя выборка. ^[5] ${\displaystyle d(k)\,\!}$ ${\displaystyle d(k)=x(k)\,\!}$ ${\displaystyle x(k-1)\,\!}$ ${\displaystyle d(k)=x(k-i-1)\,\!}$ ${\displaystyle x(k)\,\!}$

Сводка параметров

${\displaystyle \kappa _{f}(k,i)\,\!}$коэффициент прямого отражения

${\displaystyle \kappa _{b}(k,i)\,\!}$коэффициент обратного отражения

${\displaystyle e_{f}(k,i)\,\!}$представляет мгновенную ошибку апостериорного прямого прогнозирования

${\displaystyle e_{b}(k,i)\,\!}$представляет мгновенную ошибку апостериорного обратного прогнозирования

${\displaystyle \xi _{b_{\min }}^{d}(k,i)\,\!}$- минимальная ошибка обратного прогнозирования по методу наименьших квадратов

${\displaystyle \xi _{f_{\min }}^{d}(k,i)\,\!}$- минимальная ошибка прямого прогнозирования методом наименьших квадратов

${\displaystyle \gamma (k,i)\,\!}$- это коэффициент преобразования между априорными и апостериорными ошибками .

${\displaystyle v_{i}(k)\,\!}$– коэффициенты множителя прямой связи.

${\displaystyle \varepsilon \,\!}$— небольшая положительная константа, которая может составлять 0,01

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

Алгоритм фильтра LRLS можно резюмировать следующим образом:

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

Нормализованная форма LRLS имеет меньше рекурсий и переменных. Его можно рассчитать, применив нормализацию к внутренним переменным алгоритма, при которой их величина будет ограничена единицей. Обычно это не используется в приложениях реального времени из-за большого количества операций деления и извлечения квадратного корня, которые требуют высокой вычислительной нагрузки.

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

Алгоритм фильтра NLRLS можно резюмировать следующим образом:

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

• Адаптивный фильтр
• Адаптивный фильтр ядра
• Фильтр наименьших средних квадратов
• Эквалайзер с нулевым принуждением

Рекомендации

• Хейс, Монсон Х. (1996). «9.4: Рекурсивный метод наименьших квадратов». Статистическая цифровая обработка сигналов и моделирование . Уайли. п. 541. ИСБН 0-471-59431-8.
• Саймон Хайкин, Теория адаптивного фильтра , Прентис Холл, 2002, ISBN 0-13-048434-2 
• MHA Дэвис, Р.Б. Винтер, Стохастическое моделирование и управление , Springer, 1985, ISBN 0-412-16200-8 
• Вейфэн Лю, Хосе Принсипи и Саймон Хайкин, Адаптивная фильтрация ядра: всестороннее введение , Джон Уайли, 2010, ISBN 0-470-44753-2 
• РЛПлэкетт, Некоторые теоремы по наименьшим квадратам , Биометрика, 1950, 37, 149–157, ISSN  0006-3444.
• CFGauss, Theoria Combinis Observeum erroribus minimis obnoxiae , 1821, Werke, 4. Gottinge.

Примечания

1. Эманнуаль К. Ифеакор, Барри В. Джервис. Цифровая обработка сигналов: практический подход, второе издание. Индианаполис: Pearson Education Limited, 2002, с. 718
2. Стивен Ван Веренберг, Игнасио Сантамария, Мигель Лазаро-Гредилья «Оценка фактора забывания в ядерно-рекурсивном методе наименьших квадратов», Международный семинар IEEE 2012 г. по машинному обучению для обработки сигналов, 2012 г., по состоянию на 23 июня 2016 г.
3. Уэлч, Грег и Бишоп, Гэри «Введение в фильтр Калмана», факультет компьютерных наук, Университет Северной Каролины в Чапел-Хилл, 17 сентября 1997 г., по состоянию на 19 июля 2011 г.
4. Диниз, Пауло С.Р., «Адаптивная фильтрация: алгоритмы и практическая реализация», Springer Nature Switzerland AG 2020, Глава 7: Адаптивные алгоритмы RLS на основе решетки. https://doi.org/10.1007/978-3-030-29057-3_7
5. Альбу, Кадлец, Софтли, Матоусек, Херманек, Коулман, Фаган «Реализация (нормализованной) решетки RLS на Virtex», Digital Signal Processing, 2001, по состоянию на 24 декабря 2011 г.