Сингулярное разложение

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

(Различия между версиями)

Версия 14:52, 14 октября 2008

Сингулярное разложение (Singular Value Decomposition, SVD) — декомпозиция вещественной матрицы с целью ее приведения к каноническому виду. Сингулярное разложение является удобным методом при работе с матрицами. Оно показывает геометрическую структуру матрицы и позволяет наглядно представить имеющиеся данные. Сингулярное разложение используется при решении самых разных задач — от приближения методом наименьших квадратов и решения систем уравнений до сжатия изображений. При этом используются разные свойства сингулярного разложения, например, способность показывать ранг матрицы, приближать матрицы данного ранга. SVD позволяет вычислять обратные и псевдообратные матрицы большого размера, что делает его полезным инструментом при решении задач регрессионного анализа.

Для любой вещественной $(n\times n)$ -матрицы $A$ существуют две вещественные ортогональные $(n\times n)$ -матрицы $U$ и $V$ такие, что $U^T A V$ — диагональная матрица $\Lambda$ ,

$U^TAV=\Lambda.$

Матрицы $U$ и $V$ выбираются так, чтобы диагональные элементы матрицы $\Lambda$ имели вид

$\lambda_1 \geq \lambda_2 \geq ... \geq \lambda_r > \lambda_{r+1}=...=\lambda_n=0,$

где $r$ — ранг матрицы $A$ . В частности, если $A$ невырождена,

то $\lambda_1 \geq \lambda_2 \geq ... \geq \lambda_n > 0.$

Индекс $r$ элемента $\lambda_r$ есть фактическая размерность собственного пространства матрицы $A$ .

Столбцы матриц $U$ и $V$ называются соответственно левыми и правыми сингулярными векторами, а значения диагонали матрицы $\Lambda$ называются сингулярными числами.

Эквивалентная запись сингулярного разложения — $A=U\Lambda V^T$ .

Например, матрица

$A = \left(\begin{matrix}0.96 & 1.72\\2.28 & 0.96\\ \end{matrix}\right)$

имеет сингулярное разложение

$A = U\Lambda V^T=\left(\begin{matrix}0.6 & 0.8\\0.8 & -0.6\\\end{matrix}\right)\left(\begin{matrix}3 & 0\\0 & 1\\\end{matrix}\right)\left(\begin{matrix}0.8 & -0.6\\0.6 & 0.8\\\end{matrix}\right)^T$

Легко увидеть, что матрицы $U$ и $V$ ортогональны,

$U^TU=UU^T=I,$ также $V^TV=VV^T = I,$ и сумма квадратов значений их столбцов равна единице.

Содержание

1 Геометрический смысл SVD
2 Пространства матрицы и SVD
3 SVD и собственные числа матрицы
4 SVD и норма матриц
5 Нахождение псевдообратной матрицы с помощью SVD
6 Метод наименьших квадратов и число обусловленности
7 Усеченное SVD при обращении матриц
8 Смотри также
9 Литература

Геометрический смысл SVD

Пусть матрице $A$ поставлен в соответствие линейный оператор. Cингулярное разложение можно переформулировать в геометрических терминах. Линейный оператор, отображающий элементы пространства $\R^n$ в себя представим в виде последовательно выполняемых линейных операторов вращения, растяжения и вращения. Поэтому компоненты сингулярного разложения наглядно показывают геометрические изменения при отображении линейным оператором $A$ множества векторов из векторного пространства в себя или в векторное пространство другой размерности.

Пространства матрицы и SVD

Сингулярное разложение позволяет найти ортогональные базисы различных векторных пространств разлагаемой матрицы

$A_{(n\times n)} = U_{(n\times n)} \Lambda_{(n\times n)} V_{(n\times n)}^T.$

Для прямоугольных матриц существует так называемое экономное представление сингулярного разложения матрицы.

$A_{(m\times n)} = U_{(m\times m)} \Lambda_{(m\times n)} V_{(n\times n)}^T$

Согласно этому представлению при $m>n$ , диагональная матрица $\Lambda$ имеет пустые строки (их элементы равны нулю), а при $m<n$ — пустые столбцы. Поэтому существует еще одно экономное представление

$A_{(m\times n)} = U_{(m\times r)} \Lambda_{(r\times r)} V_{(r\times n)}^T,$

в котором $r=\min(m,n)$ .

Нуль-пространство матрицы $A$ — набор векторов $\mathbf{x}$ , для которого справедливо высказывание $A\mathbf{x}=\mathbf{0}$ . Собственное пространство матрицы $A$ — набор векторов $\mathbf b$ , при котором уравнение $A\mathbf{x}=\mathbf b$ имеет ненулевое решение для $\mathbf{x}$ . Обозначим $\mathbf{u}k$ и $\mathbf{v}k$ — столбцы матриц $U$ и $V$ . Тогда разложение $A=U\Lambda V^T$ может быть записано в виде: $A=\sum_{k=1}^rA_k$ , где $A_k=\mathbf{u}_k\lambda_k{\mathbf{v}}_k^T$ . Если сингулярное число $\lambda_k=0$ , то $A{\mathbf{v}}_k=\mathbf{0}$ и $\mathbf{v}_k$ находится в нуль-пространстве матрицы $A$ , а если сингулярное число $\lambda_k\neq0$ , то вектор $\mathbf{u}_k$ находятся в собственном пространстве матрицы $A$ . Следовательно, можно сконструировать базисы для различных векторных подпространств, определенных матрицей $A$ . Hабор векторов $\mathbf{v}_1,\ldots,\mathbf{v}_k$ в векторном пространстве $V$ формирует базис для $V$ , если любой вектор $\mathbf{x}$ из $V$ можно представить в виде линейной комбинации векторов $\mathbf{v}_1,\ldots,\mathbf{v}_k$ единственным способом. Пусть $V_0$ будет набором тех столбцов $\mathbf{v}k$ , для которых $\lambda_k\neq 0$ , а $V_1$ — все остальные столбцы $\mathbf{v}k$ . Также, пусть $U_0$ будет набором столбцов $\mathbf{u}k$ , для которых $\lambda_k\neq 0$ , а $U_1$ — все остальные столбцы $\mathbf{u}k$ , включая и те, для которых $k>n$ . Тогда, если $r$ — количество ненулевых сингулярных чисел, то имеется $r$ столбцов в наборе $V_0$ и $n-r$ столбцов в наборе $V_1$ и $U_1$ , а также $m-n+r$ столбцов в наборе $U_0$ . Каждый из этих наборов формирует базис векторного пространства матрицы $A$ :

$V_0$ — ортонормальный базис для ортогонального комплементарного нуль-пространства $A$ ,
$V_1$ — ортонормальный базис для нуль-пространства $A$ ,
$U_0$ — ортонормальный базис для собственного пространства $A$ ,
$U_1$ — ортонормальный базис для ортогонального комплементарного нуль-пространства $A$ .

SVD и собственные числа матрицы

Сингулярное разложение обладает свойством, которое связывает задачу отыскания сингулярного разложения и задачу отыскания собственных векторов. Собственный вектор $\mathbf{x}$ матрицы $A$ — такой вектор, при котором выполняется условие $A\mathbf{x}=\lambda\mathbf{x}$ , число $\lambda$ называется собственным числом. Так как матрицы $U$ и $V$ ортогональные, то

$\begin{array}{c}AA^T=U\Lambda V^TV\Lambda U^T=U\Lambda^2 U^T,\\A^TA=V\Lambda U^TU\Lambda V^T=V\Lambda^2 V^T.\\ \end{array}$

Умножая оба выражения справа соответственно на $U$ и $V$ получаем

$\begin{array}{c}AA^TU=U\Lambda^2,\\A^TAV=V\Lambda^2.\\\end{array}$

Из этого следует, что столбцы матрицы $U$ являются собственными векторами матрицы $AA^T$ , а квадраты сингулярных чисел $\Lambda=\mbox{diag}(\lambda_1,...,\lambda_r)$ — ее собственными числами. Также столбцы матрицы $V$ являются собственными векторами матрицы $A^TA$ , а квадраты сингулярных чисел являются ее собственными числами.

SVD и норма матриц

Рассмотрим изменение длины вектора $\mathbf{x}$ до и после его умножения слева на матрицу $A$ . Евклидова норма вектора определена как

$\|\mathbf{x}\|_E=\mathbf{x}^T\mathbf{x}.$

Если матрица $A$ ортогональна, длина вектора $A\mathbf{x}$ остается неизменной. В противном случае можно вычислить, насколько матрица $A$ растянула вектор $\mathbf{x}$ .

Евклидова норма матрицы есть максимальный коэффициент растяжения произвольного вектора $\mathbf{x}$ заданной матрицей $A$

$\|A\|_E=\max\limits_{\|\mathbf{x}\|=1}\left(\frac{\|A\mathbf{x}\|}{\|\mathbf{x}\|}\right).$

Альтернативой Евклидовой норме является норма Фробениуса:

$\|A\|_F=\sqrt{\sum_{i=1}^m\sum_{j=1}^na_{ij}^2}.$

Если известно сингулярное разложение, то обе эти нормы легко вычислить. Пусть $\lambda_1,\ldots,\lambda_r$ — сингулярные числа матрицы $A$ , отличные от нуля. Тогда

$\|A\|_E=\lambda_1,$

$\|A\|_F=\sqrt{\sum_{k=1}^r\lambda_k^2}.$

Сингулярные числа матрицы $A$ — это длины осей эллипсоида, заданного множеством

$\left. \{A\mathbf{x}\right|\|\mathbf{x}\|{_E}=1\}.$

Нахождение псевдообратной матрицы с помощью SVD

Если $(m\times n)$ -матрица $A$ является вырожденной или прямоугольной, то обратной матрицы $A^{-1}$ для нее не существует. Однако для $A$ может быть найдена псевдообратная

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

$\begin{array}{l} A^+A=I_n,\\ AA^+=I_m,\\ A^+AA^+=A^+,\\ AA^+A=A.\\ \end{array}$

Пусть найдено разложение матрицы $A$ вида

$A=U\Lambda{V}^T,$ где

$\Lambda=\mbox{diag}(\lambda_1,...,\lambda_r)$ , $r=\min(m,n)$ и $U^TU=I_m, VV^T=I_n$ . Тогда матрица $A^+=V^T\Lambda^{-1}U$ является для матрицы $A$ псевдообратной. Действительно, $A^+A=V\Lambda^{-1}U^TU\Lambda{V}^T=I_n$ , $AA^+=U\Lambda{V}^TV\Lambda^{-1}U^T=I_m$ .

Метод наименьших квадратов и число обусловленности

Задача наименьших квадратов ставиться следующим образом. Даны действительная $(m{\times}n)$ -матрица $A$ и действительный $(m)$ -вектор $Y$ . Требуется найти действительный $(n)$ -вектор $\mathbf{w}$ , минимизирующий Евклидову длину

вектора невязки, $\|Y-A\mathbf{w}\|_E\longrightarrow\min.$ Решение

задачи наименьших квадратов —

$\mathbf{w}=(A^TA)^{-1}(A^TY).$

Для отыскания решения $\mathbf{w}$ требуется обратить матрицу $A^TA$ . Для квадратных матриц $A$ число обусловленности $\ae(A)$ определено отношением

$\ae(A)=\|A\|_E\|A^{-1}\|_E.$

Из формулы Евклидовой нормы матрицы и предыдущей формулы следует, что число обусловленности матрицы есть отношение ее первого сингулярного числа к последнему.

$\ae(A)=\frac{\lambda_1}{\lambda_n}.$

Следовательно, число обусловленности матрицы $A^TA$ есть квадрат числа обусловленности матрицы $A$ . Это высказывание справедливо и для вырожденных матриц, если полагать число обусловленности как отношение $\lambda_1/\lambda_r$ , $r$ — ранг матрицы $A$ . Поэтому для получения обращения, устойчивого к малым изменениям значений матрицы $A$ , используется усеченное SVD.

Усеченное SVD при обращении матриц

Пусть матрица $A$ представлена в виде $A=U\Lambda{}V^T$ . Тогда при нахождении обратной матрицы $A^+=V\Lambda^{-1}U^T$ в силу ортогональности матриц $U$ и $V$ и в силу условия убывания диагональных элементов матрицы $\Lambda=\mbox{diag}(\lambda_1,...,\lambda_n)$ , псевдообратная матрица $A^+$ будет более зависеть от тех элементов матрицы $\Lambda$ , которые имеют меньшие значения, чем от первых сингулярных чисел. Действительно, если матрица $A$ имеет сингулярные числа $\lambda_1\geq\lambda_2\geq...\geq\lambda_n$ , то сингулярные числа матрицы $A^+$ равны

$\Lambda^{-1}=\mbox{diag}(\frac{1}{\lambda_1},...,\frac{1}{\lambda_n})$

$\frac{1}{\lambda_1}\leq\frac{1}{\lambda_2}...\leq\frac{1}{\lambda_n}.$

Считая первые $s$ сингулярных чисел определяющими собственное пространство матрицы $A$ , используем при обращении матрицы $A$ первые $s$ сингулярных чисел, $s\leq\mbox{rank}A$ . Тогда обратная матрица $A^+$ будет найдена как $A^+=V\Lambda^{-1}_sU^T$ .

Определим усеченную псевдообратную матрицу $A_s^+$ как

$A_s^+=V\Lambda^{-1}_sU^T,$

где $\Lambda^{-1}_s=\mbox{diag}(\lambda_1^{-1},...,\lambda_s^{-1},0,...,0)$ — $(n\times{n})$ -диагональная матрица.

Смотри также

Литература

Голуб Дж., Ван-Лоун Ч. Матричные вычисления. М.: Мир. 1999.
Деммель Дж. Вычислительная линейная алгебра. URSS. 2001.
Логинов Н.В. Сингулярное разложение матриц. М.: МГАПИ. 1996.
Стренг Г. Линейная алгебра и ее применения. М.: Мир. 1980.
Форсайт Дж., Молер К. Численное решение систем линейных алгебраических уравнений. М.: Мир. 1969.
Хорн Р., Джонсон Ч. Матричный анализ. М.: Мир. 1989.
Vetterling W. T. Flannery B. P. Numerical Recipies in C: The Art of Scientific Computing. NY: Cambridge University Press. 1999.
Meltzer T. SVD and its Application to Generalized Eigenvalue Problems

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%A1%D0%B8%D0%BD%D0%B3%D1%83%D0%BB%D1%8F%D1%80%D0%BD%D0%BE%D0%B5_%D1%80%D0%B0%D0%B7%D0%BB%D0%BE%D0%B6%D0%B5%D0%BD%D0%B8%D0%B5»

Категория: Регрессионный анализ

@@ Строка 207: / Строка 207: @@
 * Хорн Р., Джонсон Ч. Матричный анализ. М.: Мир. 1989.
 * Vetterling W. T. Flannery B. P. Numerical Recipies in C: The Art of Scientific Computing. NY: Cambridge University Press. 1999.
+* [http://www.prip.tuwien.ac.at/teaching/ws/statistische-mustererkennung/apponly.pdf Meltzer T. SVD and its Application to Generalized Eigenvalue Problems]
 [[Категория:Регрессионный анализ]]