Сингулярное разложение
Материал из MachineLearning.
м |
м (→Метод наименьших квадратов и число обусловленности) |
||
(10 промежуточных версий не показаны.) | |||
Строка 1: | Строка 1: | ||
+ | {{TOCright}} | ||
'''Сингулярное разложение''' (Singular Value Decomposition, SVD) — | '''Сингулярное разложение''' (Singular Value Decomposition, SVD) — | ||
декомпозиция [[вещественное число|вещественной]] [[матрица|матрицы]] с целью ее приведения к [[канонический вид|каноническому виду]]. | декомпозиция [[вещественное число|вещественной]] [[матрица|матрицы]] с целью ее приведения к [[канонический вид|каноническому виду]]. | ||
Строка 8: | Строка 9: | ||
При этом используются разные свойства сингулярного разложения, например, | При этом используются разные свойства сингулярного разложения, например, | ||
способность показывать [[ранг матрицы]], приближать матрицы данного ранга. | способность показывать [[ранг матрицы]], приближать матрицы данного ранга. | ||
- | SVD позволяет вычислять обратные и [[псевдообратные матрицы]] большого размера, | + | SVD позволяет вычислять обратные и [[псевдообратная матрица|псевдообратные матрицы]] большого размера, |
что делает его полезным инструментом при решении задач [[регрессионный анализ|регрессионного анализа]]. | что делает его полезным инструментом при решении задач [[регрессионный анализ|регрессионного анализа]]. | ||
Строка 41: | Строка 42: | ||
Поэтому компоненты сингулярного разложения наглядно показывают | Поэтому компоненты сингулярного разложения наглядно показывают | ||
геометрические изменения при отображении линейным оператором <tex>A</tex> | геометрические изменения при отображении линейным оператором <tex>A</tex> | ||
- | множества векторов из [[векторное пространство|векторного пространства]] в себя или в | + | множества векторов из [[векторное пространство|векторного пространства]] в себя или в векторное пространство другой размерности. |
== Пространства матрицы и SVD == | == Пространства матрицы и SVD == | ||
Строка 111: | Строка 112: | ||
Рассмотрим изменение длины вектора <tex>\mathbf{x}</tex> до и после его умножения | Рассмотрим изменение длины вектора <tex>\mathbf{x}</tex> до и после его умножения | ||
слева на матрицу <tex>A</tex>. Евклидова норма вектора определена как | слева на матрицу <tex>A</tex>. Евклидова норма вектора определена как | ||
- | <center><tex>\|\mathbf{x}\|_E=\mathbf{x}^T\mathbf{x}.</tex></center> | + | <center><tex>\|\mathbf{x}\|_E^2=\mathbf{x}^T\mathbf{x}.</tex></center> |
Если матрица <tex>A</tex> ортогональна, длина вектора <tex>A\mathbf{x}</tex> остается неизменной. В противном | Если матрица <tex>A</tex> ортогональна, длина вектора <tex>A\mathbf{x}</tex> остается неизменной. В противном | ||
случае можно вычислить, насколько матрица <tex>A</tex> растянула | случае можно вычислить, насколько матрица <tex>A</tex> растянула | ||
Строка 129: | Строка 130: | ||
Сингулярные числа матрицы <tex>A</tex> — это длины осей эллипсоида, | Сингулярные числа матрицы <tex>A</tex> — это длины осей эллипсоида, | ||
заданного множеством | заданного множеством | ||
- | <center><tex>\{A\mathbf{x}| | + | <center><tex>\left. \{A\mathbf{x}\right|\|\mathbf{x}\|{_E}=1\}.</tex></center> |
== Нахождение псевдообратной матрицы с помощью SVD == | == Нахождение псевдообратной матрицы с помощью SVD == | ||
Строка 149: | Строка 150: | ||
== Метод наименьших квадратов и число обусловленности == | == Метод наименьших квадратов и число обусловленности == | ||
- | Задача наименьших квадратов | + | Задача наименьших квадратов ставится следующим образом. Даны |
действительная <tex>(m{\times}n)</tex>-матрица <tex>A</tex> и | действительная <tex>(m{\times}n)</tex>-матрица <tex>A</tex> и | ||
действительный <tex>(m)</tex>-вектор <tex>Y</tex>. Требуется найти | действительный <tex>(m)</tex>-вектор <tex>Y</tex>. Требуется найти | ||
Строка 194: | Строка 195: | ||
== Смотри также == | == Смотри также == | ||
* [[Метод главных компонент]] | * [[Метод главных компонент]] | ||
+ | * [[Простой итерационный алгоритм сингулярного разложения]] | ||
* [[Регрессионный анализ]] | * [[Регрессионный анализ]] | ||
* [[Интегральный индикатор]] | * [[Интегральный индикатор]] | ||
Строка 206: | Строка 208: | ||
* Хорн Р., Джонсон Ч. Матричный анализ. М.: Мир. 1989. | * Хорн Р., Джонсон Ч. Матричный анализ. М.: Мир. 1989. | ||
* Vetterling W. T. Flannery B. P. Numerical Recipies in C: The Art of Scientific Computing. NY: Cambridge University Press. 1999. | * 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 позволяет вычислять обратные и псевдообратные матрицы большого размера, что делает его полезным инструментом при решении задач регрессионного анализа.
Для любой вещественной -матрицы существуют две вещественные ортогональные -матрицы и такие, что диагональная матрица ,
Матрицы и выбираются так, чтобы диагональные элементы матрицы имели вид
где ранг матрицы . В частности, если невырождена,
тоИндекс элемента есть фактическая размерность собственного пространства матрицы .
Столбцы матриц и называются соответственно левыми и правыми сингулярными векторами, а значения диагонали матрицы называются сингулярными числами.
Эквивалентная запись сингулярного разложения .
Например, матрица
имеет сингулярное разложение
Легко увидеть, что матрицы и ортогональны,
Геометрический смысл SVD
Пусть матрице поставлен в соответствие линейный оператор. Cингулярное разложение можно переформулировать в геометрических терминах. Линейный оператор, отображающий элементы пространства в себя представим в виде последовательно выполняемых линейных операторов вращения, растяжения и вращения. Поэтому компоненты сингулярного разложения наглядно показывают геометрические изменения при отображении линейным оператором множества векторов из векторного пространства в себя или в векторное пространство другой размерности.
Пространства матрицы и SVD
Сингулярное разложение позволяет найти ортогональные базисы различных векторных пространств разлагаемой матрицы
Для прямоугольных матриц существует так называемое экономное представление сингулярного разложения матрицы.
Согласно этому представлению при , диагональная матрица имеет пустые строки (их элементы равны нулю), а при пустые столбцы. Поэтому существует еще одно экономное представление
в котором .
Нуль-пространство матрицы набор векторов , для которого справедливо высказывание . Собственное пространство матрицы набор векторов , при котором уравнение имеет ненулевое решение для . Обозначим и столбцы матриц и . Тогда разложение может быть записано в виде: , где . Если сингулярное число , то и находится в нуль-пространстве матрицы , а если сингулярное число , то вектор находятся в собственном пространстве матрицы . Следовательно, можно сконструировать базисы для различных векторных подпространств, определенных матрицей . Hабор векторов в векторном пространстве формирует базис для , если любой вектор из можно представить в виде линейной комбинации векторов единственным способом. Пусть будет набором тех столбцов , для которых , а все остальные столбцы . Также, пусть будет набором столбцов , для которых , а все остальные столбцы , включая и те, для которых . Тогда, если количество ненулевых сингулярных чисел, то имеется столбцов в наборе и столбцов в наборе и , а также столбцов в наборе . Каждый из этих наборов формирует базис векторного пространства матрицы :
- ортонормальный базис для ортогонального комплементарного нуль-пространства ,
- ортонормальный базис для нуль-пространства ,
- ортонормальный базис для собственного пространства ,
- ортонормальный базис для ортогонального комплементарного нуль-пространства .
SVD и собственные числа матрицы
Сингулярное разложение обладает свойством, которое связывает задачу отыскания сингулярного разложения и задачу отыскания собственных векторов. Собственный вектор матрицы такой вектор, при котором выполняется условие , число называется собственным числом. Так как матрицы и ортогональные, то
Умножая оба выражения справа соответственно на и получаем
Из этого следует, что столбцы матрицы являются собственными векторами матрицы , а квадраты сингулярных чисел ее собственными числами. Также столбцы матрицы являются собственными векторами матрицы , а квадраты сингулярных чисел являются ее собственными числами.
SVD и норма матриц
Рассмотрим изменение длины вектора до и после его умножения слева на матрицу . Евклидова норма вектора определена как
Если матрица ортогональна, длина вектора остается неизменной. В противном случае можно вычислить, насколько матрица растянула вектор .
Евклидова норма матрицы есть максимальный коэффициент растяжения произвольного вектора заданной матрицей
Альтернативой Евклидовой норме является норма Фробениуса:
Если известно сингулярное разложение, то обе эти нормы легко вычислить. Пусть сингулярные числа матрицы , отличные от нуля. Тогда
и
Сингулярные числа матрицы это длины осей эллипсоида, заданного множеством
Нахождение псевдообратной матрицы с помощью SVD
Если -матрица является вырожденной или прямоугольной, то обратной матрицы для нее не существует. Однако для может быть найдена псевдообратная
матрица такая матрица, для которой выполняются условия
Пусть найдено разложение матрицы вида
, и . Тогда матрица является для матрицы псевдообратной. Действительно, , .
Метод наименьших квадратов и число обусловленности
Задача наименьших квадратов ставится следующим образом. Даны действительная -матрица и действительный -вектор . Требуется найти действительный -вектор , минимизирующий Евклидову длину
вектора невязки,задачи наименьших квадратов
Для отыскания решения требуется обратить матрицу . Для квадратных матриц число обусловленности определено отношением
Из формулы Евклидовой нормы матрицы и предыдущей формулы следует, что число обусловленности матрицы есть отношение ее первого сингулярного числа к последнему.
Следовательно, число обусловленности матрицы есть квадрат числа обусловленности матрицы . Это высказывание справедливо и для вырожденных матриц, если полагать число обусловленности как отношение , ранг матрицы . Поэтому для получения обращения, устойчивого к малым изменениям значений матрицы , используется усеченное SVD.
Усеченное SVD при обращении матриц
Пусть матрица представлена в виде . Тогда при нахождении обратной матрицы в силу ортогональности матриц и и в силу условия убывания диагональных элементов матрицы , псевдообратная матрица будет более зависеть от тех элементов матрицы , которые имеют меньшие значения, чем от первых сингулярных чисел. Действительно, если матрица имеет сингулярные числа , то сингулярные числа матрицы равны
и
Считая первые сингулярных чисел определяющими собственное пространство матрицы , используем при обращении матрицы первые сингулярных чисел, . Тогда обратная матрица будет найдена как .
Определим усеченную псевдообратную матрицу как
где -диагональная матрица.
Смотри также
- Метод главных компонент
- Простой итерационный алгоритм сингулярного разложения
- Регрессионный анализ
- Интегральный индикатор
- Согласование экспертных оценок
Литература
- Голуб Дж., Ван-Лоун Ч. Матричные вычисления. М.: Мир. 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.