Введение

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

В линейной алгебре сингулярное разложение (SVD) — это разложение реальной или комплексной матрицы на множители в виде вращения, за которым следует масштабирование, за которым следует другое вращение. Оно обобщает разложение на собственные значения квадратной нормальной матрицы с ортонормальным набором собственных векторов на любую матрицу размера m × n. Оно связано с полярным разложением. В частности, сингулярное разложение комплексной матрицы \mathbf{M} — это разложение вида, где \mathbf{U} — комплексная унитарная матрица размера m × m, — прямоугольная диагональная матрица с неотрицательными действительными числами на диагонали, \mathbf{V} — комплексная унитарная матрица, а — сопряжённо-транспонированная матрица \mathbf{V}. Такое разложение всегда существует для любой комплексной матрицы. Если \mathbf{M} — вещественная, то \mathbf{U} и \mathbf{V} могут быть гарантированно вещественными ортогональными матрицами; в таких случаях SVD часто обозначается.

Диагональные элементы матрицы однозначно определяются матрицей \mathbf{M} и известны как сингулярные значения \mathbf{M}. Количество ненулевых сингулярных значений равно рангу \mathbf{M}. Столбцы \mathbf{U} и столбцы \mathbf{V} называются соответственно левыми и правыми сингулярными векторами \mathbf{M}. Они образуют два набора ортонормальных базисов \mathbf{u}_1, \ldots, \mathbf{u}_m и \mathbf{v}_1, \ldots, \mathbf{v}_n, и если они упорядочены так, что сингулярные значения со значением, равным нулю, находятся во всех столбцах (или строках) с наибольшими номерами, то сингулярное разложение можно записать как, где — ранг \mathbf{M}.

SVD не является единственным, однако всегда можно выбрать разложение таким образом, чтобы сингулярные значения были упорядочены по убыванию. В этом случае (но не \mathbf{U} и \mathbf{V}) однозначно определяется \mathbf{M}.

Термин иногда относится к компактному SVD, аналогичному разложению, в котором \mathbf{\Sigma} — квадратная диагональная матрица размера r × r, где r ≤ min{m, n} — ранг \mathbf{M}, и содержит только ненулевые сингулярные значения. В этом варианте \mathbf{U} — полуунитарная матрица размера m × r, а — полуунитарная матрица размера n × r, такая что

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

Ротация, масштабирование координат и отражение

В особом случае, когда \mathbf M является действительной квадратной матрицей размера m \times m, матрицы \mathbf U и \mathbf V^* также могут быть выбраны как действительные матрицы размера m \times m. В этом случае "унитарная" эквивалентна "ортогональной". Интерпретируя как унитарные матрицы, так и диагональную матрицу, обобщенную здесь как \mathbf A, как линейное преобразование \mathbf x \mapsto \mathbf{Ax} пространства \mathbf R^m, матрицы \mathbf U и \mathbf V^* представляют собой вращения или отражения пространства, а \mathbf \Sigma – масштабирование каждой координаты \mathbf x_i на коэффициент \sigma_i. Таким образом, SVD-разложение раскладывает любое линейное преобразование пространства \mathbf R^m на композицию из трех геометрических преобразований: вращение или отражение, за которым следует масштабирование координат, а затем еще одно вращение или отражение.

В частности, если у матрицы \mathbf M положительный определитель, то матрицы \mathbf U и \mathbf V^* могут быть выбраны как оба вращения с отражением, либо оба вращения без отражения. Если определитель отрицательный, то ровно одна из них будет содержать отражение. Если определитель равен нулю, каждая из них может быть независимо выбрана любого типа. Если матрица \mathbf M является действительной, но не квадратной, то есть имеет размер m \times n при m \neq n, ее можно интерпретировать как линейное преобразование из \mathbf R^n в \mathbf R^m. Тогда \mathbf U и \mathbf V^* можно выбрать как вращения/отражения в \mathbf R^m и \mathbf R^n соответственно, а \mathbf \Sigma, помимо масштабирования первых \min\{m,n\} координат, также дополняет вектор нулями, то есть отбрасывает лишние координаты, чтобы преобразовать \mathbf R^n в \mathbf R^m.

Сингулярные значения как полуоси эллипса или эллипсоида

Как показано на рисунке, сингулярные значения можно интерпретировать как величину полуосей эллипса в 2D. Эта концепция может быть обобщена на n-мерное евклидово пространство, где сингулярные значения любой квадратной матрицы n \times n рассматриваются как величина полуосей n-мерного эллипсоида. Аналогично, сингулярные значения любой матрицы m \times n можно рассматривать как величину полуосей n-мерного эллипсоида в m-мерном пространстве, например, как эллипс в (наклонной) 2D-плоскости в 3D-пространстве. Сингулярные значения кодируют величину полуосей, а сингулярные векторы – направление. Более подробная информация приведена ниже.

Столбцы и являются ортонормальными основаниями

Поскольку \mathbf U и \mathbf V^* являются унитарными, столбцы каждого из них образуют набор ортонормальных векторов, которые можно рассматривать как базисные векторы. Матрица \mathbf M отображает базисный вектор \mathbf V i в растянутый единичный вектор \sigma i \mathbf U i. По определению унитарной матрицы, то же самое верно и для их эрмитовых транспонированных \mathbf U^* и \mathbf V, за исключением потери геометрической интерпретации сингулярных значений как растяжений. Короче говоря, столбцы \mathbf U, \mathbf U^*, \mathbf V и \mathbf V^* образуют ортонормальные базисы. Если \mathbf M является положительно полуопределенной эрмитовой матрицей, то \mathbf U и \mathbf V обе равны унитарной матрице, используемой для диагонализации \mathbf M. Однако, если \mathbf M не является положительно полуопределенной и эрмитовой, но все же диагонализуема, ее спектральное разложение и сингулярное разложение различны.

Отношение к четырем фундаментальным подпространствам

Первые r столбцов \mathbf U образуют базис пространства столбцов \mathbf M. Последние m-r столбцов \mathbf U образуют базис нулевого пространства \mathbf M^*. Первые r столбцов \mathbf V образуют базис пространства столбцов \mathbf M^* (пространства строк \mathbf M в вещественном случае). Последние n-r столбцов \mathbf V образуют базис нулевого пространства \mathbf M.

Псевдоинверс

Разложение по сингулярным числам может быть использовано для вычисления псевдообратной матрицы. Псевдообратная матрицы \mathbf M с разложением по сингулярным числам равна,

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

Решение однородных линейных уравнений

Набор однородных линейных уравнений может быть записан как \mathbf{Ax} = \mathbf{0} для матрицы \mathbf{A} и вектора \mathbf{x}. Типичная ситуация состоит в том, что \mathbf{A} известно, и требуется определить ненулевой вектор \mathbf{x}, который удовлетворяет этому уравнению. Такой вектор \mathbf{x} принадлежит нулевому пространству матрицы \mathbf{A} и иногда называется (правым) нулевым вектором матрицы \mathbf{A}. Вектор \mathbf{x} можно охарактеризовать как правый сингулярный вектор, соответствующий сингулярному значению матрицы \mathbf{A}, равном нулю. Это наблюдение означает, что если \mathbf{A} – квадратная матрица и не имеет нулевых сингулярных значений, то уравнение не имеет ненулевых решений \mathbf{x}. Это также означает, что если существует несколько нулевых сингулярных значений, то любая линейная комбинация соответствующих правых сингулярных векторов является допустимым решением. Аналогично определению (правого) нулевого вектора, ненулевой вектор \mathbf{x}, удовлетворяющий \mathbf{x}^* \mathbf{A} = \mathbf{0}, где \mathbf{x}^* обозначает сопряжённо-транспонированный вектор \mathbf{x}, называется левым нулевым вектором матрицы \mathbf{A}.

Минимизация общего числа наименьших квадратов

В задаче наименьших квадратов в общем смысле ищут вектор \mathbf x, минимизирующий 2-норму вектора \mathbf A \mathbf x, при условии . Решение оказывается правым сингулярным вектором матрицы \mathbf A, соответствующим наименьшему сингулярному значению.

Диапазон, нулевое пространство и ранжирование

Другое применение сингулярного разложения (SVD) заключается в том, что оно предоставляет явное представление области значений и ядра матрицы \mathbf M. Правые сингулярные векторы, соответствующие обращающимся в ноль сингулярным значениям \mathbf M, образуют базис ядра \mathbf M, а левые сингулярные векторы, соответствующие ненулевым сингулярным значениям \mathbf M, образуют базис области значений \mathbf M. Например, в вышеприведенном примере ядро образуется последней строкой \mathbf V^*, а область значений – первыми тремя столбцами \mathbf U. Следовательно, ранг \mathbf M равен количеству ненулевых сингулярных значений, что совпадает с количеством ненулевых диагональных элементов в \Sigma. В численной линейной алгебре сингулярные значения можно использовать для определения эффективного ранга матрицы, поскольку ошибка округления может приводить к небольшим, но ненулевым сингулярным значениям в матрице, имеющей недостаточный ранг. Сингулярные значения, выходящие за пределы существенного разрыва, считаются численно эквивалентными нулю.

Приближение матрицы низкого ранга

Некоторые практические приложения требуют решения задачи приближения матрицы \mathbf M к другой матрице, называемой усеченной, имеющей заданный ранг r. Если приближение основано на минимизации нормы Фробениуса разности между \mathbf M и \tilde{\mathbf M} при условии, что, то решение задается сингулярным разложением (SVD) матрицы \mathbf M, а именно:

где \tilde{\mathbf U}\Sigma\tilde{\mathbf V}^T – та же матрица, что и \mathbf U\Sigma\mathbf V}^T, за исключением того, что она содержит только r наибольших сингулярных значений (остальные сингулярные значения заменены нулями). Это известно как теорема Эккарта — Янга, поскольку она была доказана этими двумя авторами в 1936 году (хотя позже выяснилось, что она была известна и более ранним исследователям; см.).

Отдельные модели

СВД можно рассматривать как разложение матрицы на взвешенную, упорядоченную сумму разделяемых матриц. Под разделяемостью мы подразумеваем, что матрицу **A** можно представить как внешнее произведение двух векторов или, в координатах, в частности, матрицу **M** можно разложить как,

Здесь **U**ᵢ и **V**ᵢ – i-е столбцы соответствующих SVD-матриц, σᵢ – упорядоченные сингулярные значения, и каждая **A**ᵢ является разделяемой. SVD может быть использована для нахождения разложения фильтра обработки изображений на разделяемые горизонтальные и вертикальные фильтры. Следует отметить, что число ненулевых σᵢ точно равно рангу матрицы. Разделяемые модели часто встречаются в биологических системах, и SVD-факторизация полезна для анализа таких систем. Например, рецептивные поля некоторых простых клеток зрительной области V1 могут быть хорошо описаны фильтром Габора в пространственной области, умноженным на модуляционную функцию во временной области. Таким образом, учитывая линейный фильтр, оцененный, например, методом обратной корреляции, можно объединить два пространственных измерения в одно, получив таким образом двумерный фильтр (пространство, время), который можно разложить с помощью SVD. Первый столбец **U** в SVD-факторизации тогда представляет собой фильтр Габора, а первый столбец **V** – временную модуляцию (или наоборот). Можно также определить индекс разделяемости,

который представляет собой долю мощности в матрице **M**, объясняемую первой разделяемой матрицей в разложении.

Ближайшая ортогональная матрица

Можно использовать сингулярное разложение (SVD) квадратной матрицы \mathbf A для определения ортогональной матрицы, наиболее близкой к \mathbf A. Степень близости оценивается нормой Фробениуса произведения \mathbf 0 \mathbf A. Решение представляет собой произведение \mathbf U \mathbf V^*. Это интуитивно понятно, поскольку ортогональная матрица имеет разложение \mathbf U \mathbf I \mathbf V^*, где \mathbf I – единичная матрица, так что если σ_i – сингулярные значения, то произведение \mathbf U \mathbf V^* сводится к замене сингулярных значений на единицы. Эквивалентно, решение является унитарной матрицей из полярного разложения в любом порядке – растяжения и вращения, как описано выше. Схожая задача, имеющая интересные применения в анализе формы, – это ортогональная задача Прокруста, которая заключается в поиске ортогональной матрицы \mathbf O, наиболее точно отображающей матрицу \mathbf A на матрицу \mathbf B. В частности,

где ||.||_F обозначает норму Фробениуса. Эта задача эквивалентна поиску ближайшей ортогональной матрицы к заданной матрице \mathbf A.

Алгоритм Кабша

Алгоритм Кэбша (в других областях известный как проблема Вахбы) использует сингулярное разложение (SVD) для вычисления оптимального поворота (в смысле минимизации по методу наименьших квадратов), который наилучшим образом сопоставит один набор точек с другим соответствующим набором точек. Он применяется, в частности, для сравнения структур молекул.

Обработка сигналов

SVD и псевдообратная матрица успешно применяются в обработке сигналов, обработке изображений и работе с большими данными (например, в геномной обработке сигналов).

Другие примеры

SVD также широко применяется для изучения линейных обратных задач и полезен в анализе методов регуляризации, таких как метод Тихонова. Он широко используется в статистике, где связан с анализом главных компонент и анализом соответствий, а также в обработке сигналов и распознавании образов. Он также применяется в модальном анализе по выходным данным, где ненормированные собственные формы могут быть определены из сингулярных векторов. Другим применением является латентно-семантический анализ в обработке текстов на естественном языке. В общих численных расчетах, связанных с линейными или линеаризованными системами, существует универсальная константа, характеризующая регулярность или сингулярность задачи – "число обусловленности" системы. Она часто определяет скорость сходимости или погрешность заданной вычислительной схемы для таких систем. SVD также играет важную роль в области квантовой информации, в форме, часто называемой разложением Шмидта. С его помощью состояния двух квантовых систем естественным образом раскладываются, предоставляя необходимое и достаточное условие для их запутанности: если ранг матрицы больше единицы. Одно из применений SVD для достаточно больших матриц – численное прогнозирование погоды, где методы Ланцоса используются для оценки нескольких наиболее быстро растущих возмущений центрального численного прогноза погоды за заданный начальный период времени; то есть, сингулярных векторов, соответствующих наибольшим сингулярным значениям линеаризованного оператора переноса для глобальной погоды за этот временной интервал. В этом случае выходные сингулярные векторы представляют собой целые метеорологические системы. Затем эти возмущения используются в полной нелинейной модели для генерации ансамблевого прогноза, что позволяет оценить некоторые неопределенности, которые следует учитывать при текущем центральном прогнозе. SVD также применяется в задаче моделирования пониженного порядка. Цель моделирования пониженного порядка – уменьшить число степеней свободы в сложной системе, подлежащей моделированию. SVD был сопряжен с радиальными базисными функциями для интерполяции решений нестационарных трехмерных задач течения. Интересно, что SVD использовался для улучшения моделирования гравитационных волн наземным гравитационно-волновым интерферометром aLIGO. SVD может помочь повысить точность и скорость генерации формы волны для поддержки поиска гравитационных волн и обновления двух различных моделей формы волны. Сингулярное разложение значений используется в рекомендательных системах для прогнозирования оценок товаров пользователями. Разработаны распределенные алгоритмы для вычисления SVD на кластерах стандартных машин. SVD низкого ранга применяется для обнаружения горячих точек на основе пространственно-временных данных, что применимо для обнаружения вспышек заболеваний. Комбинация SVD и SVD высшего порядка также применяется для обнаружения событий в реальном времени из сложных потоков данных (многомерные данные с пространственными и временными измерениями) в эпидемиологическом надзоре. В астродинамике SVD и его варианты используются в качестве опции для определения подходящих направлений маневрирования при проектировании траектории перелета и поддержании орбиты.

Результат анализа 2 × 2 SVD

Одиночные значения матрицы 2 \times 2 могут быть найдены аналитически. Пусть матрица будет

где – комплексные числа, параметризующие матрицу, \mathbf{I} – единичная матрица, а – матрицы Паули. Тогда её два сингулярных значения задаются выражением

Сниженные SVD

В приложениях редко требуется полное сингулярное разложение (SVD), включая полное унитарное разложение нулевого пространства матрицы. Вместо этого часто бывает достаточно (а также быстрее и экономичнее с точки зрения хранения) вычислить сокращенное сингулярное разложение. Для матрицы \mathbf M размера m \times n ранга r можно выделить следующее:

Строченная SVD

Во многих приложениях число r ненулевых сингулярных значений велико, что делает даже компактное SVD непрактичным для вычисления. В таких случаях наименьшие сингулярные значения могут быть усечены, чтобы вычислить только t \ll r ненулевых сингулярных значений. Усеченное SVD больше не является точным разложением исходной матрицы \mathbf{M}, а скорее предоставляет оптимальное матричное приближение низкого ранга \tilde{\mathbf{M}} любой матрицей с фиксированным рангом t, где матрица \mathbf{U}_t имеет размер m \times t, \mathbf{\Sigma}_t имеет размер t \times t и является диагональной, а \mathbf{V}_t^* имеет размер t \times n. Вычисляются только t столбцовых векторов \mathbf{U} и t строковых векторов \mathbf{V}^* , соответствующие t наибольшим сингулярным значениям \mathbf{\Sigma}_t. Это может быть намного быстрее и экономичнее, чем компактное SVD, если t \ll r, но требует совершенно иного набора численных методов. В приложениях, требующих приближения к обобщенной обратной Мур-Пенроуза матрицы \mathbf{M}, представляют интерес наименьшие сингулярные значения \mathbf{M}, которые сложнее вычислить по сравнению с наибольшими. Усеченное SVD используется в латентном семантическом индексировании.

Нормы КИ ФАН

Сумма k наибольших сингулярных значений \mathbf M является матричной нормой, нормой Ky Fan k \mathbf M.

Первая из норм Ky Fan, норма Ky Fan 1, совпадает с операторной нормой \mathbf M как линейного оператора относительно евклидовых норм K^m и K^n. Иными словами, норма Ky Fan 1 является операторной нормой, индуцированной стандартным евклидовым внутренним произведением. По этой причине она также называется операторной 2-нормой. Связь между нормой Ky Fan 1 и сингулярными значениями можно легко проверить. Это справедливо в общем случае для ограниченного оператора \mathbf M на (возможно, бесконечномерном) гильбертовом пространстве.

Однако, в матричном случае, (\mathbf M^* \mathbf M)^{1/2} является нормальной матрицей, и, следовательно, наибольшим собственным значением (\mathbf M^* \mathbf M)^{1/2} является наибольшее сингулярное значение \mathbf M.

Последняя из норм Ky Fan, сумма всех сингулярных значений, является трассовой нормой (также известной как ядерная норма), определяемой (собственные значения \mathbf M^* \mathbf M равны квадратам сингулярных значений).

Неизменная по масштабу SVD

Одиночные значения матрицы \mathbf A определены однозначно и инвариантны относительно левых и/или правых унитарных преобразований \mathbf A. Иными словами, сингулярные значения \mathbf U \mathbf A \mathbf V, где \mathbf U и \mathbf V – унитарные матрицы, равны сингулярным значениям \mathbf A. Это важное свойство для приложений, в которых требуется сохранение евклидовых расстояний и инвариантность относительно вращений. Масштабно-инвариантное сингулярное разложение, или SI SVD, аналогично обычному сингулярному разложению, за исключением того, что его однозначно определенные сингулярные значения инвариантны относительно диагональных преобразований \mathbf A. Иными словами, сингулярные значения \mathbf D \mathbf A \mathbf E, где \mathbf D и \mathbf E – невырожденные диагональные матрицы, равны сингулярным значениям \mathbf A. Это важное свойство для приложений, которым требуется инвариантность к выбору единиц измерения переменных (например, метрической и имперской систем).

Сингулярные значения и компактные операторы

Понятие сингулярных значений и левых/правых сингулярных векторов можно расширить на компактные операторы в гильбертовом пространстве, поскольку они имеют дискретный спектр. Если T компактен, то каждое ненулевое λ в его спектре является собственным значением. Более того, компактный самосопряженный оператор может быть диагонализован по своим собственным векторам. Если \mathbf M компактен, то \mathbf M^* \mathbf M также компактен. Применяя результат диагонализации, унитарное преобразование положительного квадратного корня из T f имеет набор ортонормальных собственных векторов \{e_i\}, соответствующих строго положительным собственным значениям \{\sigma_i\}. Для любого \psi из H,

где ряд сходится в норме на H. Обратите внимание на сходство с выражением в конечномерном случае. \sigma_i называются сингулярными значениями \mathbf M. Множества \{\mathbf U e_i\} (соответственно, \{\mathbf U e_i\}) можно рассматривать как левые сингулярные (соответственно, правые сингулярные) векторы \mathbf M.

Компактные операторы в гильбертовом пространстве являются замыканием операторов конечного ранга в равномерной операторной топологии. Приведенное выше разложение в ряд дает явное представление такого типа. Непосредственным следствием этого является:

Теорема. \mathbf M компактен тогда и только тогда, когда \mathbf M^* \mathbf M компактен.

История

Сингулярное разложение было первоначально разработано дифференциальными геометрами, которые стремились определить, можно ли привести реальную двулинейную форму к другой посредством независимых ортогональных преобразований двух пространств, на которых она действует. Эухенио Белтрами и Камиль Жордан независимо друг от друга, в 1873 и 1874 годах соответственно, обнаружили, что сингулярные значения двулинейных форм, представленных в виде матрицы, образуют полный набор инвариантов для двулинейных форм при ортогональных заменах. Джеймс Джозеф Сильвестр также пришел к сингулярному разложению для вещественных квадратных матриц в 1889 году, по-видимому, независимо от Белтрами и Жордана. Сильвестр назвал сингулярные значения каноническими множителями матрицы \mathbf A. Четвертым математиком, независимо открывшим сингулярное разложение, является Отонн в 1915 году, который пришел к нему через полярное разложение. Первое доказательство сингулярного разложения для прямоугольных и комплексных матриц, по-видимому, было дано Карлом Эккартом и Гейлом Дж. Янгом в 1936 году; они рассматривали его как обобщение преобразования главных осей для эрмитовых матриц. В 1907 году Эрхард Шмидт определил аналог сингулярных значений для интегральных операторов (которые являются компактными при некоторых слабых технических предположениях); по-видимому, он не знал о параллельных исследованиях сингулярных значений конечных матриц. Эта теория была далее развита Эмилем Пикаром в 1910 году, который впервые назвал эти числа сингулярными значениями (или на французском языке – valeurs singulières). Практические методы вычисления сингулярного разложения восходят к работам Когбетлианца в 1954–1955 годах и Хестена в 1958 году, тесно напоминающим алгоритм собственных значений Якоби, использующий плоские или вращения Гивенса. Однако они были заменены методом Джина Голуба и Уильяма Кахана, опубликованным в 1965 году, который использует преобразования Хаусхолдера или отражения. В 1970 году Голуб и Кристиан Райнш опубликовали вариант алгоритма Голуба/Кахана, который до сих пор является наиболее используемым.