Рекурсивный метод наименьших квадратов (RLS) - это алгоритм адаптивного фильтра , который рекурсивно находит коэффициенты, которые минимизируют взвешенную линейную функцию наименьших квадратов, относящуюся к входным сигналам. Этот подход отличается от других алгоритмов, таких как метод наименьших средних квадратов (LMS), которые направлены на уменьшение среднеквадратичной ошибки . При выводе RLS входные сигналы считаются детерминированными , в то время как для LMS и аналогичного алгоритма они считаются стохастическими . По сравнению с большинством своих конкурентов, RLS демонстрирует чрезвычайно быструю сходимость. Однако это преимущество достигается за счет высокой вычислительной сложности.
Мотивация
RLS был открыт Гауссом, но не использовался или игнорировался до 1950 года, когда Плакетт заново открыл оригинальную работу Гаусса 1821 года. В общем, RLS можно использовать для решения любой проблемы, которую можно решить с помощью адаптивных фильтров . Например, предположим, что сигналпередается по эхо- каналу , зашумленному, что вызывает его прием как
где представляет собой аддитивный шум . Назначение фильтра RLS - восстановить полезный сигнал. с помощью -tap КИХ- фильтр,:
где это вектор - столбец , содержащий самые последние образцы . Оценка восстановленного полезного сигнала
Цель - оценить параметры фильтра. , и каждый раз мы называем текущую оценку как и адаптированная оценка методом наименьших квадратов . также вектор-столбец, как показано ниже, а транспонирование ,, является вектор-строкой . Матричное произведение(который является скалярным произведением из а также ) является , скаляр. Оценка считается "хорошей", еслимала по величине в некотором смысле наименьших квадратов .
С течением времени желательно избегать полного повторения алгоритма наименьших квадратов, чтобы найти новую оценку для , с точки зрения .
Преимущество алгоритма RLS состоит в том, что нет необходимости инвертировать матрицы, тем самым экономя вычислительные затраты. Еще одно преимущество заключается в том, что он обеспечивает интуитивное понимание таких результатов, как фильтр Калмана .
Обсуждение
Идея фильтров RLS состоит в том, чтобы минимизировать функцию стоимости. путем соответствующего выбора коэффициентов фильтра , обновляя фильтр по мере поступления новых данных. Сигнал ошибки и желаемый сигнал определены на диаграмме отрицательной обратной связи ниже:
Ошибка неявно зависит от коэффициентов фильтра через оценку :
Функция взвешенных наименьших квадратов ошибок - функция затрат, которую мы хотим минимизировать, - являющаяся функцией поэтому также зависит от коэффициентов фильтра:
где это «фактор забвения», который придает экспоненциально меньший вес более старым выборкам ошибок.
Функция стоимости минимизируется путем взятия частных производных для всех элементов вектора коэффициентов и обнуление результатов
Далее замените с определением сигнала ошибки
Преобразование уравнения дает
Эту форму можно выразить через матрицы
где - взвешенная выборочная ковариационная матрица для, а также эквивалентная оценка кросс-ковариации между а также . На основе этого выражения находим коэффициенты, которые минимизируют функцию стоимости как
Это главный результат обсуждения.
Выбор
Меньший , тем меньше вклад предыдущих выборок в ковариационную матрицу. Это делает фильтр более чувствительным к недавним выборкам, что означает большее колебание коэффициентов фильтра. Вслучай называется алгоритмом RLS с растущим окном . На практике,обычно выбирается между 0,98 и 1. [1] Используя оценку максимального правдоподобия типа II, оптимальныйможно оценить по набору данных. [2]
Рекурсивный алгоритм
Обсуждение привело к единому уравнению для определения вектора коэффициентов, который минимизирует функцию стоимости. В этом разделе мы хотим получить рекурсивное решение вида
где поправочный коэффициент во времени . Мы начинаем вывод рекурсивного алгоритма с выражения кросс-ковариации с точки зрения
где это размерный вектор данных
Аналогично выражаем с точки зрения от
Чтобы сгенерировать вектор коэффициентов, нас интересует инверсия детерминированной автоковариационной матрицы. Для этой задачи пригодится матричное тождество Вудбери . С участием
Чтобы соответствовать стандартной литературе, мы определяем
где вектор усиления является
Прежде чем двигаться дальше, необходимо принести в другую форму
Вычитание второго члена в левой части дает
С рекурсивным определением желаемая форма следует
Теперь мы готовы завершить рекурсию. Как обсуждалось
Второй шаг следует из рекурсивного определения . Далее мы включаем рекурсивное определение вместе с альтернативной формой и получить
С участием мы приходим к уравнению обновления
где - априорная ошибка. Сравните это с апостериорной ошибкой; ошибка, рассчитанная после обновления фильтра:
Значит, мы нашли поправочный коэффициент
Этот интуитивно удовлетворительный результат показывает, что поправочный коэффициент прямо пропорционален как ошибке, так и вектору усиления, который контролирует желаемую чувствительность через весовой коэффициент, .
Сводка алгоритма RLS
Алгоритм RLS для фильтра RLS p-го порядка можно резюмировать как
Решетка Рекурсивный метод наименьших квадратов адаптивный фильтр связан со стандартными RLS исключением того, что она требует меньшего числа арифметических операций (порядка N). [4] Он предлагает дополнительные преимущества по сравнению с обычными алгоритмами LMS, такие как более высокая скорость сходимости, модульная структура и нечувствительность к изменениям в разбросе собственных значений входной корреляционной матрицы. Описанный алгоритм LRLS основан на апостериорных ошибках и включает нормализованную форму. Вывод аналогичен стандартному алгоритму RLS и основан на определении. В случае прямого прогнозирования мы имеем с входным сигналом как самый актуальный образец. Случай обратного предсказания, где i - индекс выборки в прошлом, которую мы хотим спрогнозировать, а входной сигнал это самый последний образец. [5]
Сводка параметров
коэффициент прямого отражения
коэффициент обратного отражения
представляет собой мгновенную апостериорную ошибку прямого прогнозирования
представляет собой мгновенную апостериорную ошибку обратного предсказания
- минимальная ошибка обратного предсказания методом наименьших квадратов
минимальная ошибка прямого прогнозирования методом наименьших квадратов
коэффициент пересчета между априорными и апостериорными ошибками
- коэффициенты множителя с прямой связью.
небольшая положительная константа, которая может быть 0,01
Нормализованная форма LRLS имеет меньше рекурсий и переменных. Его можно вычислить, применив нормализацию к внутренним переменным алгоритма, при которой их величина будет ограничена единицей. Обычно это не используется в приложениях реального времени из-за большого количества операций деления и извлечения квадратного корня, что сопряжено с высокой вычислительной нагрузкой.
^ Emannual С. Ifeacor, Бэрри В. Джервис. Цифровая обработка сигналов: практический подход, второе издание. Индианаполис: Pearson Education Limited, 2002, стр. 718
^ Стивен Ван Вэренберг, Игнасио Сантамария, Мигель Ласаро-Гредилья «Оценка фактора забывания в рекурсивных методах наименьших квадратов ядра» , 2012 IEEE International Workshop on Machine Learning for Signal Processing, 2012, по состоянию на 23 июня 2016 г.
^ Велч, Грег и Бишоп, Гэри «Введение в фильтр Калмана» , факультет компьютерных наук, Университет Северной Каролины в Чапел-Хилл, 17 сентября 1997 г., по состоянию на 19 июля 2011 г.
^ Диниз, Пауло С.Р., «Адаптивная фильтрация: алгоритмы и практическая реализация», Springer Nature Switzerland AG 2020, Глава 7: Адаптивные алгоритмы RLS на основе решеток. https://doi.org/10.1007/978-3-030-29057-3_7
↑ Albu, Kadlec, Softley, Matousek, Hermanek, Coleman, Fagan «Внедрение (нормализованной) решетки RLS на Virtex» , Digital Signal Processing, 2001, по состоянию на 24 декабря 2011 года.