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

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

(Различия между версиями)
Перейти к: навигация, поиск
м (Метод наименьших квадратов и число обусловленности)
 
(15 промежуточных версий не показаны.)
Строка 1: Строка 1:
-
<p>'''Сингулярное разложение''' (Singular Value Decomposition, SVD)&nbsp;&#151; декомпозиция вещественной матрицы с целью ее приведения к следующему каноническому виду.</p>
+
{{TOCright}}
-
<p><b>Теорема</b>. Для любой вещественной <tex>(m\times m)</tex>-матрицы&nbsp;<tex>A</tex> существуют две вещественные ортогональные <tex>(m\times m)</tex>-матрицы&nbsp;<tex>U</tex> и&nbsp;<tex>V</tex> такие, что <tex>U^T A V</tex>&nbsp;&#151; диагональная матрица&nbsp;<tex>\Lambda</tex>, </p>
+
'''Сингулярное разложение''' (Singular Value Decomposition, SVD)&nbsp;&#151;
-
<p><center><tex>U^TAV=\Lambda.</tex></center></p>
+
декомпозиция [[вещественное число|вещественной]] [[матрица|матрицы]] с целью ее приведения к [[канонический вид|каноническому виду]].
-
<p>Матрицы&nbsp;<tex>U</tex> и&nbsp;<tex>V</tex> выбираются так, чтобы диагональные элементы матрицы&nbsp;<tex>\Lambda</tex> имели вид </p>
+
Сингулярное разложение является удобным методом при работе с&nbsp;матрицами.
-
<p><center><tex>\lambda_1 \geq \lambda_2 \geq \ldots \geq \lambda_r > \lambda_{r+1}=\ldots=\lambda_m=0,</tex></center></p>
+
Оно показывает геометрическую структуру матрицы и позволяет наглядно представить имеющиеся данные.
-
<p>где&nbsp;<tex>r</tex>&nbsp;&#151; ранг матрицы&nbsp;<tex>A</tex>. В частности, если&nbsp;<tex>A</tex> невырождена, то </p>
+
Сингулярное разложение используется при решении самых разных задач&nbsp;&#151;
-
<p><center><tex>\lambda_1 \geq \lambda_2 \geq \ldots \geq \lambda_m > 0.</tex></center></p>
+
от&nbsp;приближения [[метод наименьших квадратов|методом наименьших квадратов]] и решения систем уравнений
-
<p>Индекс&nbsp;<tex>r</tex> элемента&nbsp;<tex>\lambda_r</tex> есть фактическая размерность собственного пространства матрицы&nbsp;<tex>A</tex>. Столбцы матриц&nbsp;<tex>U</tex> и&nbsp;<tex>V</tex> называются соответственно левыми и правыми сингулярными векторами, а значения диагонали матрицы&nbsp;<tex>\Lambda</tex> называются сингулярными числами.
+
до&nbsp;[[сжатие изображений|сжатия изображений]].
-
</p>
+
При этом используются разные свойства сингулярного разложения, например,
 +
способность показывать [[ранг матрицы]], приближать матрицы данного ранга.
 +
SVD позволяет вычислять обратные и [[псевдообратная матрица|псевдообратные матрицы]] большого размера,
 +
что делает его полезным инструментом при решении задач [[регрессионный анализ|регрессионного анализа]].
 +
 
 +
Для любой вещественной <tex>(n\times n)</tex>-матрицы&nbsp;<tex>A</tex> существуют две вещественные
 +
[[ортогональная матрица|ортогональные]] <tex>(n\times n)</tex>-матрицы&nbsp;<tex>U</tex> и&nbsp;<tex>V</tex> такие,
 +
что <tex>U^T A V</tex>&nbsp;&#151; диагональная матрица&nbsp;<tex>\Lambda</tex>,
 +
<center><tex>U^TAV=\Lambda.</tex></center>
 +
Матрицы&nbsp;<tex>U</tex> и&nbsp;<tex>V</tex> выбираются так, чтобы диагональные элементы матрицы&nbsp;<tex>\Lambda</tex> имели вид
 +
<center><tex>\lambda_1 \geq \lambda_2 \geq ... \geq \lambda_r > \lambda_{r+1}=...=\lambda_n=0,</tex></center>
 +
где&nbsp;<tex>r</tex>&nbsp;&#151; ранг матрицы&nbsp;<tex>A</tex>. В частности, если&nbsp;<tex>A</tex> [[вырожденная матрица|невырождена]],
 +
то <center><tex>\lambda_1 \geq \lambda_2 \geq ... \geq \lambda_n > 0.</tex></center>
 +
 
 +
Индекс&nbsp;<tex>r</tex> элемента&nbsp;<tex>\lambda_r</tex> есть фактическая размерность [[собственное пространство матрицы|собственного пространства матрицы]] &nbsp;<tex>A</tex>.
 +
 
 +
Столбцы матриц&nbsp;<tex>U</tex> и&nbsp;<tex>V</tex> называются соответственно левыми и правыми сингулярными векторами, а значения диагонали матрицы&nbsp;<tex>\Lambda</tex> называются сингулярными числами.
 +
 
 +
Эквивалентная запись сингулярного разложения&nbsp;&#151; <tex>A=U\Lambda V^T</tex>.
 +
 
 +
Например, матрица
 +
<center><tex>A = \left(\begin{matrix}0.96 & 1.72\\2.28 & 0.96\\ \end{matrix}\right)</tex></center>
 +
имеет сингулярное разложение
 +
<center><tex>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</tex></center>
 +
Легко увидеть, что матрицы&nbsp;<tex>U</tex> и&nbsp;<tex>V</tex> ортогональны,
 +
<center><tex>U^TU=UU^T=I,</tex> также <tex>V^TV=VV^T = I,</tex></center>и сумма квадратов значений их столбцов равна единице.
 +
 
 +
== Геометрический смысл SVD ==
 +
 
 +
Пусть матрице&nbsp;<tex>A</tex> поставлен в&nbsp;соответствие [[линейный оператор]].
 +
Cингулярное разложение можно переформулировать в геометрических терминах.
 +
Линейный оператор, отображающий элементы пространства&nbsp;<tex>\R^n</tex> в себя представим в виде последовательно выполняемых
 +
линейных операторов вращения, растяжения и вращения.
 +
Поэтому компоненты сингулярного разложения наглядно показывают
 +
геометрические изменения при отображении линейным оператором <tex>A</tex>
 +
множества векторов из [[векторное пространство|векторного пространства]] в себя или в векторное пространство другой размерности.
 +
 
 +
== Пространства матрицы и SVD ==
 +
 
 +
Сингулярное разложение позволяет найти [[ортогональный базис|ортогональные базисы]]
 +
различных векторных пространств разлагаемой матрицы
 +
<center><tex>A_{(n\times n)} = U_{(n\times n)} \Lambda_{(n\times n)} V_{(n\times n)}^T.</tex></center>
 +
Для прямоугольных матриц существует так называемое экономное представление сингулярного
 +
разложения матрицы.
 +
<center><tex>A_{(m\times n)} = U_{(m\times m)} \Lambda_{(m\times n)} V_{(n\times n)}^T</tex></center>
 +
Согласно этому представлению при&nbsp;<tex>m>n</tex>, диагональная
 +
матрица&nbsp;<tex>\Lambda</tex> имеет пустые строки (их элементы равны нулю), а при&nbsp;<tex>m<n</tex>&nbsp;&#151; пустые
 +
столбцы. Поэтому существует еще одно экономное представление
 +
<center><tex>A_{(m\times n)} = U_{(m\times r)} \Lambda_{(r\times r)} V_{(r\times n)}^T,</tex></center>
 +
в котором&nbsp;<tex>r=\min(m,n)</tex>.
 +
 
 +
Нуль-пространство матрицы&nbsp;<tex>A</tex>&nbsp;&#151; набор векторов&nbsp;<tex>\mathbf{x}</tex>, для
 +
которого справедливо высказывание&nbsp;<tex>A\mathbf{x}=\mathbf{0}</tex>. Собственное
 +
пространство матрицы&nbsp;<tex>A</tex>&nbsp;&#151; набор векторов&nbsp;<tex>\mathbf b</tex>, при
 +
котором уравнение&nbsp;<tex>A\mathbf{x}=\mathbf b</tex> имеет ненулевое решение
 +
для&nbsp;<tex>\mathbf{x}</tex>. Обозначим&nbsp;<tex>\mathbf{u}k</tex> и&nbsp;<tex>\mathbf{v}k</tex>&nbsp;&#151; столбцы матриц&nbsp;<tex>U</tex> и&nbsp;<tex>V</tex>.
 +
Тогда разложение&nbsp;<tex>A=U\Lambda V^T</tex> может быть записано в виде:
 +
<tex>A=\sum_{k=1}^rA_k</tex>, где&nbsp;<tex>A_k=\mathbf{u}_k\lambda_k{\mathbf{v}}_k^T</tex>. Если
 +
сингулярное число&nbsp;<tex>\lambda_k=0</tex>, то <tex>A{\mathbf{v}}_k=\mathbf{0}</tex> и
 +
<tex>\mathbf{v}_k</tex> находится в нуль-пространстве матрицы&nbsp;<tex>A</tex>, а если
 +
сингулярное число&nbsp;<tex>\lambda_k\neq0</tex>, то вектор&nbsp;<tex>\mathbf{u}_k</tex> находятся в
 +
собственном пространстве матрицы&nbsp;<tex>A</tex>. Следовательно, можно
 +
сконструировать базисы для различных векторных подпространств,
 +
определенных матрицей&nbsp;<tex>A</tex>. Hабор
 +
векторов&nbsp;<tex>\mathbf{v}_1,\ldots,\mathbf{v}_k</tex> в векторном
 +
пространстве&nbsp;<tex>V</tex> формирует [[базис линейного пространства|базис]] для&nbsp;<tex>V</tex>, если любой
 +
вектор&nbsp;<tex>\mathbf{x}</tex> из&nbsp;<tex>V</tex> можно представить в виде [[линейная комбинация|линейной комбинации]]
 +
векторов&nbsp;<tex>\mathbf{v}_1,\ldots,\mathbf{v}_k</tex> единственным способом.
 +
Пусть&nbsp;<tex>V_0</tex> будет набором тех столбцов&nbsp;<tex>\mathbf{v}k</tex>, для
 +
которых&nbsp;<tex>\lambda_k\neq 0</tex>, а&nbsp;<tex>V_1</tex>&nbsp;&#151; все остальные
 +
столбцы&nbsp;<tex>\mathbf{v}k</tex>. Также, пусть&nbsp;<tex>U_0</tex> будет набором столбцов&nbsp;<tex>\mathbf{u}k</tex>,
 +
для которых&nbsp;<tex>\lambda_k\neq 0</tex>, а&nbsp;<tex>U_1</tex>&nbsp;&#151; все остальные
 +
столбцы&nbsp;<tex>\mathbf{u}k</tex>, включая и те, для которых&nbsp;<tex>k>n</tex>. Тогда,
 +
если&nbsp;<tex>r</tex>&nbsp;&#151; количество ненулевых сингулярных чисел, то
 +
имеется&nbsp;<tex>r</tex> столбцов в наборе&nbsp;<tex>V_0</tex> и&nbsp;<tex>n-r</tex> столбцов в
 +
наборе&nbsp;<tex>V_1</tex> и&nbsp;<tex>U_1</tex>, а также&nbsp;<tex>m-n+r</tex> столбцов в наборе&nbsp;<tex>U_0</tex>.
 +
Каждый из этих наборов формирует базис векторного пространства матрицы&nbsp;<tex>A</tex>:
 +
 
 +
* <tex>V_0</tex>&nbsp;&#151; ортонормальный базис для ортогонального комплементарного нуль-пространства&nbsp;<tex>A</tex>,
 +
* <tex>V_1</tex>&nbsp;&#151; ортонормальный базис для нуль-пространства&nbsp;<tex>A</tex>,
 +
* <tex>U_0</tex>&nbsp;&#151; ортонормальный базис для собственного пространства&nbsp;<tex>A</tex>,
 +
* <tex>U_1</tex>&nbsp;&#151; ортонормальный базис для ортогонального комплементарного нуль-пространства&nbsp;<tex>A</tex>.
 +
 
 +
== SVD и собственные числа матрицы ==
 +
 
 +
Сингулярное разложение обладает свойством, которое связывает
 +
задачу отыскания сингулярного разложения и задачу отыскания
 +
собственных векторов. Собственный вектор&nbsp;<tex>\mathbf{x}</tex> матрицы&nbsp;<tex>A</tex>&nbsp;&#151;
 +
такой вектор, при котором выполняется условие&nbsp;<tex>A\mathbf{x}=\lambda\mathbf{x}</tex>,
 +
число&nbsp;<tex>\lambda</tex> называется собственным числом. Так как матрицы&nbsp;<tex>U</tex>
 +
и&nbsp;<tex>V</tex> ортогональные, то
 +
<center><tex>\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}</tex></center>
 +
Умножая оба выражения справа соответственно на&nbsp;<tex>U</tex> и&nbsp;<tex>V</tex> получаем
 +
<center><tex>\begin{array}{c}AA^TU=U\Lambda^2,\\A^TAV=V\Lambda^2.\\\end{array}</tex></center>
 +
Из этого следует, что столбцы матрицы&nbsp;<tex>U</tex> являются собственными
 +
векторами матрицы <tex>AA^T</tex>, а&nbsp;квадраты сингулярных чисел
 +
<tex>\Lambda=\mbox{diag}(\lambda_1,...,\lambda_r)</tex>&nbsp;&#151; ее собственными
 +
числами.
 +
Также столбцы матрицы <tex>V</tex> являются собственными векторами матрицы <tex>A^TA</tex>, а
 +
квадраты сингулярных чисел являются ее собственными числами.
 +
 
 +
== SVD и норма матриц ==
 +
 
 +
Рассмотрим изменение длины вектора&nbsp;<tex>\mathbf{x}</tex> до и после его умножения
 +
слева на матрицу&nbsp;<tex>A</tex>. Евклидова норма вектора определена как
 +
<center><tex>\|\mathbf{x}\|_E^2=\mathbf{x}^T\mathbf{x}.</tex></center>
 +
Если матрица&nbsp;<tex>A</tex> ортогональна, длина вектора&nbsp;<tex>A\mathbf{x}</tex> остается неизменной. В противном
 +
случае можно вычислить, насколько матрица&nbsp;<tex>A</tex> растянула
 +
вектор&nbsp;<tex>\mathbf{x}</tex>.
 +
 
 +
Евклидова норма матрицы есть максимальный коэффициент растяжения произвольного вектора&nbsp;<tex>\mathbf{x}</tex> заданной матрицей&nbsp;<tex>A</tex>
 +
<center><tex>\|A\|_E=\max\limits_{\|\mathbf{x}\|=1}\left(\frac{\|A\mathbf{x}\|}{\|\mathbf{x}\|}\right).</tex></center>
 +
Альтернативой Евклидовой норме является норма Фробениуса:
 +
<center><tex>\|A\|_F=\sqrt{\sum_{i=1}^m\sum_{j=1}^na_{ij}^2}.</tex></center>
 +
Если известно сингулярное разложение, то обе эти нормы легко
 +
вычислить. Пусть&nbsp;<tex>\lambda_1,\ldots,\lambda_r</tex>&nbsp;&#151; сингулярные числа матрицы&nbsp;<tex>A</tex>, отличные от нуля.
 +
Тогда
 +
<center><tex>\|A\|_E=\lambda_1,</tex></center>
 +
и
 +
<center><tex>\|A\|_F=\sqrt{\sum_{k=1}^r\lambda_k^2}.</tex></center>
 +
 
 +
Сингулярные числа матрицы&nbsp;<tex>A</tex>&nbsp;&#151; это длины осей эллипсоида,
 +
заданного множеством
 +
<center><tex>\left. \{A\mathbf{x}\right|\|\mathbf{x}\|{_E}=1\}.</tex></center>
 +
 
 +
== Нахождение псевдообратной матрицы с помощью SVD ==
 +
 
 +
Если&nbsp;<tex>(m\times n)</tex>-матрица&nbsp;<tex>A</tex> является вырожденной или
 +
прямоугольной, то обратной матрицы&nbsp;<tex>A^{-1}</tex> для нее не&nbsp;существует.
 +
Однако для&nbsp;<tex>A</tex> может быть найдена псевдообратная
 +
 
 +
матрица&nbsp;<tex>A^+</tex>&nbsp;&#151; такая матрица, для которой выполняются условия
 +
<center><tex>\begin{array}{l} A^+A=I_n,\\ AA^+=I_m,\\ A^+AA^+=A^+,\\ AA^+A=A.\\ \end{array}</tex></center>
 +
Пусть найдено разложение матрицы&nbsp;<tex>A</tex> вида
 +
<center><tex>A=U\Lambda{V}^T,</tex></center> где
 +
<tex>\Lambda=\mbox{diag}(\lambda_1,...,\lambda_r)</tex>, <tex>r=\min(m,n)</tex> и
 +
<tex>U^TU=I_m, VV^T=I_n</tex>.
 +
Тогда матрица&nbsp;<tex>A^+=V^T\Lambda^{-1}U</tex> является для матрицы&nbsp;<tex>A</tex>
 +
псевдообратной.
 +
Действительно, <tex>A^+A=V\Lambda^{-1}U^TU\Lambda{V}^T=I_n</tex>, <tex>AA^+=U\Lambda{V}^TV\Lambda^{-1}U^T=I_m</tex>.
 +
 
 +
== Метод наименьших квадратов и число обусловленности ==
 +
 
 +
Задача наименьших квадратов ставится следующим образом. Даны
 +
действительная <tex>(m{\times}n)</tex>-матрица&nbsp;<tex>A</tex> и
 +
действительный&nbsp;<tex>(m)</tex>-вектор&nbsp;<tex>Y</tex>. Требуется найти
 +
действительный&nbsp;<tex>(n)</tex>-вектор&nbsp;<tex>\mathbf{w}</tex>, минимизирующий Евклидову длину
 +
вектора невязки, <center><tex>\|Y-A\mathbf{w}\|_E\longrightarrow\min.</tex></center> Решение
 +
задачи наименьших квадратов&nbsp;&#151;
 +
<center><tex>\mathbf{w}=(A^TA)^{-1}(A^TY).</tex></center>
 +
 
 +
Для отыскания решения&nbsp;<tex>\mathbf{w}</tex> требуется обратить матрицу&nbsp;<tex>A^TA</tex>.
 +
Для квадратных матриц&nbsp;<tex>A</tex> число обусловленности&nbsp;<tex>\ae(A)</tex> определено отношением
 +
<center><tex>\ae(A)=\|A\|_E\|A^{-1}\|_E.</tex></center>
 +
Из формулы Евклидовой нормы матрицы и предыдущей формулы следует, что число обусловленности матрицы есть отношение ее первого сингулярного числа к последнему.
 +
<center><tex>\ae(A)=\frac{\lambda_1}{\lambda_n}.</tex></center>
 +
 
 +
Следовательно, число обусловленности матрицы&nbsp;<tex>A^TA</tex> есть квадрат числа обусловленности матрицы&nbsp;<tex>A</tex>.
 +
Это высказывание справедливо и для [[вырожденная матрица|вырожденных матриц]], если полагать число обусловленности как отношение
 +
<tex>\lambda_1/\lambda_r</tex>, <tex>r</tex>&nbsp;&#151; ранг матрицы&nbsp;<tex>A</tex>.
 +
Поэтому для получения обращения, [[устойчивоcть|устойчивого]] к малым изменениям значений матрицы&nbsp;<tex>A</tex>, используется усеченное SVD.
 +
 
 +
== Усеченное SVD при обращении матриц ==
 +
 
 +
Пусть матрица&nbsp;<tex>A</tex> представлена в&nbsp;виде <tex>A=U\Lambda{}V^T</tex>.
 +
Тогда при нахождении обратной матрицы
 +
<tex>A^+=V\Lambda^{-1}U^T</tex> в силу ортогональности матриц&nbsp;<tex>U</tex> и&nbsp;<tex>V</tex> и в силу условия убывания диагональных элементов
 +
матрицы <tex>\Lambda=\mbox{diag}(\lambda_1,...,\lambda_n)</tex>,
 +
псевдообратная матрица&nbsp;<tex>A^+</tex> будет более зависеть от тех элементов
 +
матрицы&nbsp;<tex>\Lambda</tex>, которые имеют меньшие значения, чем от первых
 +
сингулярных чисел. Действительно, если матрица&nbsp;<tex>A</tex> имеет сингулярные числа
 +
<tex>\lambda_1\geq\lambda_2\geq...\geq\lambda_n</tex>, то
 +
сингулярные числа матрицы&nbsp;<tex>A^+</tex> равны
 +
<center><tex>\Lambda^{-1}=\mbox{diag}(\frac{1}{\lambda_1},...,\frac{1}{\lambda_n})</tex>
 +
и
 +
<tex>\frac{1}{\lambda_1}\leq\frac{1}{\lambda_2}...\leq\frac{1}{\lambda_n}.</tex></center>
 +
Считая первые&nbsp;<tex>s</tex> сингулярных чисел определяющими собственное
 +
пространство матрицы&nbsp;<tex>A</tex>, используем при обращении матрицы&nbsp;<tex>A</tex>
 +
первые&nbsp;<tex>s</tex> сингулярных чисел, <tex>s\leq\mbox{rank}A</tex>. Тогда обратная матрица&nbsp;<tex>A^+</tex> будет
 +
найдена как <tex>A^+=V\Lambda^{-1}_sU^T</tex>.
 +
 
 +
Определим усеченную псевдообратную матрицу&nbsp;<tex>A_s^+</tex> как
 +
<center><tex> A_s^+=V\Lambda^{-1}_sU^T,</tex></center>
 +
где&nbsp;<tex>\Lambda^{-1}_s=\mbox{diag}(\lambda_1^{-1},...,\lambda_s^{-1},0,...,0)</tex>&nbsp;&#151;
 +
<tex>(n\times{n})</tex>-диагональная матрица.
 +
 
 +
== Смотри также ==
 +
* [[Метод главных компонент]]
 +
* [[Простой итерационный алгоритм сингулярного разложения]]
 +
* [[Регрессионный анализ]]
 +
* [[Интегральный индикатор]]
 +
* [[Согласование экспертных оценок]]
 +
 
 +
== Литература ==
 +
* Голуб Дж., Ван-Лоун Ч. Матричные вычисления. М.: Мир. 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.
 +
* [http://www.prip.tuwien.ac.at/teaching/ws/statistische-mustererkennung/apponly.pdf Meltzer T. SVD and its Application to Generalized Eigenvalue Problems. 2004. 16 pages.]
 +
[[Категория:Регрессионный анализ]]
 +
[[Категория:Популярные и обзорные статьи]]

Текущая версия

Содержание

Сингулярное разложение (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,
и сумма квадратов значений их столбцов равна единице.

Геометрический смысл 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^2=\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. 2004. 16 pages.
Личные инструменты