Немного запутался с минимальной дисперсией ошибки этих алгоритмов.

Оптимальной (в смысле MSE) является винеровская фильтрация. Дисперсия ошибки будет минимальной. Метод наименьших квадратов (МНК, Least Squares (LS)) является детерминированным аналогом винеровской фильтрации. Напрямую МНК не используют, чтобы каждый раз не обращать увеличивающиеся матрицы. Вместо него используют РНК (RLS) алгоритм. Я правильно понимаю, что RLS по сути является эффективной реализацией МНК в плане вычислений, обеспечивая при этом такую же дисперсию ошибки, как тупое вычисление здоровых матриц в МНК? Разве что кроме некоторого переходного процесса при поступлении на вход первых N отсчетов. В литературе приводятся формулы для RLS, но в одной книге нашел, где они обозначаются как LS. То есть в плане дисперсии ошибки LS и RLS абсолютно идентичны?

Имхо фильтрация Винера предполагает точное знание статистик второго порядка. LMS, RLS используют входные данные для оценки требуемых корреляций. В случае стационарных процессов и для установившегося режима (когда алгоритм сбежался) для LMS, RLS имеем веса фильтра как случайный процесс с некой дисперсией и мат. ожиданием, равным винеровскому решению. Это приводит к дополнительному по отношению к винеровскому решению шуму на выходе. Шум оценивают как excess MSE (разность мощности шума в установившемся режиме и шума винеровского решения). В случае LMS excess MSE зависит от параметра сходимости и следа корр. матрицы. В случае RLS (на сколько помню) от параметра forgetting factor при оценке элементов корр. матрицы. От следа не зависит. В принципе, для каждого стационарного входа можно так подобрать параметры RLS и LMS, чтобы в установившемся режиме была одинаковая дисперсия. Характер сходимости будет разный.

PS подробности можно найти в Behrouz Farhang-Boroujeny, Adaptive Filters: Theory and Applications

Сообщение отредактировал andyp - Mar 14 2018, 21:40

Спасибо за ответ. Только я имел в виду не LMS, а LS. Сам постоянно путаюсь в названиях, которые исторически так сложилось, но не отражают сути. С LMS понятно. Я чего-то задумался про сравнение RLS и прямой оценке по МНК, при которой на каждом шаге обращались бы матрицы полностью (увеличивающиеся в размерности). По сути ведь в RLS по сравнению с МНК нет никаких аппроксимаций и приближения, значит должны давать одинаковую ошибку, которая хуже Винера, но при бесконечном числе отсчетов на входе стремится к винеровскому решению.

UPD. Добавил картинки.



На первой формула (3.7) - это и есть МНК "в лоб". На второй картинке говорится о дисперсии ошибки оценки для этого метода при большом числе входных отсчетов n. На третьей подчеркнуто, что в RLS (РНК) дисперсия убывает пропорционально отношению (N/n), где N - число коэффициентов. Интересно, а вот как связаны дисперсии ошибки для МНК и RLS (РНК) при малых n. Здесь я подвис. Ведь RLS получается из (3.7) лишь путем различных матричных преобразований. Вроде бы тогда ошибки должны быть одинаковы.

P.S. Есть некая относительно небольшая выборка с постоянными коэффициентами, подлежащими оценке. Хочу, не прибегая пока к моделированию, разобраться с точностью оценки по МНК и РНК...

Ух, кажется понял о чем Вы. МНК от RLS отличается тем, что в одном случае (МНК) для оценки используется невзвешенная сумма n отсчетов, в случае RLS - всегда взвешенная (лямбда меньше 1 в терминах Вашей книжки) . Ну т.е. в случае MHK используются все входные отсчеты с одинаковым весом 1/n, в случае RLS для усреднения используется БИХ фильтр с параметром лямбда. Поэтому даже в асимптоте (n->Бесконечность)там перед оценками множитель вида (1-lambda)/(1+lambda) будет и соответствующая ошибка. MHK при бесконечном усреднении и эргодических процессах на входе даст стремящуюся к 0 по отношению к винеровскому фильтру ошибку.

При lambda близкой к 1, n много большей N (длина фильтра в Вашей книжке) для эргодических процессов на входе множитель (1+lambda)/(1-lambda) будет сколь угодно близок к 1 и ошибка будет примерно одинаковой.

Да. Я как раз про эту ситуацию. А вот теперь самое интересное Есть входная выборка отсчетов, в пределах которой коэффициент передачи канала можно считать постоянным. Производится его оценка. Нужно без лишней задержки на обработку выдавать оценки для демодулятора. Допустим, коэффициентов для оценки 10, а длина входного вектора - 100. Отношение N/n = 0,1. Тут напрашивается RLS (lambda = 1). После поступления очередного отсчета идет переоценка h. Очевидно, что BER будет хуже по сравнению со случаем, когда бы я дождался всего блока на входе, решил один раз задачу МНК и с полученными оценками h произвел демодуляцию сразу для всего блока. Теоретически я могу вместо RLS каждый раз "в лоб" решать МНК по формуле (3.7) при этом размер вектора будет постоянно увеличиваться: 1, 2, 3, ... 100. На каждой следующей итерации нужно будет решать все бОльшую систему целиком. Это, разумеется, неоптимально по вычислительным затратам. Но я не могу до конца понять, не будет ли в данном случае дисперсия ошибки меньше, чем в RLS. Наверное, нет. В моем первом посте на правом рисунке из обозначений в формулах выходит, что дисперсии одинаковы для МНК и RLS, при малых N/n они хуже оптимальных, но с увеличением длины выборки к ним стремятся. Это самый волнующий меня вопрос Какие-то сомнения всё-таки присутствуют...

Т.е. МНК по доступным данным vs RLS по доступным данным? Все эти excess MSE дают нижнюю границу оценки ошибки и асимптотику. На коротких выборках и то и то будет плохо имхо (ну т.е. хуже чем эта граница).

Давайте посмотрим на оценку КФ в случае RLS с параметром lambda = l и квадратами входов X_i

В случае усреднения двух отсчетов будем иметь
l*X_1 + (1-l)*X_2 против 0.5*X_1 + 0.5 *X_2 для MHK

Для трех
l^2 *X_1 + l*(1-l)*X_2 + (1-l)*X_3 против 1/3*X_1 + 1/3*X_2 + 1/3*X_1 для MHK

Справа - наилучшая оценка КФ, которую можно получить по доступным данным.

Имхо, то что слева будет хуже того, что справа, пока не усредняем K*(1/(1-l)) отсчетов, где K - примерно 10 (каждые 1/(1-l) отсчетов excess MSE RLS убывает в e раз)

Сообщение отредактировал andyp - Mar 15 2018, 10:55

Согласен. Аналогично думал.


Спасибо большущее за это. Прояснилась картина.

UPD.: Хм, а ведь при постоянном значении коэффициентов в RLS без экспоненциального затухания lambda = 1 (канал не меняется из-за полосы/времени когерентности, скажем, на 100 отсчетах). Тогда члены (1-l) становятся равны нулю. Не совсем понял, как быть в этом случае. То есть задача сводится вообще к примитивнейшей, поскольку фильтрация должна быть с одинаковыми весами. По идее должно быть вырождение в МНК в этом случае. Так?

С l = 1 работать не будет. Оценки корр. функции считаются по следующей формуле
R_n = l*R_n-1 + (1-l)*X_n

Фактически это экспоненциальное усреднение БИХ фильтром первого порядка. В зависимости от l серединка окна будет браться с большими весами, а к краям окна веса будут спадать.

Такая форма получения оценки КФ зашита внутрь RLS и именно она позволяет считать обновления сразу для обратной матрицы.

С этим утверждением не соглашусь. На 3-5 слайдах написано об этом случае: https://www-sigproc.eng.cam.ac.uk/foswiki/p...ain/4F7/rls.pdf Для стационарных процессов равенство единице имеет место. В этом случае потребуется "бесконечная" память, а все веса будут равны. Для моей блоковой задачи размер памяти будет соответствовать размеру блока.
Почитал за день разные книги по адаптивной фильтрации, в том числе отечественные. В учебнике Сергиенко по ЦОС нашел ответ и на начальный мой вопрос. Получается, что, по крайней мере, для стационарных процессов без экспоненциального забывания, дисперсии ошибок должны совпадать с МНК, поскольку в целевой функции веса идентичны у слагаемых. Меня смущало, что, возможно, я не до конца понимаю переход от МНК к его рекурсивной реализации и не вижу каких-то преобразований, которые ухудшают дисперсию.

Первый абзац про коэффициенты, ниже про лямбду.


Формула 9.21 относится к оптимальному фильтру по МНК: w = (XX^T)^(-1)d.

Да, был не прав.

рекурсия выглядит как

R_n = l*R_n-1 + X_n.

Тогда все сработает.

Спасибо за участие в обсуждении и помощь. Помогли понять, на что обратить внимание.