Участник:Василий Ломакин/Псевдообратная матрица

Материал из MachineLearning.

Версия от 15:18, 12 ноября 2008; Василий Ломакин (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

Псевдообратные матрицы — обобощение обратных матриц в математике и, в частности, в линейной алгебре. Псевдообратная матрица к матрице $A$ обозначается $A^+$ . Наиболее известно псевдообращение Мура — Пенроуза, которое было независимо описано Э. Х. Муром и Роджером Пенроузом. Концепцию псевдообратных интегрирующих операторов в 1903 году представил Фредгольм. Термин «обобщенное обращение» иногда используется как синоним для псевдообращения. Псевдообращение можно понимать как наилучшую апроксимацию (по методу наименьших квадратов) решения соответствующей системы линейных уравнений (см. далее в применении). Псевдообращение определено для любых матриц над действительными и комплексными числами. Псевдообратная матрица может быть вычислена с помощью собственного представления матрицы.

Определение

$A^+$ называется псевдообратной матрицей для матрицы $A$ , если она удовлетворяет следующим критериям:

$A A^+A = A;$
$A^+A A^+ = A^+$ ( $A^+$ является слабым обращением в мультипликативной полугруппе);
$(AA^+)^* = AA^+$ (это означает, что $AA^+$ — эрмитова матрица);
$(A^+A)^* = A^+A$ ( $A^+A$ - тоже эрмитова матрица).

Здесь $M^*$ - эрмитова сопряжённая матрица M. Для матриц над полем действительных чисел $M^* = M^T$ .

Существует эквивалентный способ задания псевдообратной матрицы через предел обратных:

$A^+ = \lim_{\delta \to 0} (A^* A + \delta I)^{-1} A^* = \lim_{\delta \to 0} A^* (A A^* + \delta I)^{-1}$

(смотрите регуляризация Тихонова). Этот предел существует, даже если $(A A^*)^{-1}$ и $(A^* A)^{-1}$ не определены.

Свойства

Псевдообращение обратимо, более того, эта операция обратна самой себе:
$(A^+)^+ = A$ .
Псевдообращение нулевой матрицы равно транспонированию.
Псевдообращение комутирует с транспонированием, сопряжением и эрмитовым сопряжением:
$(A^T)^+ = (A^+)^T$ ,
$(\overline{A})^+ = \overline{A^+}$ ,
$(A^*)^+ = (A^+)^* .$
Псевдообратное произведения матрицы $A$ на скаляр $\alpha$ равно соответствующему произведению матрицы $A^+$ на обратное число $\alpha^{-1}$ :
$(\alpha A)^+ = \alpha^{-1} A^+$ , для $\alpha$ ≠ 0.
Если псевдообратная матрица для $A^*A$ уже известна, она может быть использовано для вычисления $A^+$ :
$A^+ = (A^*A)^+A^*$ .
Аналогично, если матрица $(AA^*)^+$ уже известна:
$A^+ = A^*(AA^*)^+$ .

Особые случаи

Если столбцы матрицы $A$ линейно независимы, тогда матрица $A^* A$ обратима. В таком случае псевдообратная матрица задаётся формулой

$A^+ = (A^* A)^{-1} A^*.$

Это эквивалентно тому, что в первой части определения через предел убирается слагаемое с $\delta$ . Отсюда следует что $A^+$ - левая обратная матрица для A: $A^+ A = I$ .

Если строки матрицы $A$ линейно независимы, тогда матрица $A A^*$ обратима. В таком случае псевдообратная матрица задаётся формулой

$A^+ = A^*(A A^*)^{-1}.$

Это эквивалентно тому, что во второй части определения через предел убирается слагаемое с $\delta$ . Отсюда следует, что $A^+$ — правая обратная матрица для A: $A A^+ = I$ .

Если и столбцы и строки линейно независимы (что верно для квадратных невырожденных матриц), псевдообращение равно обращению:

$A^+ = A^{-1} .$

Если A и B таковы, что произведение определено, и
- либо $A^* A = I$ ,
- либо $B B^* = I$ ,
- либо столбцы $A$ линейно независимы и строки $B$ линейно независимы,

тогда

$(AB)^+ = B^+ A^+$ .

Псевдообращение можно применять и к скалярам, и к векторам. Это подразумевает, что их будут считать матрицами. Псевдообратный к скаляру $x$ — ноль, если $x$ — ноль, и обратный к $x$ в противном случае:

$x^+ = \left\{\begin{matrix} 0, & x=0; \\ x^{-1}, & x \ne 0. \end{matrix}\right.$

Псевдообратный для нулевого вектора - транспонированый нулевой вектор. Псевдообратный для иного вектора - сопряжённый транспонированный вектор, делённый на квадрат своей длины:

$x^+ = \left\{\begin{matrix} 0^T, & x = 0; \\ {x^* \over x^* x}, & x \ne 0. \end{matrix}\right.$

Для доказательства достаточно проверить, что эти величины удовлетворяют определению псевдообратных.

Происхождение

Если $(A^* A)^{-1}$ существует, то

$Ax = b,$

$A^* A x = A^* b,$

$(A^* A)^{-1}(A^* A) x = (A^* A)^{-1}A^* b,$

$x = (A^* A)^{-1}A^* b,$

что порождает понятие псевдообращения

$A^+ = (A^* A)^{-1}A^*$ .

Вычисление

Пусть k - ранг матрицы A размера $m \times n$ . Тогда A может быть представлена как $A = BC$ , где B — матрица размера $m \times k$ и C — матрица размера $k \times n$ . Тогда

$A^+ = C^*(CC^*)^{-1}(B^*B)^{-1}B^*.$

Если A имеет полнострочный ранг, то есть k = m, тогда в качестве B может быть выбрана единичная матрица и формула сокращается до $A^+ = A^*(AA^*)^{-1}$ . Аналогично, если A имеет полностолбцовый ранг, то есть, k = n, имеем $A^+ = (A^*A)^{-1}A^*.$

Простейший вычислительный путь получения псевдообратной матрицы — использование собственного представления матрицы (СПМ).

Если $A = U\Sigma V^*$ — собственное представление A, тогда $A^+ = V\Sigma^+ U^*.$ Для диагональной матрицы, такой как $\Sigma$ , псевдообратная вычисляется обращением каждого ненулевого элемента на диагонали.

Существуют оптимизированые подходы для вычисления псевдоинверсии блочных матриц.

Если псевдоинверсия известна для некой матрицы и нужно найти псевдоинверсию для аналогичной матрицы, иногда она может быть вычислена с помощью специальных алгоритмов, требующих меньшего количества расчётов. В частности, если аналогичная матрица отличается от начальной на один изменённый, добавленный или удалённый столбец или строку — существуют накопительные алгоритмы, которые могут использовать взаимосвязь между матрицами.

Применение

Псевдоинверсия реализирует решение метода наименьших квадратов для системы линейных уравнений.

При этом для данной системы $A x = b$ ищется вектор $x$ , котрый минимизирует невязку $\|A x - b\|^2$ , где $\|\,\cdot\,\|$ обозначает евклидову норму.

Общее решение неоднородной системы $A x = b$ представимо как сумма частного решения неоднородной системы и общего решения соответствующей однородной системы $A x = 0$ .

Лемма: Если $(A A^*)^{-1}$ существует, тогда решение $x$ всегда представимо как сумма решения псевдообратного решения неоднородной системы и решения однородной системы:

$x = A^*(A A^*)^{-1}b + (1 - A^*(A A^*)^{-1} A)y.$

Доказательство:

$Ax$	$=$	$A A^(A A^)^{-1}$	$b$	$+$	$A y - A A^(A A^)^{-1} A y$
	$=$		$b$	$+$	$A y - A y$
	$=$		$b$	.

Здесь вектор $y$ случаен (с точностью до размерности). В двух других членах есть псевдообратная матрица $A^*(A A^*)^{-1}$ . Переписав её в форме $A^+$ , приведём выражение к форме:

$x = A^+ b + (1 - A^+ A)y.$

Первый член — псевдообратное решение. В терминах метода наименьших квадратов — это наилучшее приближение к настоящему решению. Это значит, что корректирующий член имеет минимальную евклидову норму. Следующий член даёт решение однородной системы $A x = 0$ , потому что $(1 - A^+ A)$ — оператор проектирования на ядро оператора A, тогда как $(A^+A) = A^* (A A^*)^{-1} A$ — оператор проектирования на образ оператора A.