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

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

Перейти к: навигация, поиск

Содержание

Сингулярное разложение (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=\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.