насколько я понял, лучше для оптимизации формулы X = (A^H * A)^-1 * A^H не отдельно оптимизировать умножение матриц и инверсию, а использовать псевдоинверсию.
но будет ли это менее затратно?

пусть матрица А имеет размерность [m x n], где m>n. используя псевдоинверсию и svd разложение получаем

X = V*S*U^H, где V - матрица порядка n, U - матрица порядка m, S - диагональная матрица размерностью [n x m];

перемножение этих матриц, плюс немалые затраты на svd разложение(с которым я еще до конца не разобрался)... будет ли это менее затратно, чем прямое вычисление по формуле X = (A^H * A)^-1 * A^H ?


кстати, матрица A у меня не совсем теплицевая.
теплицевыми являются матрицы A((1:2:end),: ) и A((2:2:end),: ).

но само перемножение A^H * A я могу делать пользуясь преимуществом теплицевой матрицы, т.к.
A^H * A = A((1:2:end),: )^H*A((1:2:end),: )+A((2:2:end),: )^H*A((2:2:end),: );

SVD операция затратная, но:
1) псевдоинверсия вычислительно устойчивый алгоритм
2) при переходе к матрице (A^H * A) вы будете работать с энергиями, т.к. это корреляционная матрица, разрядность вырастет в 2 раза, в общем случае вы не сможете откинуть добавочные разряды, т.к. потеряете информацию, которая в ней заключается (особенно это заметно в случае близком к вырождению, например АФАР, где собственные числа полезного сигнала много меньше собственных чисел помех).
3) SVD даст вам собственные числа матрицы данных, которые можно использовать с пользой в дальнейшем.
4) матрица данных у вас должна быть все таки Теплицевой или я чего то не понимаю, вы можете попробовать выиграть от SVD Теплицевой матрицы, а перейдя к (A^H * A) вы получете квадратную матрицу общего вида (она будет близка к Эрмитовой и тем ближе чем более длинные матрицы данных вы будете брать, но в общем случае она не Эрмитова, т.к. это только аппроксимация, поэтому я не уверен, что здесь можно выиграть от использования ее структуры)
5) если цель - алгоритм с фиксированной точкой, то по SVD есть литература как получить устойчивую имплементацию, хотя это будет сложно и весело. Можно в целых числах сделать инверсию (A^H * A) пользуясь QR декомпозицией, которая проще (и я бы даже мог поделиться матлабовскими скриптами по fixed point реализации), но см пункт 2 о росте разрядности.

В общем то, что я тут понаписал не претендует на истину в первой инстанции, т.к. я сам далеко не спец) но это мои соображения)

Сообщение отредактировал serjj - Apr 13 2015, 10:35

Странно у тебя получается. Вообще-то говоря, твоя X и есть псевдоинверсия матрицы A. Для ее вычисления нужно найти svd(A):

A = U*S*VH

S - диагональная

Тогда X = V*inv(S)*UH;

Инверсия S - просто инверсия элементов на главной диагонали.

andyp, мне кажется у него другая дилема: считать ли X = (A^H * A)^-1 * A^H напрямую или через X = V * S^-1 *U^H, с предварительным SVD. Мне кажется, что если бы вычисление напрямую было бы менее трудоёмким, то про 2й метод и не говорили бы

именно так


это радует

Она у меня не теплицевая, т.к. состовляется из двух разных импульсных характеристик. (на один символ приходится два отсчета.)
Если удалить из матрицы ряды через один, получиться теплицевая.


Интересует алгоритм с плавающей точкой

Вроде бы SVD будет наиболее эффективным вариантом, если требуется вычислить псевдоинверсию при этой структуре матрицы A. Кстати, такие "частично тёплицевы" матрицы вылазят в fractionally spaced эквалайзере.
Если это какой-то сорт MSE, то, может статься, что псевдоинверсия в замкнутом виде там и не нужна. Оптимальный вариант - обойтись без нее, что возвращает нас к статьям Al-Dhahir . У него там метод back substitution описан.

Сообщение отредактировал andyp - Apr 13 2015, 11:57

В моем случае используется DDE. Возможно ли в таком случае обойтись без псевдоинверсии? Может посоветуете какую-нибудь статью?

Так я ссылку приводил выше по теме именно на то, что нужно - быстрый способ вычисления весов в эквалайзере с обратной связью по решениям. Остальные роботы этого автора доступны здесь
http://www.utdallas.edu/~aldhahir/pubs.html

Виктор39, DDE = data directed equalizer? Который Nato STANAG*4285, Second example of demodulation technique?

да

UPD. Пардон, затупил. Произведение комплексных Теплицевых матриц вида A^H * A даёт Эрмитову, а вот при оценке автокорреляционной матрицы с увеличением времени оценки Эрмитова матрица стремится к реальной корреляционной у которой элементы на диагоналях, параллельных главной, равны (см. определение корреляционной матрицы).

В документе STANAG матрица весов W Теплицева, произведение W^H * W - Эрмитова матрица. Для обращения такой матрицы можно применить разложение Холецкого, которое легко сделать в арифметике с плавающей точкой. Разложение Холецкого устойчиво и требует меньше вычислений чем QR или SVD. Прямая инверсия матрицы тогда не понадобится, т.к. преобразование W^H * W к L*L^H приводит искомую систему линейных уравнений к двум треугольным. Про оптимизацию произведения Теплицевых матриц говорилось в начале темы.

Сообщение отредактировал serjj - Apr 14 2015, 08:04

объясните, почему инверсия матриц в таком случае не нужна?

Инверсия делается для решения системы линейных уравнений. Если систему можно переписать так, чтобы исключить прямую инверсию матрицы коэффициентов, то инверсия не нужна.
Удобным является приведение к треугольной форме, тогда система решается методом подстановки снизу/сверху. Разложение Холецкого представляет симметричную/Эрмитову матрицу в виде двух треугольных матриц: (W^H * W) = A = (L * L^H).
Исходная система: (W2^H * W2)*b = [W2^H * (r - W1*a)]
Полученная система: (L2 * L2^H)*b = [W2^H * (r - W1*a)]
Раскладываем её на 2 системы: L2 * t = [W2^H * (r - W1*a)] и L2^H * b = t.
И решаем их последовательно.

Сообщение отредактировал serjj - Apr 14 2015, 09:41

Общее замечание:
Воспоминания из студенческого прошлого говорят мне, что любую систему линейных уравнений можно атаковать например методом Гаусса. К инверсии можно обращаться, когда нужно решить дофига систем Ax = b для разных b. Матлаб, на сколько помню, тоже всегда советовал использовать x = A\b вместо x = inv(A)*b

Может статься, будет интересно
http://scicomp.stackexchange.com/questions...square-matrices

Сообщение отредактировал andyp - Apr 14 2015, 10:26

Познавательно насчёт матлаба


Это с точки зрения математики. А если смотреть на реализацию, то добавляются новые углы зрения. Для нас самый большой интерес представляют Теплицевы матрицы данных и Эрмитовы матрицы апроксимации автокорреляционной матрицы.

1) Если мы делаем обработку на процессоре с плавающей запятой, то можно решать СЛУ методом Холецкого, т.к. алгоритм имеет малое в сравнении с QR/LU для матриц общего вида количество вычислений; выполняется последовательно
2) Если мы делаем обработку на процессоре с фиксированной точкой, то возможно (?) выгоднее будет сделать QR/LU методом Гивенса или Хаусхолдера
3) Если мы делаем обработку на ПЛИС, то можно решать СЛУ через QR или SVD псевдоинверсию методом Гивенса, т.к. можно считать факторизацию параллельно на систолическом массиве из однообразных элементов
4) Еще есть класс быстрых алгоритмов, но они не все обладают устойчивостью и некоторые дают выигрыш только для очень больших матриц, поэтому это больше интересно для разгона научных вычислений