Эта статья
требует дополнительных ссылок для проверки .
Пожалуйста, помогите улучшить эту статью , добавив цитаты из надежных источников . Материал, не полученный от источника, может быть оспорен и удален. Найти источники: «Псевдообратная матрица блоков» - новости · газеты · книги · ученый · JSTOR ( декабрь 2010 г. ) ( Узнайте, как и когда удалить это сообщение-шаблон )
В математике , А блок - матрица Псевдообратный является формулой для псевдообратных из в секционированной матрице . Это полезно для разложения или аппроксимации многих алгоритмов обновления параметров при обработке сигналов , которые основаны на методе наименьших квадратов .
Рассмотрим разделенную по столбцам матрицу:
[ А B ] , А ∈ р м × п , B ∈ р м × п , м ≥ п + п . {\ displaystyle {\ begin {bmatrix} \ mathbf {A} & \ mathbf {B} \ end {bmatrix}}, \ quad \ mathbf {A} \ in \ mathbb {R} ^ {m \ times n}, \ quad \ mathbf {B} \ in \ mathbb {R} ^ {m \ times p}, \ quad m \ geq n + p.} Если указанная выше матрица полного ранга, обратные матрицы Мура – Пенроуза к ней и ее транспонирование равны
[ А B ] + знак равно ( [ А B ] Т [ А B ] ) - 1 [ А B ] Т , [ А Т B Т ] + знак равно [ А B ] ( [ А B ] Т [ А B ] ) - 1 . {\displaystyle {\begin{aligned}{\begin{bmatrix}\mathbf {A} &\mathbf {B} \end{bmatrix}}^{+}&=\left({\begin{bmatrix}\mathbf {A} &\mathbf {B} \end{bmatrix}}^{\textsf {T}}{\begin{bmatrix}\mathbf {A} &\mathbf {B} \end{bmatrix}}\right)^{-1}{\begin{bmatrix}\mathbf {A} &\mathbf {B} \end{bmatrix}}^{\textsf {T}},\\{\begin{bmatrix}\mathbf {A} ^{\textsf {T}}\\\mathbf {B} ^{\textsf {T}}\end{bmatrix}}^{+}&={\begin{bmatrix}\mathbf {A} &\mathbf {B} \end{bmatrix}}\left({\begin{bmatrix}\mathbf {A} &\mathbf {B} \end{bmatrix}}^{\textsf {T}}{\begin{bmatrix}\mathbf {A} &\mathbf {B} \end{bmatrix}}\right)^{-1}.\end{aligned}}} Это вычисление псевдообратной матрицы требует обращения ( n + p ) -квадратной матрицы и не использует блочную форму.
Чтобы сократить вычислительные затраты до обращения n- и p- квадратных матриц и ввести параллелизм, рассматривая блоки отдельно, выводится [1]
[ A B ] + = [ P B ⊥ A ( A T P B ⊥ A ) − 1 P A ⊥ B ( B T P A ⊥ B ) − 1 ] = [ ( P B ⊥ A ) + ( P A ⊥ B ) + ] , [ A T B T ] + = [ P B ⊥ A ( A T P B ⊥ A ) − 1 , P A ⊥ B ( B T P A ⊥ B ) − 1 ] = [ ( A T P B ⊥ ) + ( B T P A ⊥ ) + ] , {\displaystyle {\begin{aligned}{\begin{bmatrix}\mathbf {A} &\mathbf {B} \end{bmatrix}}^{+}&={\begin{bmatrix}\mathbf {P} _{B}^{\perp }\mathbf {A} \left(\mathbf {A} ^{\textsf {T}}\mathbf {P} _{B}^{\perp }\mathbf {A} \right)^{-1}\\\mathbf {P} _{A}^{\perp }\mathbf {B} \left(\mathbf {B} ^{\textsf {T}}\mathbf {P} _{A}^{\perp }\mathbf {B} \right)^{-1}\end{bmatrix}}={\begin{bmatrix}\left(\mathbf {P} _{B}^{\perp }\mathbf {A} \right)^{+}\\\left(\mathbf {P} _{A}^{\perp }\mathbf {B} \right)^{+}\end{bmatrix}},\\{\begin{bmatrix}\mathbf {A} ^{\textsf {T}}\\\mathbf {B} ^{\textsf {T}}\end{bmatrix}}^{+}&={\begin{bmatrix}\mathbf {P} _{B}^{\perp }\mathbf {A} \left(\mathbf {A} ^{\textsf {T}}\mathbf {P} _{B}^{\perp }\mathbf {A} \right)^{-1},\quad \mathbf {P} _{A}^{\perp }\mathbf {B} \left(\mathbf {B} ^{\textsf {T}}\mathbf {P} _{A}^{\perp }\mathbf {B} \right)^{-1}\end{bmatrix}}={\begin{bmatrix}\left(\mathbf {A} ^{\textsf {T}}\mathbf {P} _{B}^{\perp }\right)^{+}&\left(\mathbf {B} ^{\textsf {T}}\mathbf {P} _{A}^{\perp }\right)^{+}\end{bmatrix}},\end{aligned}}} где ортогональные проекционные матрицы определяются как
P A ⊥ = I − A ( A T A ) − 1 A T , P B ⊥ = I − B ( B T B ) − 1 B T . {\displaystyle {\begin{aligned}\mathbf {P} _{A}^{\perp }&=\mathbf {I} -\mathbf {A} \left(\mathbf {A} ^{\textsf {T}}\mathbf {A} \right)^{-1}\mathbf {A} ^{\textsf {T}},\\\mathbf {P} _{B}^{\perp }&=\mathbf {I} -\mathbf {B} \left(\mathbf {B} ^{\textsf {T}}\mathbf {B} \right)^{-1}\mathbf {B} ^{\textsf {T}}.\end{aligned}}} Приведенные выше формулы не обязательно действительны, если не имеет полного ранга - например, если , то [ A B ] {\displaystyle {\begin{bmatrix}\mathbf {A} &\mathbf {B} \end{bmatrix}}} A ≠ 0 {\displaystyle \mathbf {A} \neq 0}
[ A A ] + = 1 2 [ A + A + ] ≠ [ ( P A ⊥ A ) + ( P A ⊥ A ) + ] = 0 {\displaystyle {\begin{bmatrix}\mathbf {A} &\mathbf {A} \end{bmatrix}}^{+}={\frac {1}{2}}{\begin{bmatrix}\mathbf {A} ^{+}\\\mathbf {A} ^{+}\end{bmatrix}}\neq {\begin{bmatrix}\left(\mathbf {P} _{A}^{\perp }\mathbf {A} \right)^{+}\\\left(\mathbf {P} _{A}^{\perp }\mathbf {A} \right)^{+}\end{bmatrix}}=0} Применение к задачам наименьших квадратов [ править ] Учитывая те же матрицы, что и выше, мы рассматриваем следующие задачи наименьших квадратов, которые проявляются как множественные целевые оптимизации или проблемы с ограничениями при обработке сигналов. В конце концов, мы можем реализовать параллельный алгоритм наименьших квадратов на основе следующих результатов.
Разделение по столбцам в переопределенных методах наименьших квадратов [ править ] Предположим, решение решает переопределенную систему: x = [ x 1 x 2 ] {\displaystyle \mathbf {x} ={\begin{bmatrix}\mathbf {x} _{1}\\\mathbf {x} _{2}\\\end{bmatrix}}}
[ A , B ] [ x 1 x 2 ] = d , d ∈ R m × 1 . {\displaystyle {\begin{bmatrix}\mathbf {A} ,&\mathbf {B} \end{bmatrix}}{\begin{bmatrix}\mathbf {x} _{1}\\\mathbf {x} _{2}\\\end{bmatrix}}=\mathbf {d} ,\quad \mathbf {d} \in \mathbb {R} ^{m\times 1}.} Используя псевдообратную блочную матрицу, имеем
x = [ A , B ] + d = [ ( P B ⊥ A ) + ( P A ⊥ B ) + ] d . {\displaystyle \mathbf {x} ={\begin{bmatrix}\mathbf {A} ,&\mathbf {B} \end{bmatrix}}^{+}\,\mathbf {d} ={\begin{bmatrix}\left(\mathbf {P} _{B}^{\perp }\mathbf {A} \right)^{+}\\\left(\mathbf {P} _{A}^{\perp }\mathbf {B} \right)^{+}\end{bmatrix}}\mathbf {d} .} Следовательно, у нас есть разложенное решение:
x 1 = ( P B ⊥ A ) + d , x 2 = ( P A ⊥ B ) + d . {\displaystyle \mathbf {x} _{1}=\left(\mathbf {P} _{B}^{\perp }\mathbf {A} \right)^{+}\,\mathbf {d} ,\quad \mathbf {x} _{2}=\left(\mathbf {P} _{A}^{\perp }\mathbf {B} \right)^{+}\,\mathbf {d} .} Разделение по строкам методом наименьших квадратов [ править ] Предположим, что решение решает недоопределенную систему: x {\displaystyle \mathbf {x} }
[ A T B T ] x = [ e f ] , e ∈ R n × 1 , f ∈ R p × 1 . {\displaystyle {\begin{bmatrix}\mathbf {A} ^{\textsf {T}}\\\mathbf {B} ^{\textsf {T}}\end{bmatrix}}\mathbf {x} ={\begin{bmatrix}\mathbf {e} \\\mathbf {f} \end{bmatrix}},\quad \mathbf {e} \in \mathbb {R} ^{n\times 1},\quad \mathbf {f} \in \mathbb {R} ^{p\times 1}.} Решение с минимальной нормой дается формулой
x = [ A T B T ] + [ e f ] . {\displaystyle \mathbf {x} ={\begin{bmatrix}\mathbf {A} ^{\textsf {T}}\\\mathbf {B} ^{\textsf {T}}\end{bmatrix}}^{+}\,{\begin{bmatrix}\mathbf {e} \\\mathbf {f} \end{bmatrix}}.} Используя псевдообратную блочную матрицу, имеем
x = [ ( A T P B ⊥ ) + ( B T P A ⊥ ) + ] [ e f ] = ( A T P B ⊥ ) + e + ( B T P A ⊥ ) + f . {\displaystyle \mathbf {x} ={\begin{bmatrix}\left(\mathbf {A} ^{\textsf {T}}\mathbf {P} _{B}^{\perp }\right)^{+}&\left(\mathbf {B} ^{\textsf {T}}\mathbf {P} _{A}^{\perp }\right)^{+}\end{bmatrix}}{\begin{bmatrix}\mathbf {e} \\\mathbf {f} \end{bmatrix}}=\left(\mathbf {A} ^{\textsf {T}}\mathbf {P} _{B}^{\perp }\right)^{+}\,\mathbf {e} +\left(\mathbf {B} ^{\textsf {T}}\mathbf {P} _{A}^{\perp }\right)^{+}\,\mathbf {f} .} Вместо этого нам нужно вычислить прямо или косвенно [ необходима цитата ] [ оригинальное исследование? ] ( [ A B ] T [ A B ] ) − 1 {\displaystyle \mathbf {\left({\begin{bmatrix}\mathbf {A} &\mathbf {B} \end{bmatrix}}^{\textsf {T}}{\begin{bmatrix}\mathbf {A} &\mathbf {B} \end{bmatrix}}\right)} ^{-1}}
( A T A ) − 1 , ( B T B ) − 1 , ( A T P B ⊥ A ) − 1 , ( B T P A ⊥ B ) − 1 . {\displaystyle \left(\mathbf {A} ^{\textsf {T}}\mathbf {A} \right)^{-1},\quad \left(\mathbf {B} ^{\textsf {T}}\mathbf {B} \right)^{-1},\quad \left(\mathbf {A} ^{\textsf {T}}\mathbf {P} _{B}^{\perp }\mathbf {A} \right)^{-1},\quad \left(\mathbf {B} ^{\textsf {T}}\mathbf {P} _{A}^{\perp }\mathbf {B} \right)^{-1}.} В плотной и небольшой системе мы можем использовать разложение по сингулярным числам , QR-разложение или разложение Холецкого, чтобы заменить инверсию матриц числовыми процедурами. В большой системе мы можем использовать итерационные методы, такие как методы подпространства Крылова.
Рассматривая параллельные алгоритмы , мы можем вычислять и параллельно. Затем мы заканчиваем вычисления, и тоже параллельно. ( A T A ) − 1 {\displaystyle \left(\mathbf {A} ^{\textsf {T}}\mathbf {A} \right)^{-1}} ( B T B ) − 1 {\displaystyle \left(\mathbf {B} ^{\textsf {T}}\mathbf {B} \right)^{-1}} ( A T P B ⊥ A ) − 1 {\displaystyle \left(\mathbf {A} ^{\textsf {T}}\mathbf {P} _{B}^{\perp }\mathbf {A} \right)^{-1}} ( B T P A ⊥ B ) − 1 {\displaystyle \left(\mathbf {B} ^{\textsf {T}}\mathbf {P} _{A}^{\perp }\mathbf {B} \right)^{-1}}
Внешние ссылки [ править ] Справочное руководство по матрице Майка Брукса Линейная алгебра Глоссарий по Джону Burkardt Матрица Cookbook по Kaare Brandt Петерсен Лекция 8: Решения неопределенных уравнений по наименьшей норме [1] [ постоянная мертвая ссылка ] tanford.edu/~boyd/ Стивен П. Бойд] Плавающая запятая Численная стабильность Система линейных уравнений Матричные разложения Умножение матриц ( алгоритмы ) Расщепление матрицы Редкие проблемы Кеш процессора TLB Алгоритм без кеширования SIMD Многопроцессорность MATLAB Подпрограммы базовой линейной алгебры (BLAS) ЛАПАК Специализированные библиотеки Программное обеспечение общего назначения