2.2 Адаптивный алгоритм LMS

Один из наиболее распространенных адаптивных алгоритмов основан на поиске минимума целевой функции методом наискорейшего спуска. При использовании данного способа оптимизации вектор коэффициентов фильтра w зависит от номера итерации k: , и должен на каждой итерации смещаться на величину, пропорциональную градиенту целевой функции в данной точке, следующим образом:

, (11)

где - положительный коэффициент, называемый размером шага. Подробный анализ сходимости данного процесса приведен, например, в [фильтр Винера]. Показано, что алгоритм сходится, если

, (12)

где - максимальное собственное число корреляционной матрицы R. Скорость сходимости при этом зависит от разброса собственных чисел корреляционной матрицы R- чем меньше отношение тем быстрее сходится итерационный процесс.

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

При использовании данных оценок формула принимает следующий вид:

(13)

Выражение, стоящее в скобках, согласно (3), представляет собой разность между образцовым сигналом и выходным сигналом фильтра на k-м шаге, то есть ошибку фильтрации е(k). С учетом этого, выражение для рекурсивного обновления коэффициентов фильтра оказывается очень простым:

(14)

Алгоритм адаптивной фильтрации, основанный на данной формуле, получил название LMS (Least Mean Square, метод наименьших квадратов). Можно получить ту же формулу и несколько иным образом: использовав вместо градиента статистически усредненного квадрата ошибки градиент его мгновенного значения .

Анализ сходимости алгоритма LMS оказывается чрезвычайно сложной задачей, для которой не существует точного аналитического решения. Достаточно подробный анализ с использованием приближений приведен в книге С. Хайкина. Он показывает, что верхняя граница для размера шага в данном случае является меньшей, чем при использовании истинных значений градиента. Эта граница примерно равна:

(15)

где - собственные числа корреляционной матрицы R, а - средний квадрат входного сигнала фильтра.

На вышеприведенной формуле основан нормированный (normalized) LMS-алгоритм, в котором коэффициент на каждом шаге рассчитывается, исходя из энергии сигнала, содержащегося в линии задержки:

(16)

где µ0 - нормированное значение µ, лежащее в диапазоне от 0 до 2, а е -- малая положительная константа, назначение которой -- ограничить рост µ при нулевом сигнале на входе фильтра.

Даже если LMS-алгоритм сходится, дисперсии коэффициентов фильтра при k>? не стремится к нулю -- коэффициенты флуктуируют вокруг оптимальных значений. Из-за этого ошибка фильтрации в установившемся режиме оказывается больше, чем ошибка для винеровского фильтра :

,

где Eex - средний квадрат избыточной ошибки (excess error) алгоритма LMS.

В той же книге С.Хайкина приводится следующая приближенная формула для так называемого коэффициента расстройства (misalignment), равного отношению средних квадратов избыточной и винеровской ошибок:

(17)

Значение коэффициента µ влияет на два главных параметра LMS-фильтра: скорость сходимости и коэффициент расстройки. Чем больше µ, тем быстрее сходится алгоритм, но тем больше становится коэффициент расстройки и наоборот.

Основным достоинством алгоритма LMS является предельная вычислительная простота - для подстройки коэффициентов фильтра на каждом шаге нужно выполнить N + 1 пар операций «умножение-сложение». Платой за простоту является медленная сходимость и повышенная (по сравнению с минимально достижимым значением) дисперсия ошибки в установившемся режиме.

2.3 Детерминированная задача оптимальной фильтрации

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

Пусть, как и раньше, обработке подвергается последовательность отсчетов {x(k)}, коэффициенты нерекурсивного фильтра порядка N образуют набор {wn}, а отсчеты образцового сигнала равны {d(k)}. Выходной сигнал фильтра определяется формулой (1), а ошибка воспроизведения образцового сигнала - формулой (2) или, в векторном виде, (3).

Теперь оптимизационная задача формулируется так: нужно отыскать такие коэффициенты фильтра {wn}, чтобы суммарная квадратичная ошибка воспроизведения образцового сигнала была минимальной:

(18)

Для решения задачи необходимо перейти в формуле (3) к матричной записи вдоль координаты k, получив формулы для векторов-столбцов выходного сигнала у и для ошибки воспроизведения входного сигнала е :

(19)

Здесь d - вектор-столбец отсчетов образцового сигнала, а X - матрица, столбцы которой представляют собой содержимое линии задержки фильтра на разных тактах:

Выражение (18) для для суммарной квадратичной ошибки можно переписать в матричном виде следующим образом:

(20)

Подставив (19) в (20), имеем:

Для нахождения минимума необходимо вычислить градиент данного функционала и приравнять его нулю:

Отсюда легко получается искомое оптимальное решение:

(21)

В формуле прослеживается близкое родство с формулой (8), описывающей оптимальный в статистическом смысле фильтр Винера. Действительно, если учесть, что дает оценку корреляционной матрицы сигнала, полученную по одной реализации эргодического случайного процесса путем временного усреднения, а является аналогичной оценкой взаимных корреляций между образцовым сигналом и содержимым линии задержки фильтра, то формулы (8) и (21) совпадут.