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

Алгоритм наименьших средних квадратов (Least Mean Squares, LMS) — это адаптивный алгоритм цифровой обработки сигналов, используемый для настройки коэффициентов линейного фильтра в режиме реального времени. Относится к классу методов стохастического градиентного спуска и применяется для минимизации среднеквадратической ошибки между выходным сигналом фильтра и эталонным (желаемым) сигналом. Алгоритм был предложен Бернардом Уидроу и Тедом Хоффом в 1960 году и является одним из наиболее распространённых в задачах адаптивной фильтрации, эхоподавления, идентификации систем и выравнивания каналов связи.

История

Разработка LMS-алгоритма связана с развитием теории адаптивной обработки сигналов в середине XX века. В 1959 году Бернард Уидроу, работавший в Стэнфордском университете, совместно с аспирантом Тедом Хоффом создал первый адаптивный фильтр на основе метода наименьших квадратов. В 1960 году они опубликовали статью «Adaptive Switching Circuits», где описали LMS-алгоритм как практический способ обучения нейроноподобных структур (адалайн). Впоследствии алгоритм получил широкое распространение благодаря своей простоте, низкой вычислительной сложности и способности работать в условиях нестационарных сигналов.

Принцип работы

Математическая основа

LMS-алгоритм решает задачу минимизации функции стоимости — среднеквадратической ошибки (MSE):

\[ J(\mathbf{w}) = E[e^2(n)] \]

где \( e(n) = d(n) - y(n) \) — ошибка на шаге \( n \), \( d(n) \) — желаемый сигнал, \( y(n) = \mathbf{w}^T(n) \mathbf{x}(n) \) — выход фильтра, \( \mathbf{w}(n) \) — вектор весовых коэффициентов, \( \mathbf{x}(n) \) — вектор входных отсчётов.

Вместо полного вычисления градиента (как в методе наименьших квадратов) LMS использует мгновенную оценку градиента:

\[ \nabla J(n) \approx -2 e(n) \mathbf{x}(n) \]

Обновление весов

Правило обновления весов имеет вид:

\[ \mathbf{w}(n+1) = \mathbf{w}(n) + 2\mu e(n) \mathbf{x}(n) \]

где \( \mu \) — шаг сходимости (коэффициент адаптации). Выбор \( \mu \) критичен для устойчивости и скорости сходимости алгоритма.

Классификация

По типу сигнала

• Стандартный LMS — для вещественных сигналов.
• Комплексный LMS — для обработки квадратурных сигналов (например, в радиосвязи).

По модификациям

• Нормализованный LMS (NLMS) — корректирует шаг адаптации в зависимости от энергии входного сигнала, что повышает устойчивость.
• Знаковый LMS (Sign-LMS) — использует только знак ошибки, снижая вычислительные затраты.
• С переменным шагом (VSLMS) — динамически изменяет \( \mu \) для улучшения компромисса между скоростью и точностью.

Характеристики

Преимущества

• Низкая вычислительная сложность — \( O(N) \) операций на итерацию, где \( N \) — порядок фильтра.
• Простота реализации — не требует хранения больших объёмов данных или обращения матриц.
• Работа в реальном времени — подходит для встраиваемых систем и DSP-процессоров.

Недостатки

• Медленная сходимость при коррелированных входных сигналах.
• Чувствительность к выбору шага — слишком большой \( \mu \) приводит к расходимости, слишком малый — к медленной адаптации.
• Не гарантирует глобальный минимум — может застревать в локальных минимумах при невыпуклых функциях стоимости.

Применение

Эхоподавление в телефонных сетях

LMS-алгоритмы используются в акустических и электрических эхокомпенсаторах для подавления отражённых сигналов. Например, в системах VoIP (Voice over IP) и цифровых телефонных станциях.

Идентификация систем

В задачах моделирования неизвестных динамических систем (например, в автоматике или сейсмологии) LMS позволяет оценить импульсную характеристику объекта.

Выравнивание каналов связи

В цифровых модемах и беспроводных системах (Wi-Fi, LTE) LMS-фильтры компенсируют межсимвольную интерференцию, вызванную многолучевым распространением.

Адаптивное подавление помех

В медицине (например, при обработке ЭКГ) LMS-алгоритмы удаляют шумы, сохраняя полезный сигнал. В радиолокации — для подавления активных помех.

Активное шумоподавление

В наушниках и автомобильных системах LMS-фильтры генерируют противофазный сигнал для нейтрализации внешнего шума.

Пример реализации

Ниже приведён псевдокод стандартного LMS-алгоритма для фильтра порядка \( N \):

`` Инициализация: w = [0, 0, ..., 0] (вектор длины N) Для каждого момента времени n: x = [x(n), x(n-1), ..., x(n-N+1)] y = dot(w, x) # выход фильтра e = d(n) - y # ошибка w = w + 2 mu e * x # обновление весов ``

Критика

Основная критика LMS-алгоритма связана с его зависимостью от выбора шага сходимости \( \mu \). В практических приложениях требуется либо предварительное тестирование, либо использование адаптивных методов (например, NLMS). Кроме того, при обработке нестационарных сигналов с быстро меняющимися характеристиками стандартный LMS может не успевать отслеживать изменения, что приводит к ухудшению качества фильтрации.

Интересные факты

• LMS-алгоритм является частным случаем более общего класса фильтров Винера, адаптированных для работы в реальном времени.
• В 1970-х годах алгоритм был реализован на первых цифровых сигнальных процессорах (DSP) компании Texas Instruments.
• Несмотря на возраст, LMS остаётся одним из самых изучаемых алгоритмов в учебных курсах по цифровой обработке сигналов.

Источники

• Widrow B., Hoff M. E. Adaptive Switching Circuits // IRE WESCON Convention Record. — 1960. — Vol. 4. — P. 96–104.
• Haykin S. Adaptive Filter Theory. — 5th ed. — Pearson, 2014.
• Diniz P. S. R. Adaptive Filtering: Algorithms and Practical Implementation. — 5th ed. — Springer, 2013.
• Sayed A. H. Adaptive Filters. — Wiley, 2008.