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

Сингуля́рное разложе́ние (англ. singular value decomposition, SVD) — это разложение прямоугольной вещественной или комплексной матрицы, имеющее широкое применение, в силу своей наглядной геометрической интерпретации, при решении многих прикладных задач.

Сингулярное разложение матрицы <math>M</math> позволяет вычислять сингулярные числа данной матрицы, а также, левые и правые сингулярные векторы матрицы <math>M</math>:

• левые сингулярные векторы матрицы <math>M</math> — это собственные векторы матрицы <math>MM^{*}</math>;
• правые сингулярные векторы матрицы <math>M</math> — это собственные векторы матрицы <math>M^{*}M</math>.

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

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

Сингулярное разложение также используется для приближения матриц матрицами заданного ранга.

Определение

Пусть матрица <math>M</math> порядка <math>m \times n</math> состоит из элементов из поля <math>K</math>, где <math>K</math> — либо поле вещественных чисел, либо поле комплексных чисел.

Сингулярные числа и сингулярные векторы

Неотрицательное вещественное число <math>\sigma</math> называется сингулярным числом матрицы <math>M</math>, тогда и только тогда, когда существуют два вектора единичной длины <math>u \in K^m</math> и <math>v \in K^n</math> такие, что:

<math>Mv = \sigma u,</math> и <math>M^{*} u = \sigma v.</math>

Такие векторы <math>u</math> и <math>v</math> называются, соответственно, левым сингулярным вектором и правым сингулярным вектором, соответствующим сингулярному числу <math>\sigma</math>.

Разложение матрицы

Сингулярным разложением матрицы <math>M</math> порядка <math>m \times n</math> является разложение следующего вида

<math>M = U\Sigma V^{*},</math>

где <math>\Sigma</math> — матрица размера <math>m \times n</math>, у которой элементы, лежащие на главной диагонали — это сингулярные числа (а все элементы, не лежащие на главной диагонали, являются нулевыми), а матрицы <math>U</math> (порядка <math>m</math>) и <math>V</math> (порядка <math>n</math>) — это две унитарные матрицы, состоящие из левых и правых сингулярных векторов соответственно (а <math>V^*</math> — это сопряжённо-транспонированная матрица к <math>V</math>).

Пример

Пусть дана матрица:

<math>M =

\begin{bmatrix} 1 & 0 & 0 & 0 & 2\\ 0 & 0 & 3 & 0 & 0\\ 0 & 0 & 0 & 0 & 0\\ 0 & 4 & 0 & 0 & 0\end{bmatrix} </math>

Одним из сингулярных разложений этой матрицы является разложение <math>M = U \Sigma V^*</math>, где матрицы <math>U</math>, <math>\Sigma</math> и <math>V^*</math> следующие:

<math>

U = \begin{bmatrix} 0 & 0 & 1 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 0 & -1\\ 1 & 0 & 0 & 0\end{bmatrix}, \quad

\Sigma = \begin{bmatrix} 4 & 0 & 0 & 0 & 0\\ 0 & 3 & 0 & 0 & 0\\ 0 & 0 & \sqrt{5} & 0 & 0\\ 0 & 0 & 0 & 0 & 0\end{bmatrix}, \quad

V^* = \begin{bmatrix} 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0\\ \sqrt{0.2} & 0 & 0 & 0 & \sqrt{0.8}\\ 0 & 0 & 0 & 1 & 0\\ -\sqrt{0.8} & 0 & 0 & 0 & \sqrt{0.2}\end{bmatrix}, </math> так как матрицы <math>U</math> и <math>V</math> унитарны (<math>UU^* = I</math> и <math>VV^* = I</math>, где <math>I</math> — единичная матрица), а <math>\Sigma</math> — прямоугольная диагональная матрица, то есть <math>\Sigma_{ij} = 0</math>, если <math>i \neq j</math>.

Реализация

Численные алгоритмы нахождения сингулярного разложения встроены во многие математические пакеты. Например, в системах MATLAB и GNU Octave его можно найти командой:

[U, S, V] = svd(M);

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

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

Для более визуального представления рассмотрим сферу <math>S</math> единичного радиуса в пространстве <math>\R^n</math>. Линейное отображение <math>T</math> отображает эту сферу в эллипсоид пространства <math>\R^m</math>. Тогда ненулевые сингулярные значения диагонали матрицы <math>\Sigma</math> являются длинами полуосей этого эллипсоида. В случае когда <math>n = m</math> и все сингулярные величины различны и отличны от нуля, сингулярное разложение линейного отображения <math>T</math> может быть легко проанализировано как последствие трех действий: рассмотрим эллипсоид <math>T(S)</math> и его оси; затем рассмотрим направления в <math>\R^n</math>, которые отображение <math>T</math> переводит в эти оси. Эти направления ортогональны. Вначале применим изометрию <math>\mathbf{v}^*</math>, отобразив эти направления на координатные оси <math>\R^n</math>. Вторым шагом применим эндоморфизм <math>\mathbf{d}</math>, диагонализированный вдоль координатных осей и расширяющий/сжимающий эти направления, используя длины полуосей <math>T(S)</math> как коэффициенты растяжения. Тогда произведение <math>\mathbf{d} \otimes \mathbf{v}^*</math> отображает единичную сферу на изометричный эллипсоид <math>T(S)</math>. Для определения последнего шага <math>u</math>, просто применим изометрию к этому эллипсоиду так, чтобы перевести его в <math>T(S)</math>. Как можно легко проверить, произведение <math>\mathbf{u} \otimes \mathbf{d} \otimes \mathbf{v}^*</math> совпадает с <math>T</math>.

Приложения

Псевдообратная матрица

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

Если <math>M = U\Sigma V^*</math>, то псевдообратная к ней матрица находится по формуле:

<math> M^+ = V \Sigma^+ U^*,</math>

где <math>\Sigma^+</math> — псевдообратная к матрице <math>\Sigma</math>, получающаяся из неё заменой каждого ненулевого элемента <math>\sigma</math> на диагонали на обратный к нему: <math>1 / {\sigma}</math>, с последующим транспонированием самой матрицы.

Приближение матрицей меньшего ранга

В некоторых практических задачах требуется приближать заданную матрицу <math>M</math> некоторой другой матрицей <math>M_k</math> с заранее заданным рангом <math>k</math>. Известна следующая теорема, которую иногда называют теоремой Эккарта — Янга.

Если потребовать, чтобы такое приближение было наилучшим в том смысле, что Фробениусова норма разности матриц <math>M</math> и <math>M_k</math> минимальна, при ограничении <math>\mbox{rank}(M_k) = k</math>, то оказывается, что наилучшая такая матрица <math>M_k</math> получается из сингулярного разложения матрицы <math>M</math> по формуле:

<math>M_k = U \Sigma_k V^*,</math>

где <math>\Sigma_k</math> — матрица <math>\Sigma</math>, в которой заменили нулями все диагональные элементы, кроме <math>k</math> наибольших элементов.

Если элементы матрицы <math>\Sigma</math> упорядочены по невозрастанию, то выражение для матрицы <math>M_k</math> можно переписать в такой форме:

<math>M_k = U_k \Sigma_k V_k^*,</math>

где матрицы <math>U_k</math>, <math>\Sigma_k</math> и <math>V_k</math> получаются из соответствующих матриц в сингулярном разложении матрицы <math>M</math> обрезанием до ровно <math>k</math> первых столбцов.

Таким образом видно, что приближая матрицу <math>M</math> матрицей меньшего ранга, мы выполняем своего рода сжатие информации, содержащейся в <math>M</math>: матрица <math>M</math> размера <math>m \times n</math> заменяется меньшими матрицами размеров <math>m \times k</math> и <math>k \times n</math> и диагональной матрицей с <math>k</math> элементами. При этом сжатие происходит с потерями — в приближении сохраняется лишь наиболее существенная часть матрицы <math>M</math>.

Во многом благодаря этому свойству сингулярное разложение и находит широкое практическое применение: в сжатии данных, обработке сигналов, численных итерационных методах для работы с матрицами, методе главных компонент, латентно-семантическом анализе и прочих областях.

Сокращенное представление

Для матрицы <math>M</math> порядка <math>m \times n</math> ранга <math>r</math> часто используют компактное представление разложения:

<math>M = U_r \Sigma_r V_r^*.</math>

Вычисляются только <math>r</math> столбцов <math>U</math> и <math>r</math> строк <math>V^*</math>. Остальные столбцы <math>U</math> и строки <math>V^*</math> не вычисляются. Это экономит большое количество памяти при <math>r<<n</math>.

Программные реализации

SVD входит в список основных методов многих математических библиотек, в том числе свободно распространяемых.
Так, например, существуют реализации

• В GNU Scientific library (GSL):

www.gnu.org/software/gsl/manual/html_node/Singular-Value-Decomposition.html

• Во framework'е ROOT, разрабатываемом в CERN и широко используемом в научной среде:

root.cern.ch/root/htmldoc/guides/users-guide/LinearAlgebra.html#svd

• В платной библиотеке Intel® Math Kernel Library (Intel® MKL).

software.intel.com/en-us/intel-mkl

• И некоторые другие

tedlab.mit.edu/~dr/SVDLIBC/
www.alglib.net/matrixops/general/svd.php

См. также

• Разложение матрицы
• Метод главных компонент
• Латентно-семантический анализ

Литература

• William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery. [www.haoli.org/nr/bookcpdf/c2-6.pdf 2.6 Singular Value Decomposition] // Numerical Recipes in C. — 2nd edition. — Cambridge: Cambridge University Press. — ISBN 0-521-43108-5.

Ссылки

Статьи

• [www.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 Статья о сингулярном разложении на machinelearning.ru]
• [mathworld.wolfram.com/SingularValueDecomposition.html Статья на MathWorld] и [demonstrations.wolfram.com/ImageCompressionViaTheSingularValueDecomposition/ пример использования] для сжатия изображения. (англ.)

Лекции on-line

• [www.youtube.com/watch?v=bJcc7A3TtYM Лекция о сингулярном разложении] в контексте метода главных компонент, Хайдельбергский университет, проф. Fred Hamprecht (англ.)

Отрывок, характеризующий Сингулярное разложение

– Да я его взял сперва наперво на зорьке еще, – продолжал Тихон, переставляя пошире плоские, вывернутые в лаптях ноги, – да и свел в лес. Вижу, не ладен. Думаю, дай схожу, другого поаккуратнее какого возьму.
– Ишь, шельма, так и есть, – сказал Денисов эсаулу. – Зачем же ты этого не пг'ивел?
– Да что ж его водить то, – сердито и поспешно перебил Тихон, – не гожающий. Разве я не знаю, каких вам надо?
– Эка бестия!.. Ну?..
– Пошел за другим, – продолжал Тихон, – подполоз я таким манером в лес, да и лег. – Тихон неожиданно и гибко лег на брюхо, представляя в лицах, как он это сделал. – Один и навернись, – продолжал он. – Я его таким манером и сграбь. – Тихон быстро, легко вскочил. – Пойдем, говорю, к полковнику. Как загалдит. А их тут четверо. Бросились на меня с шпажками. Я на них таким манером топором: что вы, мол, Христос с вами, – вскрикнул Тихон, размахнув руками и грозно хмурясь, выставляя грудь.
– То то мы с горы видели, как ты стречка задавал через лужи то, – сказал эсаул, суживая свои блестящие глаза.
Пете очень хотелось смеяться, но он видел, что все удерживались от смеха. Он быстро переводил глаза с лица Тихона на лицо эсаула и Денисова, не понимая того, что все это значило.
– Ты дуг'ака то не представляй, – сказал Денисов, сердито покашливая. – Зачем пег'вого не пг'ивел?
Тихон стал чесать одной рукой спину, другой голову, и вдруг вся рожа его растянулась в сияющую глупую улыбку, открывшую недостаток зуба (за что он и прозван Щербатый). Денисов улыбнулся, и Петя залился веселым смехом, к которому присоединился и сам Тихон.
– Да что, совсем несправный, – сказал Тихон. – Одежонка плохенькая на нем, куда же его водить то. Да и грубиян, ваше благородие. Как же, говорит, я сам анаральский сын, не пойду, говорит.
– Экая скотина! – сказал Денисов. – Мне расспросить надо…
– Да я его спрашивал, – сказал Тихон. – Он говорит: плохо зн аком. Наших, говорит, и много, да всё плохие; только, говорит, одна названия. Ахнете, говорит, хорошенько, всех заберете, – заключил Тихон, весело и решительно взглянув в глаза Денисова.
– Вот я те всыплю сотню гог'ячих, ты и будешь дуг'ака то ког'чить, – сказал Денисов строго.
– Да что же серчать то, – сказал Тихон, – что ж, я не видал французов ваших? Вот дай позатемняет, я табе каких хошь, хоть троих приведу.
– Ну, поедем, – сказал Денисов, и до самой караулки он ехал, сердито нахмурившись и молча.
Тихон зашел сзади, и Петя слышал, как смеялись с ним и над ним казаки о каких то сапогах, которые он бросил в куст.
Когда прошел тот овладевший им смех при словах и улыбке Тихона, и Петя понял на мгновенье, что Тихон этот убил человека, ему сделалось неловко. Он оглянулся на пленного барабанщика, и что то кольнуло его в сердце. Но эта неловкость продолжалась только одно мгновенье. Он почувствовал необходимость повыше поднять голову, подбодриться и расспросить эсаула с значительным видом о завтрашнем предприятии, с тем чтобы не быть недостойным того общества, в котором он находился.
Посланный офицер встретил Денисова на дороге с известием, что Долохов сам сейчас приедет и что с его стороны все благополучно.
Денисов вдруг повеселел и подозвал к себе Петю.
– Ну, г'асскажи ты мне пг'о себя, – сказал он.


Петя при выезде из Москвы, оставив своих родных, присоединился к своему полку и скоро после этого был взят ординарцем к генералу, командовавшему большим отрядом. Со времени своего производства в офицеры, и в особенности с поступления в действующую армию, где он участвовал в Вяземском сражении, Петя находился в постоянно счастливо возбужденном состоянии радости на то, что он большой, и в постоянно восторженной поспешности не пропустить какого нибудь случая настоящего геройства. Он был очень счастлив тем, что он видел и испытал в армии, но вместе с тем ему все казалось, что там, где его нет, там то теперь и совершается самое настоящее, геройское. И он торопился поспеть туда, где его не было.
Когда 21 го октября его генерал выразил желание послать кого нибудь в отряд Денисова, Петя так жалостно просил, чтобы послать его, что генерал не мог отказать. Но, отправляя его, генерал, поминая безумный поступок Пети в Вяземском сражении, где Петя, вместо того чтобы ехать дорогой туда, куда он был послан, поскакал в цепь под огонь французов и выстрелил там два раза из своего пистолета, – отправляя его, генерал именно запретил Пете участвовать в каких бы то ни было действиях Денисова. От этого то Петя покраснел и смешался, когда Денисов спросил, можно ли ему остаться. До выезда на опушку леса Петя считал, что ему надобно, строго исполняя свой долг, сейчас же вернуться. Но когда он увидал французов, увидал Тихона, узнал, что в ночь непременно атакуют, он, с быстротою переходов молодых людей от одного взгляда к другому, решил сам с собою, что генерал его, которого он до сих пор очень уважал, – дрянь, немец, что Денисов герой, и эсаул герой, и что Тихон герой, и что ему было бы стыдно уехать от них в трудную минуту.
Уже смеркалось, когда Денисов с Петей и эсаулом подъехали к караулке. В полутьме виднелись лошади в седлах, казаки, гусары, прилаживавшие шалашики на поляне и (чтобы не видели дыма французы) разводившие красневший огонь в лесном овраге. В сенях маленькой избушки казак, засучив рукава, рубил баранину. В самой избе были три офицера из партии Денисова, устроивавшие стол из двери. Петя снял, отдав сушить, свое мокрое платье и тотчас принялся содействовать офицерам в устройстве обеденного стола.
Через десять минут был готов стол, покрытый салфеткой. На столе была водка, ром в фляжке, белый хлеб и жареная баранина с солью.
Сидя вместе с офицерами за столом и разрывая руками, по которым текло сало, жирную душистую баранину, Петя находился в восторженном детском состоянии нежной любви ко всем людям и вследствие того уверенности в такой же любви к себе других людей.
– Так что же вы думаете, Василий Федорович, – обратился он к Денисову, – ничего, что я с вами останусь на денек? – И, не дожидаясь ответа, он сам отвечал себе: – Ведь мне велено узнать, ну вот я и узнаю… Только вы меня пустите в самую… в главную. Мне не нужно наград… А мне хочется… – Петя стиснул зубы и оглянулся, подергивая кверху поднятой головой и размахивая рукой.
– В самую главную… – повторил Денисов, улыбаясь.
– Только уж, пожалуйста, мне дайте команду совсем, чтобы я командовал, – продолжал Петя, – ну что вам стоит? Ах, вам ножик? – обратился он к офицеру, хотевшему отрезать баранины. И он подал свой складной ножик.
Офицер похвалил ножик.
– Возьмите, пожалуйста, себе. У меня много таких… – покраснев, сказал Петя. – Батюшки! Я и забыл совсем, – вдруг вскрикнул он. – У меня изюм чудесный, знаете, такой, без косточек. У нас маркитант новый – и такие прекрасные вещи. Я купил десять фунтов. Я привык что нибудь сладкое. Хотите?.. – И Петя побежал в сени к своему казаку, принес торбы, в которых было фунтов пять изюму. – Кушайте, господа, кушайте.
– А то не нужно ли вам кофейник? – обратился он к эсаулу. – Я у нашего маркитанта купил, чудесный! У него прекрасные вещи. И он честный очень. Это главное. Я вам пришлю непременно. А может быть еще, у вас вышли, обились кремни, – ведь это бывает. Я взял с собою, у меня вот тут… – он показал на торбы, – сто кремней. Я очень дешево купил. Возьмите, пожалуйста, сколько нужно, а то и все… – И вдруг, испугавшись, не заврался ли он, Петя остановился и покраснел.
Он стал вспоминать, не сделал ли он еще каких нибудь глупостей. И, перебирая воспоминания нынешнего дня, воспоминание о французе барабанщике представилось ему. «Нам то отлично, а ему каково? Куда его дели? Покормили ли его? Не обидели ли?» – подумал он. Но заметив, что он заврался о кремнях, он теперь боялся.
«Спросить бы можно, – думал он, – да скажут: сам мальчик и мальчика пожалел. Я им покажу завтра, какой я мальчик! Стыдно будет, если я спрошу? – думал Петя. – Ну, да все равно!» – и тотчас же, покраснев и испуганно глядя на офицеров, не будет ли в их лицах насмешки, он сказал:
– А можно позвать этого мальчика, что взяли в плен? дать ему чего нибудь поесть… может…
– Да, жалкий мальчишка, – сказал Денисов, видимо, не найдя ничего стыдного в этом напоминании. – Позвать его сюда. Vincent Bosse его зовут. Позвать.
– Я позову, – сказал Петя.
– Позови, позови. Жалкий мальчишка, – повторил Денисов.
Петя стоял у двери, когда Денисов сказал это. Петя пролез между офицерами и близко подошел к Денисову.
– Позвольте вас поцеловать, голубчик, – сказал он. – Ах, как отлично! как хорошо! – И, поцеловав Денисова, он побежал на двор.
– Bosse! Vincent! – прокричал Петя, остановясь у двери.
– Вам кого, сударь, надо? – сказал голос из темноты. Петя отвечал, что того мальчика француза, которого взяли нынче.
– А! Весеннего? – сказал казак.
Имя его Vincent уже переделали: казаки – в Весеннего, а мужики и солдаты – в Висеню. В обеих переделках это напоминание о весне сходилось с представлением о молоденьком мальчике.
– Он там у костра грелся. Эй, Висеня! Висеня! Весенний! – послышались в темноте передающиеся голоса и смех.
– А мальчонок шустрый, – сказал гусар, стоявший подле Пети. – Мы его покормили давеча. Страсть голодный был!
В темноте послышались шаги и, шлепая босыми ногами по грязи, барабанщик подошел к двери.
– Ah, c'est vous! – сказал Петя. – Voulez vous manger? N'ayez pas peur, on ne vous fera pas de mal, – прибавил он, робко и ласково дотрогиваясь до его руки. – Entrez, entrez. [Ах, это вы! Хотите есть? Не бойтесь, вам ничего не сделают. Войдите, войдите.]