- Сингулярное разложение
-
Сингуля́рное разложе́ние (англ. singular value decomposition, SVD) — это разложение прямоугольной вещественной или комплексной матрицы, применяющееся во многих областях прикладной математики. Сингулярное разложение может быть использовано, например, для нахождения ранга и ядра матриц, псевдообратных матриц, приближения матриц матрицами заданного ранга.
Содержание
Определение
Любая матрица порядка , элементы которой — комплексные числа, может быть представлена в следующем виде, называемом сингулярным разложением матрицы :
где — унитарная матрица порядка , — диагональная матрица порядка с неотрицательными вещественными числами на диагонали, — унитарная матрица порядка , а — сопряжённо-транспонированная матрица к .
Под диагональной прямоугольной матрицей здесь понимается матрица такая, что все её недиагональные элементы равны нулю:
- если
В частном случае, когда состоит из вещественных чисел, существует сингулярное разложение вида , в котором и — ортогональные матрицы.
Элементы на диагонали матрицы называются сингулярными числами матрицы и определены с точностью до их перестановки. Обычно требуют, чтобы они располагались в матрице в невозрастающем порядке — тогда (но не и ) однозначно определяется по матрице . Столбцы матриц и называются, соответственно, левыми и правыми сингулярными векторами.
Пример
Пусть дана матрица:
Одним из сингулярных разложений этой матрицы является разложение , где матрицы , и следующие:
так как матрицы и унитарны ( и , где — единичная матрица), а — прямоугольная диагональная матрица, то есть , если .
Численные алгоритмы нахождения сингулярного разложения встроены во многие математические пакеты. Например, в системах MATLAB и GNU Octave его можно найти командой:
[U, S, V] = svd(M);
Сингулярные числа и сингулярные векторы
Сингулярные числа и сингулярные вектора можно также определить следующим образом, эквивалентным данным им выше определениям, как частям сингулярного разложения.
Пусть матрица порядка состоит из элементов из поля , где — либо поле вещественных чисел, либо поле комплексных чисел.
Неотрицательное вещественное число называется сингулярным числом матрицы если и только если существуют вектора единичной длины и такие, что:
- и
Такие векторы и называются, соответственно, левым сингулярным вектором и правым сингулярным вектором, соответствующим сингулярному числу .
В сингулярном разложении:
диагональные элементы матрицы с необходимостью являются сингулярными числами матрицы , а столбцы матриц и содержат левые и правые сингулярные векторы для соответствующих им сингулярных значений на диагонали матрицы .
Геометрический смысл
Пусть матрице поставлен в соответствие линейный оператор. Cингулярное разложение можно переформулировать в геометрических терминах. Линейный оператор, отображающий элементы пространства в себя представим в виде последовательно выполняемых линейных операторов вращения и растяжения. Поэтому компоненты сингулярного разложения наглядно показывают геометрические изменения при отображении линейным оператором множества векторов из векторного пространства в себя или в векторное пространство другой размерности[1].
Для более визуального представления рассмотрим сферу единичного радиуса в пространстве . Линейное отображение отображает эту сферу в эллипсоид пространства . Тогда ненулевые сингулярные значения диагонали матрицы являются длинами полуосей этого эллипсоида. В случае когда и все сингулярные величины различны и отличны от нуля, сингулярное разложение линейного отображения может быть легко проанализировано как последствие трех действий: рассмотрим эллипсоид и его оси; затем рассмотрим направления в , которые отображение переводит в эти оси. Эти направления ортогональны. Вначале применим изометрию , отобразив эти направления на координатные оси . Вторым шагом применим эндоморфизм , диагонализированный вдоль координатных осей и расширяющий/сжимающий эти направления, используя длины полуосей как коэффициенты растяжения. Тогда произведение отображает единичную сферу на изометричный эллипсоид . Для определения последнего шага , просто применим изометрию к этому эллипсоиду так, чтобы перевести его в . Как можно легко проверить, произведение совпадает с .
Приложения
Псевдообратная матрица
Сингулярное разложение может быть использовано для нахождения псевдообратных матриц, которые применяются, в частности, в методе наименьших квадратов.
Если , то псевдообратная к ней матрица находится по формуле:
где — псевдообратная к матрице , получающаяся из неё заменой каждого ненулевого элемента на диагонали на обратный к нему: .
Приближение матрицей меньшего ранга
В некоторых практических задачах требуется приближать заданную матрицу некоторой другой матрицей с заранее заданным рангом . Известна следующая теорема, которую иногда называют теоремой Эккарта — Янга.[2]
Если потребовать, чтобы такое приближение было наилучшим в том смысле, что Фробениусова норма разности матриц и минимальна, при ограничении , то оказывается, что наилучшая такая матрица получается из сингулярного разложения матрицы по формуле:
где — матрица , в которой заменили нулями все диагональные элементы, кроме наибольших элементов.
Если элементы матрицы упорядочены по невозрастанию, то выражение для матрицы можно переписать в такой форме:
где матрицы , и получаются из соответствующих матриц в сингулярном разложении матрицы обрезанием до ровно первых столбцов.
Таким образом видно, что приближая матрицу матрицей меньшего ранга, мы выполняем своего рода сжатие информации, содержащейся в : матрица размера заменяется меньшими матрицами размеров и и диагональной матрицей с элементами. При этом сжатие происходит с потерями — в приближении сохраняется лишь наиболее существенная часть матрицы .
Во многом благодаря этому свойству сингулярное разложение и находит широкое практическое применение: в сжатии данных, обработке сигналов, численных итерационных методах для работы с матрицами, методе главных компонент, латентно-семантическом анализе и прочих областях.
См. также
Примечания
- ↑ Сингулярное разложение на вики Распознавание
- ↑ Eckart, C., and Young, G. The approximation of one matrix by another of lower rank. Psychometrika, 1936, 1, 211—218.
Литература
- William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery. 2.6 Singular Value Decomposition // Numerical Recipes in C. — 2nd edition. — Cambridge: Cambridge University Press. — ISBN 0-521-43108-5
Ссылки
- Статья о сингулярном разложение на machinelearning, ru
- Статья на MathWorld и пример использования для сжатия изображения. (англ.)
Категория:- Разложения матриц
Wikimedia Foundation. 2010.