«Методы слепой обработки сигналов и их приложения в системах радиотехники и связи Москва Радио и связь 2003 УДК 621.396 Горячкин О.В. Методы слепой обработки сигналов и ...»
Пример 4.9. Пусть x( z ) кольцу C [z ] - случайный полином степени n 1, заданный случайным вектором с нулевым математическим ожиданием и независимыми компонентами. Тогда многообразие нулевой корреляции случайного полинома может быть факторизовано в объединение n 1 неприводимых многообразий:
Пример 4.10. Пусть x( z ) кольцу C [z ] - случайный полином перr01 0. Тогда вой степени, ковариация коэффициентов которого K1,1,0,0 (z1, z2 ) = r00 + r11z1z2 + r01(z1 + z2 ). Этот многочлен является приx водимым, только если r00 r11 r012 = 0. Что невозможно в силу свойств ковариации двух статистически связанных случайных величин, т.к.
r00 r11 r012. Т.о. в данном примере 1,1,0,0 (0 ) - неприводимо.
В рассмотренных примерах мы неявно использовали связь между неприводимыми многообразиями и простыми идеалами кольца полиномов. Для случая, когда многообразие порождается одним полиномом, его неприводимость эквивалентна просто неприводимости порождающего полинома. Если многообразие порождено набором полиномов, то его неприводимость связана с простотой соответствующего идеала (см. [57]).
4.2.2. Слепая идентификация канала, как решение системы полиномиальных уравнений Уравнение, связывающее полиномиальные кумулянты на входе и выходе идентифицируемой системы с пассивной паузой (Рис.1.3.б) можно записать в следующем виде:
K y k1,..., k r,m1,..., mr (z1, z2,..., zr ) = = h(z1 )k1...h(zr )k r h* (z1 )m1...h* (zr )mr K x k1,..., k r, m1,..., mr (z1, z2,..., zr ) + + K v k1,..., k r, m1,..., mr (z1, z2,..., zr ) В некоторых приложениях СОС, например, для систем связи, статистика передаваемого сообщения и аддитивного шума часто известна получателю. В этом случае, если бы мы имели точную оценку полиномиального кумулянта K y k1,...,kr,m1,...,mr (z1, z 2,..., z r ), то алгоритм идентификации сводился бы к элементарным операциям в кольце C [z1,..., zr ]. Конечно, нам доступны только выборочные статистики и в этом случае операция деления не всегда возможна, но кроме этого, для системы общего вида (Рис.1.3.а,г) полиномиальный момент выходного сигнала нельзя записать в виде линейных комбинаций полиномов в кольце C [z1,..., zr ] вида (4.72).
Для преодоления этих трудностей перепишем (2.21) в виде:
Тогда мы можем записать полиномиальные кумулянты выходной последовательности в кольце полиномов C [h0,..., hL 1, z1,..., zr ].
Уравнения для кумулянтов на входе и выходе системы можно записать, подставив (4.73) в (4.46). Например, для симметричных полиномиальных кумулянтов, эти уравнения имеют вид:
где: Fix,...,i (z1, z2,..., zr ) = cum xi1 (z1 )...xir (zr ).
Задавая различные точки в C r r = z1k ), z2k ),..., zrk ), k = 0,..., L из (4.74) получим систему L полиномиальных уравнений:
... hi1...hir Fi1x,...,ir z1(0),..., zr(0) + K rv z10),..., zr(0) и K ry z1,..., zr - выборочный полиномиальный кумулянт.
Данная система уравнений определяет аффинное многообразие f в C L и соответствующий ему идеал I = f 0,..., f L 1 в кольце полиномов C [h0,..., hL 1].
При решении системы (4.75) возможны два случая:
1) число решений конечно и не превосходит r L, т.е. многообразие (4.75) состоит из конечного множества точек в пространстве C L, или другими словами нульмерно;
2) число решений бесконечно, т.е. многообразие (4.75) является кривой, поверхностью или гиперповерхностью в C L, т.е. размерность его Этот факт хорошо известен в алгебраической геометрии как теорема Безу [67]. Идентифицируемость системы в данном случае тесно связана с вопросом о размерности многообразия f. Для алгебраически замкнутого поля (в нашем случае это так) размерность многообразия определяется аффинной функцией Гильберта идеала I f [57]. Определение размерности аффинного многообразия в общем случае довольно сложная задача.
Однако в большинстве случаев интуитивное представление о размерности геометрического объекта совпадает со строгим определением. Т.е. размерность точки – 0, кривой – 1, поверхности -2 и т.п.
В нашей задаче, при выполнении условий теорем статистической идентифицируемости канала Т.7 и Т.8, при соответствующем выборе r многообразия типа (4.75) обычно нульмерны, и имеют конечное множество решений.
Задача решения систем полиномиальных уравнений - это область современной математики тесно связанная с алгебраической геометрией и коммутативной алгеброй, причем некоторые существенные результаты в этой области получены относительно недавно, что стимулировало работы по получению новых методов решения задач в приложениях. Примером этому являются результаты данной главы.
Для решения полиномиальных систем небольшой размерности используются методы, основанные на теории результантов. Простые примеры решения полиномиальных систем можно найти в [1], общую теорию результантов в [57,68]. Использование данных методов для систем общего вида ограничено их громоздкостью.
В соответствии с теоремой Гильберта «О конечной порожденности идеала» любой идеал кольца C[h0,..., hL 1 ] имеет конечное число порождающих полиномов, составляющих базис идеала.
Поэтому один из возможных путей решения (4.75) - это выбор более подходящих для решения системы базисных полиномов идеала I f ( ) - множество всех полиномов кольца C[h0,..., hL1] нули коздесь I f торых f ).
Обычно для решения подобных систем выбирают базис Грёбнера, который состоит из полиномов, содержащих последовательно исключенные переменные h0,..., hL 1 [57].
Данный подход сводится к методу Гаусса при решении систем линейных уравнений. К сожалению, метод крайне сложен с вычислительной точки зрения и не адаптирован к ошибкам задания коэффициентов. Более приемлемый вариант этого алгоритма описан в [63].
Другой путь основан на теореме Штеттера [69]. Если f нульмерно, то факторкольцо C[h0,..., hL 1 ] I как векторное пространство изоморфно конечномерному векторному пространству T s.
Факторкольцом C[h0,..., hL 1 ] I по идеалу I называется множество классов эквивалентности по отношению к сравнимости по модулю I, т.е.:
Этот факт позволяет решать систему полиномиальных уравнений методами линейной алгебры. Традиционный путь решения системы (4.75), это сведение её к задаче поиска собственных чисел и векторов линейных операторов специального вида, определенных на конечномерном векторном пространстве, соответствующему факторкольцу C [h0,..., hL 1] I [57].
Пространство T s образовано линейным многообразием всех мономов {, t 2, t3,..., t s }, принадлежащих дополнению мономиального идеала LT (I ) (идеал, порожденный старшими мономами полиномов из I ) [57].
Этот факт позволяет свести задачу (4.75) к задаче поиска собственных значений линейных операторов специального вида, определенных на Ts.
Теорема Штеттера, полученная относительно недавно, является обобщением известного подхода к вычислению корней полинома от одной переменной через собственные числа матрицы Фробениуса.
Пусть M g - матрица линейного оператора, отображающая T s T s так, что для любого полинома g T s найдется (s s ) матрица M g с элементами mi, j, i, j = 0,..., s 1 такими, что:
При этом, если j, j = 0,..., s 1 - собственные числа матрицы M g, и ( j ) = ( 0,..., L 1 ) одно из (r) L решений системы уравнений (4.75), то собственное пространство соответствующее ненулевому собственному числу j может быть построено с помощью собственного вектора (1, t2 ( ( j ) ),..., ts ( ( j )).
Т.о. найдя все различные ненулевые собственные числа матрицы M g и соответствующие им собственные вектора, мы получим все решения системы полиномиальных уравнений (4.75).
Недостатком данного метода является неопределенность выбора полинома g T s и неустойчивость решения при возмущении коэффициентов системы уравнений (4.75). Для преодоления последнего недостатка мы пользуемся далее методом регуляризации.
Т.о., используя полиномиальные статистики, мы свели решение задачи слепой идентификации к задаче решения систем полиномиальных уравнений от многих переменных [63,65].
Данный подход является обобщением подхода, основанного на использовании полиспектров (п. 4.1.1). Соответственно предложенному методу присущи и некоторые общие недостатки методов, использующих моментные и кумулянтные функции. Это, прежде всего медленная сходимость получаемых оценок. Однако, как мы покажем далее, в рамках используемого подхода мы будем иметь возможности дополнительной оптимизации параметров алгоритма.
Проиллюстрируем эти возможности на примере слепой идентификации скалярного канала с нестационарным входом по статистикам второго порядка. Запишем уравнение полиномиальных кумулянтов 2-го порядка, соответствующих модели системы вида (4.75) в виде:
В частности, если отсчеты входного сигнала некоррелированны, имеют нестационарную дисперсию i2 и нулевое математическое ожидание, то соответствующие полиномиальные моменты входной последовательности в (4.79) имеют вид:
Задавая различные точки в C 2, соответствующие значениям форk ) (k ) мальным переменных ( z1, z 2 ), k = 0,..., s 1 в (4.78), получим систему полиномиальных уравнений (4.75), связывающую искомые переменные h0, h1,..., hL 1.
Для идентифицируемой системы число решений конечно и не превосходит 2 L.
Заметим, что все полиномы системы уравнений (4.75) образованы мономами вида hi h j. Введем новые переменные {u1, u2,..., u s }, где систему (4.75) можно записать в виде системы линейных уравнений:
где: элементы матрицы P, pk,m = Fixm ), j (m ) z1k ), z2k ), а элементы вектора q, qk = K 2,0 z1, z2 K 2,0 z1, z 2. Если выполняются условия идентифицируемости, заданные теоремой Т.8, то система уравнений (4.81) совместна и ранг матрицы P равен s. Тогда найдется единственный вектор (1,..., s ), такой, что система (4.75), эквивалентна системе полиномиальных уравнений вида:
Для системы уравнений (4.82) легко определить мономы, принадлежащие дополнению мономиального идеала LT (I ), это 1, h0,...hL 1.
Пусть g = h0, тогда матрица M g имеет вид:
У такой матрицы только два собственных числа будут отличны от нуля, что соответствует 2-м решениям системы (4.75), отличающимся на постоянный множитель. Пусть - собственный вектор соответствующий ненулевому собственному числу матрицы M g, тогда оценка канала непосредственно дается ( 2,... L +1 ) компонентами вектора.
Поскольку вектор q системы (4.81) известен нам с погрешностью, вызванной аддитивным шумом и использованием выборочной ковариационной матрицы наблюдаемых сигналов, то решение системы будет сопровождаться погрешностью, величина которой зависит от отношения сигнал шум и числа реализаций сигнала, используемых для оценки ковариационной матрицы. Поэтому для решения системы (4.81) мы используем метод регуляризации Тихонова.
Как отмечалось выше, недостатком метода Штеттера является неопределенность выбора матрицы M g. Однако для решения простых систем полиномиальных уравнений типа (4.82) мы можем использовать базис Грёбнера.
Если система уравнений (4.82) совместна и ранг матрицы P равен где 1, 2,..., s единственное решение (4.81), а {u1, u2,..., u s } это, мономы в C [h0,..., hL 1 ].
Вычисляя базис Грёбнера идеала u1 1, u2 2,..., u s s, полуg1,..., g L, где образующие полиномы содержат последовачим идеал тельно исключенные переменные кольца C [h0,..., hL 1].
Конечно, теоретически возможно построение базиса Грёбнера идеала I непосредственно по полиномам f 0,..., f L 1, однако обычно вычисление базиса в кольце полиномов над полем комплексных чисел крайне трудная задача, особенно в общем виде, поэтому сведение множества формирующих полиномов идеала к полиномам более простого вида сложно переоценить.