Разложение по сингулярным значениям

Матричное разложение

Иллюстрация разложения сингулярных чисел UΣV ^⁎ действительной матрицы M размером 2 × 2 .

• Вверху: действие M , выраженное его влиянием на единичный круг D и два канонических единичных вектора e ₁ и e ₂ .
• Слева: действие V ^⁎ , вращения, на D , e ₁ и e ₂ .
• Внизу: действие Σ , масштабирование по сингулярным значениям σ ₁ по горизонтали и σ ₂ по вертикали.
• Справа: действие U , еще один поворот.

В линейной алгебре сингулярное разложение ( SVD ) — это факторизация действительной или комплексной матрицы во вращение, за которым следует масштабирование, за которым следует еще одно вращение. Оно обобщает собственное разложение квадратной нормальной матрицы с ортонормированным собственным базисом на любую матрицу . Оно связано с полярным разложением . ${\displaystyle m\times n}$

В частности, сингулярное разложение комплексной матрицы ⁠ ⁠ является факторизацией вида , где ⁠ ⁠ является ⁠ ⁠ комплексной унитарной матрицей , является прямоугольной диагональной матрицей с неотрицательными действительными числами на диагонали, ⁠ ⁠ является комплексной унитарной матрицей и является сопряженной транспонированной матрицей ⁠ ⁠ . Такое разложение всегда существует для любой комплексной матрицы. Если ⁠ ⁠ является действительной, то ⁠ ⁠ и ⁠ ⁠ можно гарантировать, что они будут действительными ортогональными матрицами; в таких контекстах SVD часто обозначается ${\displaystyle m\times n}$ ${\displaystyle \mathbf {M} }$ ${\displaystyle \mathbf {M} =\mathbf {U\Sigma V^{*}} ,}$ ${\displaystyle \mathbf {U} }$ ${\displaystyle m\times m}$ ${\displaystyle \mathbf {\Sigma } }$ ${\displaystyle m\times n}$ ${\displaystyle \mathbf {V} }$ ${\displaystyle n\times n}$ ${\displaystyle \mathbf {V} ^{*}}$ ${\displaystyle \mathbf {V} }$ ${\displaystyle \mathbf {M} }$ ${\displaystyle \mathbf {U} }$ ${\displaystyle \mathbf {V} }$ ${\displaystyle \mathbf {U} \mathbf {\Sigma } \mathbf {V} ^{\mathrm {T} }.}$

Диагональные элементы однозначно определяются ⁠ ⁠ и называются сингулярными значениями ⁠ ⁠ . Количество ненулевых сингулярных значений равно рангу ⁠ ⁠ . Столбцы ⁠ ⁠ и столбцы ⁠ ⁠ называются лево-сингулярными векторами и право-сингулярными векторами ⁠ ⁠ , соответственно. Они образуют два набора ортонормированных базисов ⁠ ⁠ и ⁠ ⁠ , и если они отсортированы так, что сингулярные значения со значением ноль находятся в столбцах (или строках) с наибольшими номерами, разложение сингулярных значений можно записать как ${\displaystyle \sigma _{i}=\Sigma _{ii}}$ ${\displaystyle \mathbf {\Sigma } }$ ${\displaystyle \mathbf {M} }$ ${\displaystyle \mathbf {M} }$ ${\displaystyle \mathbf {M} }$ ${\displaystyle \mathbf {U} }$ ${\displaystyle \mathbf {V} }$ ${\displaystyle \mathbf {M} }$ ${\displaystyle \mathbf {u} _{1},\ldots ,\mathbf {u} _{m}}$ ${\displaystyle \mathbf {v} _{1},\ldots ,\mathbf {v} _{n},}$ ${\displaystyle \sigma _{i}}$

$${\displaystyle \mathbf {M} =\sum _{i=1}^{r}\sigma _{i}\mathbf {u} _{i}\mathbf {v} _{i}^{*},}$$

где ранг ⁠ ⁠ ${\displaystyle r\leq \min\{m,n\}}$ ${\displaystyle \mathbf {M} .}$

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

Термин иногда относится к компактному SVD , похожему разложению ⁠ ⁠, ${\displaystyle \mathbf {M} =\mathbf {U\Sigma V} ^{*}}$ в котором ⁠ ⁠ ${\displaystyle \mathbf {\Sigma } }$ является квадратной диагональю размера ⁠ ⁠, ${\displaystyle r\times r,}$ где ⁠ ⁠ ${\displaystyle r\leq \min\{m,n\}}$ — это ранг ⁠ ⁠ ${\displaystyle \mathbf {M} ,}$ и имеет только ненулевые сингулярные значения. В этом варианте ⁠ ⁠ ${\displaystyle \mathbf {U} }$ является ⁠ ⁠ ${\displaystyle m\times r}$ полуунитарной матрицей и является ⁠ ⁠ полуунитарной матрицей , такой что ${\displaystyle \mathbf {V} }$ ${\displaystyle n\times r}$ ${\displaystyle \mathbf {U} ^{*}\mathbf {U} =\mathbf {V} ^{*}\mathbf {V} =\mathbf {I} _{r}.}$

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

Интуитивные интерпретации

Анимированная иллюстрация SVD двумерной действительной матрицы сдвига M. Сначала мы видим единичный диск синего цвета вместе с двумя каноническими единичными векторами . Затем мы видим действия M , которые искажают диск до эллипса . SVD разлагает M на три простых преобразования: начальное вращение V ^⁎ , масштабирование вдоль осей координат и конечное вращение U . Длины σ ₁ и σ ₂ полуосей эллипса являются сингулярными значениями M , а именно Σ _1,1 и Σ _2,2 . ${\displaystyle \mathbf {\Sigma } }$

Визуализация умножения матриц в сингулярном разложении

Вращение, масштабирование координат и отражение

В особом случае, когда ⁠ ⁠ ${\displaystyle \mathbf {M} }$ является ⁠ ⁠ ${\displaystyle m\times m}$ действительной квадратной матрицей , матрицы ⁠ ⁠ ${\displaystyle \mathbf {U} }$ и ⁠ ⁠ ${\displaystyle \mathbf {V} ^{*}}$ также могут быть выбраны действительными ⁠ ⁠ ${\displaystyle m\times m}$ матрицами. В этом случае «унитарный» — то же самое, что и « ортогональный ». Затем, интерпретируя как унитарные матрицы, так и диагональную матрицу, суммированную здесь как ⁠ ⁠ ${\displaystyle \mathbf {A} ,}$ как линейное преобразование ⁠ ⁠ ${\displaystyle \mathbf {x} \mapsto \mathbf {Ax} }$ пространства ⁠ ⁠ ${\displaystyle \mathbf {R} _{m},}$ матрицы ⁠ ⁠ ${\displaystyle \mathbf {U} }$ и ⁠ ⁠ ${\displaystyle \mathbf {V} ^{*}}$ представляют повороты или отражение пространства, в то время как ⁠ ⁠ ${\displaystyle \mathbf {\Sigma } }$ представляет масштабирование каждой координаты ⁠ ⁠ ${\displaystyle \mathbf {x} _{i}}$ на коэффициент ⁠ ⁠ ${\displaystyle \sigma _{i}.}$ Таким образом, разложение SVD разбивает любое линейное преобразование ⁠ ⁠ ${\displaystyle \mathbf {R} ^{m}}$ на композицию трех геометрических преобразований : поворот или отражение ( ⁠ ⁠ ${\displaystyle \mathbf {V} ^{*}}$ ), за которым следует масштабирование по координатам ( ⁠ ⁠ ${\displaystyle \mathbf {\Sigma } }$ ), за которым следует еще один поворот или отражение ( ⁠ ⁠ ${\displaystyle \mathbf {U} }$ ).

В частности, если ⁠ ⁠ ${\displaystyle \mathbf {M} }$ имеет положительный определитель, то ⁠ ⁠ ${\displaystyle \mathbf {U} }$ и ⁠ ⁠ ${\displaystyle \mathbf {V} ^{*}}$ могут быть выбраны как оба вращения с отражениями или как оба вращения без отражений. ^{[ необходима цитата ]} Если определитель отрицательный, ровно один из них будет иметь отражение. Если определитель равен нулю, каждый из них может быть независимо выбран как относящийся к любому типу.

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

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

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

КолонныУиВявляются ортонормированными базисами

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

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

• Первые ⁠ ⁠ ${\displaystyle r}$ столбцы ⁠ ⁠ ${\displaystyle \mathbf {U} }$ являются базисом столбцового пространства ⁠ ${\displaystyle \mathbf {M} }$ ⁠ .
• Последние ⁠ ⁠ ${\displaystyle m-r}$ столбцы ⁠ ⁠ ${\displaystyle \mathbf {U} }$ являются базисом нулевого пространства ⁠ ${\displaystyle \mathbf {M} ^{*}}$ ⁠ .
• Первые ⁠ ⁠ ${\displaystyle r}$ столбцы ⁠ ⁠ ${\displaystyle \mathbf {V} }$ являются базисом пространства столбцов ⁠ ⁠ ${\displaystyle \mathbf {M} ^{*}}$ ( пространства строк ⁠ ⁠ в ${\displaystyle \mathbf {M} }$ действительном случае).
• Последние ⁠ ⁠ ${\displaystyle n-r}$ столбцы ⁠ ⁠ ${\displaystyle \mathbf {V} }$ являются базисом нулевого пространства ⁠ ⁠ ${\displaystyle \mathbf {M} }$ .

Геометрическое значение

Поскольку ⁠ ⁠ ${\displaystyle \mathbf {U} }$ и ⁠ ⁠ ${\displaystyle \mathbf {V} }$ являются унитарными, мы знаем, что столбцы ⁠ ⁠ ${\displaystyle \mathbf {U} _{1},\ldots ,\mathbf {U} _{m}}$ из ⁠ ⁠ ${\displaystyle \mathbf {U} }$ дают ортонормированный базис ⁠ ⁠ , ${\displaystyle K^{m}}$ а столбцы ⁠ ⁠ ${\displaystyle \mathbf {V} _{1},\ldots ,\mathbf {V} _{n}}$ из ⁠ ⁠ ${\displaystyle \mathbf {V} }$ дают ортонормированный базис ⁠ ⁠ ${\displaystyle K^{n}}$ (относительно стандартных скалярных произведений в этих пространствах).

Линейное преобразование

$${\displaystyle T:\left\{{\begin{aligned}K^{n}&\to K^{m}\\x&\mapsto \mathbf {M} x\end{aligned}}\right.}$$

имеет особенно простое описание относительно этих ортонормированных базисов: мы имеем

$${\displaystyle T(\mathbf {V} _{i})=\sigma _{i}\mathbf {U} _{i},\qquad i=1,\ldots ,\min(m,n),}$$

где ⁠ ⁠ — ${\displaystyle \sigma _{i}}$⁠ ⁠ ${\displaystyle i}$ - й диагональный элемент ⁠ ⁠ ${\displaystyle \mathbf {\Sigma } ,}$ и ⁠ ⁠ ${\displaystyle T(\mathbf {V} _{i})=0}$ для ⁠ ⁠ ${\displaystyle i>\min(m,n).}$

Геометрическое содержание теоремы SVD можно, таким образом, резюмировать следующим образом: для каждого линейного отображения ⁠ ⁠ ${\displaystyle T:K^{n}\to K^{m}}$ можно найти ортонормированные базисы ⁠ ⁠ ${\displaystyle K^{n}}$ и ⁠ ⁠ ${\displaystyle K^{m}}$ такие, что ⁠ ⁠ ${\displaystyle T}$ отображает ⁠ ⁠ ${\displaystyle i}$ -й базисный вектор ⁠ ⁠ ${\displaystyle K^{n}}$ в неотрицательное кратное ⁠ ⁠ ${\displaystyle i}$ -го базисного вектора ⁠ ⁠ ${\displaystyle K^{m},}$ и отправляет оставшиеся базисные векторы в ноль. Относительно этих базисов отображение ⁠ ⁠, ${\displaystyle T}$ таким образом, представлено диагональной матрицей с неотрицательными действительными диагональными элементами.

Чтобы получить более наглядное представление о сингулярных значениях и факторизации SVD — по крайней мере, при работе с реальными векторными пространствами — рассмотрим сферу ⁠ ⁠ ${\displaystyle S}$ радиуса один в ⁠ ⁠ ${\displaystyle \mathbf {R} ^{n}.}$ Линейное отображение ⁠ ⁠ ${\displaystyle T}$ отображает эту сферу на эллипсоид в ⁠ ⁠ ${\displaystyle \mathbf {R} ^{m}.}$ Ненулевые сингулярные значения — это просто длины полуосей этого эллипсоида. Особенно когда ⁠ ⁠ ${\displaystyle n=m,}$ и все сингулярные значения различны и не равны нулю, SVD линейного отображения ⁠ ⁠ ${\displaystyle T}$ можно легко проанализировать как последовательность трех последовательных ходов: рассмотрим эллипсоид ⁠ ⁠ ${\displaystyle T(S)}$ и, в частности, его оси; затем рассмотрим направления в ⁠ ⁠, ${\displaystyle \mathbf {R} ^{n}}$ посланные ⁠ ⁠ ${\displaystyle T}$ на эти оси. Эти направления оказываются взаимно ортогональными. Сначала примените изометрию ⁠ ⁠, ${\displaystyle \mathbf {V} ^{*}}$ отправив эти направления осям координат ⁠ ⁠ ${\displaystyle \mathbf {R} ^{n}.}$ На втором ходу примените эндоморфизм ⁠ ⁠, ${\displaystyle \mathbf {D} }$ диагонализованный вдоль осей координат и растягивающийся или сжимающийся в каждом направлении, используя длины полуосей ⁠ ⁠ ${\displaystyle T(S)}$ в качестве коэффициентов растяжения. Затем композиция ⁠ ⁠ ${\displaystyle \mathbf {D} \circ \mathbf {V} ^{*}}$ отправляет единичную сферу на эллипсоид, изометричный ⁠ ⁠ ${\displaystyle T(S).}$ Чтобы определить третий и последний ход, примените изометрию ⁠ ⁠ ${\displaystyle \mathbf {U} }$ к этому эллипсоиду, чтобы получить ⁠ ⁠ ${\displaystyle T(S).}$ Как можно легко проверить, композиция ⁠ ⁠ ${\displaystyle \mathbf {U} \circ \mathbf {D} \circ \mathbf {V} ^{*}}$ совпадает с ⁠ ⁠ ${\displaystyle T.}$

Пример

Рассмотрим матрицу​ ${\displaystyle 4\times 5}$​

$${\displaystyle \mathbf {M} ={\begin{bmatrix}1&0&0&0&2\\0&0&3&0&0\\0&0&0&0&0\\0&2&0&0&0\end{bmatrix}}}$$

Сингулярное разложение этой матрицы задается формулой ⁠ ⁠ ${\displaystyle \mathbf {U} \mathbf {\Sigma } \mathbf {V} ^{*}}$

$${\displaystyle {\begin{aligned}\mathbf {U} &={\begin{bmatrix}\color {Green}0&\color {Blue}-1&\color {Cyan}0&\color {Emerald}0\\\color {Green}-1&\color {Blue}0&\color {Cyan}0&\color {Emerald}0\\\color {Green}0&\color {Blue}0&\color {Cyan}0&\color {Emerald}-1\\\color {Green}0&\color {Blue}0&\color {Cyan}-1&\color {Emerald}0\end{bmatrix}}\\[6pt]\mathbf {\Sigma } &={\begin{bmatrix}3&0&0&0&\color {Gray}{\mathit {0}}\\0&{\sqrt {5}}&0&0&\color {Gray}{\mathit {0}}\\0&0&2&0&\color {Gray}{\mathit {0}}\\0&0&0&\color {Red}\mathbf {0} &\color {Gray}{\mathit {0}}\end{bmatrix}}\\[6pt]\mathbf {V} ^{*}&={\begin{bmatrix}\color {Violet}0&\color {Violet}0&\color {Violet}-1&\color {Violet}0&\color {Violet}0\\\color {Plum}-{\sqrt {0.2}}&\color {Plum}0&\color {Plum}0&\color {Plum}0&\color {Plum}-{\sqrt {0.8}}\\\color {Magenta}0&\color {Magenta}-1&\color {Magenta}0&\color {Magenta}0&\color {Magenta}0\\\color {Orchid}0&\color {Orchid}0&\color {Orchid}0&\color {Orchid}1&\color {Orchid}0\\\color {Purple}-{\sqrt {0.8}}&\color {Purple}0&\color {Purple}0&\color {Purple}0&\color {Purple}{\sqrt {0.2}}\end{bmatrix}}\end{aligned}}}$$

Матрица масштабирования ⁠ ⁠ ${\displaystyle \mathbf {\Sigma } }$ равна нулю вне диагонали (серый курсив), а один диагональный элемент равен нулю (красный полужирный, светло-синий полужирный в темном режиме). Кроме того, поскольку матрицы ⁠ ⁠ ${\displaystyle \mathbf {U} }$ и ⁠ ⁠ ${\displaystyle \mathbf {V} ^{*}}$ являются унитарными , умножение на их соответствующие сопряженные транспонированные матрицы дает единичные матрицы , как показано ниже. В этом случае, поскольку ⁠ ⁠ ${\displaystyle \mathbf {U} }$ и ⁠ ⁠ ${\displaystyle \mathbf {V} ^{*}}$ являются действительными, каждая из них является ортогональной матрицей .

$${\displaystyle {\begin{aligned}\mathbf {U} \mathbf {U} ^{*}&={\begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&1&0\\0&0&0&1\end{bmatrix}}=\mathbf {I} _{4}\\[6pt]\mathbf {V} \mathbf {V} ^{*}&={\begin{bmatrix}1&0&0&0&0\\0&1&0&0&0\\0&0&1&0&0\\0&0&0&1&0\\0&0&0&0&1\end{bmatrix}}=\mathbf {I} _{5}\end{aligned}}}$$

Это конкретное разложение сингулярных значений не уникально. Например, мы можем сохранить ⁠ ⁠ ${\displaystyle \mathbf {U} }$ и ⁠ ⁠ ${\displaystyle \mathbf {\Sigma } }$ тем же самым, но изменить последние две строки ⁠ ⁠ ${\displaystyle \mathbf {V} ^{*}}$ так, что

$${\displaystyle \mathbf {V} ^{*}={\begin{bmatrix}\color {Violet}0&\color {Violet}0&\color {Violet}-1&\color {Violet}0&\color {Violet}0\\\color {Plum}-{\sqrt {0.2}}&\color {Plum}0&\color {Plum}0&\color {Plum}0&\color {Plum}-{\sqrt {0.8}}\\\color {Magenta}0&\color {Magenta}-1&\color {Magenta}0&\color {Magenta}0&\color {Magenta}0\\\color {Orchid}{\sqrt {0.4}}&\color {Orchid}0&\color {Orchid}0&\color {Orchid}{\sqrt {0.5}}&\color {Orchid}-{\sqrt {0.1}}\\\color {Purple}-{\sqrt {0.4}}&\color {Purple}0&\color {Purple}0&\color {Purple}{\sqrt {0.5}}&\color {Purple}{\sqrt {0.1}}\end{bmatrix}}}$$

и получить одинаково допустимое разложение по сингулярным значениям. Поскольку матрица ⁠ ⁠ ${\displaystyle \mathbf {M} }$ имеет ранг 3, она имеет только 3 ненулевых сингулярных значения. При получении произведения ⁠ ⁠ ${\displaystyle \mathbf {U} \mathbf {\Sigma } \mathbf {V} ^{*}}$ последний столбец ⁠ ⁠ ${\displaystyle \mathbf {U} }$ и последние две строки ⁠ ⁠ ${\displaystyle \mathbf {V^{*}} }$ умножаются на ноль, поэтому не оказывают никакого влияния на произведение матриц и могут быть заменены любыми единичными векторами, которые ортогональны первым трем и друг другу.

Компактный SVD, ⁠ ⁠ ${\displaystyle \mathbf {M} =\mathbf {U} _{r}\mathbf {\Sigma } _{r}\mathbf {V} _{r}^{*}}$ , устраняет эти лишние строки, столбцы и сингулярные значения:

$${\displaystyle {\begin{aligned}\mathbf {U} _{r}&={\begin{bmatrix}\color {Green}0&\color {Blue}-1&\color {Cyan}0\\\color {Green}-1&\color {Blue}0&\color {Cyan}0\\\color {Green}0&\color {Blue}0&\color {Cyan}0\\\color {Green}0&\color {Blue}0&\color {Cyan}-1\end{bmatrix}}\\[6pt]\mathbf {\Sigma } _{r}&={\begin{bmatrix}3&0&0\\0&{\sqrt {5}}&0\\0&0&2\end{bmatrix}}\\[6pt]\mathbf {V} _{r}^{*}&={\begin{bmatrix}\color {Violet}0&\color {Violet}0&\color {Violet}-1&\color {Violet}0&\color {Violet}0\\\color {Plum}-{\sqrt {0.2}}&\color {Plum}0&\color {Plum}0&\color {Plum}0&\color {Plum}-{\sqrt {0.8}}\\\color {Magenta}0&\color {Magenta}-1&\color {Magenta}0&\color {Magenta}0&\color {Magenta}0\end{bmatrix}}\end{aligned}}}$$

SVD и спектральное разложение

Сингулярные значения, сингулярные векторы и их связь с SVD

Неотрицательное действительное число ⁠ ⁠ ${\displaystyle \sigma }$ является сингулярным значением для ⁠ ⁠ ${\displaystyle \mathbf {M} }$ тогда и только тогда, когда существуют векторы единичной длины ⁠ ⁠ ${\displaystyle \mathbf {u} }$ в ⁠ ⁠ ${\displaystyle K^{m}}$ и ⁠ ⁠ ${\displaystyle \mathbf {v} }$ в ⁠ ⁠ ${\displaystyle K^{n}}$ такие, что

$${\displaystyle {\begin{aligned}\mathbf {Mv} &=\sigma \mathbf {u} ,\\[3mu]\mathbf {M} ^{*}\mathbf {u} &=\sigma \mathbf {v} .\end{aligned}}}$$

Векторы ⁠ ⁠ ${\displaystyle \mathbf {u} }$ и ⁠ ⁠ ${\displaystyle \mathbf {v} }$ называются левосингулярными и правосингулярными векторами для ⁠ ⁠ ${\displaystyle \sigma ,}$ соответственно.

В любом сингулярном разложении

$${\displaystyle \mathbf {M} =\mathbf {U} \mathbf {\Sigma } \mathbf {V} ^{*}}$$

диагональные элементы ⁠ ⁠ ${\displaystyle \mathbf {\Sigma } }$ равны сингулярным значениям ⁠ ⁠ ${\displaystyle \mathbf {M} .}$ Первые ⁠ ⁠ ${\displaystyle p=\min(m,n)}$ столбцы ⁠ ⁠ ${\displaystyle \mathbf {U} }$ и ⁠ ⁠ являются ${\displaystyle \mathbf {V} }$ , соответственно, лево- и право-сингулярными векторами для соответствующих сингулярных значений. Следовательно, из вышеприведенной теоремы следует, что:

• Матрица имеет не более ⁠ ⁠ ${\displaystyle m\times n}$различных ${\displaystyle \mathbf {M} }$сингулярных значений . ${\displaystyle p}$
• Всегда можно найти унитарный базис ⁠ ⁠ ${\displaystyle \mathbf {U} }$ для ⁠ ⁠ ${\displaystyle K^{m}}$ с подмножеством базисных векторов, охватывающих левые сингулярные векторы каждого сингулярного значения ⁠ ⁠ ${\displaystyle \mathbf {M} .}$
• Всегда можно найти унитарный базис ⁠ ⁠ ${\displaystyle \mathbf {V} }$ для ⁠ ⁠ ${\displaystyle K^{n}}$ с подмножеством базисных векторов, охватывающих правосингулярные векторы каждого сингулярного значения ⁠ ⁠ ${\displaystyle \mathbf {M} .}$

Сингулярное значение, для которого мы можем найти два левых (или правых) сингулярных вектора, которые линейно независимы, называется вырожденным . Если ⁠ ⁠ ${\displaystyle \mathbf {u} _{1}}$ и ⁠ ⁠ ${\displaystyle \mathbf {u} _{2}}$ — два левых сингулярных вектора, которые оба соответствуют сингулярному значению σ, то любая нормализованная линейная комбинация двух векторов также является левосингулярным вектором, соответствующим сингулярному значению σ. Аналогичное утверждение верно для правосингулярных векторов. Количество независимых левых и правосингулярных векторов совпадает, и эти сингулярные векторы появляются в тех же столбцах ⁠ ⁠ ${\displaystyle \mathbf {U} }$ и ⁠ ⁠, ${\displaystyle \mathbf {V} }$ соответствующих диагональным элементам ⁠ ⁠, ${\displaystyle \mathbf {\Sigma } }$ все с тем же значением ⁠ ⁠ ${\displaystyle \sigma .}$

В качестве исключения левые и правые сингулярные векторы сингулярного значения 0 включают все единичные векторы в коядре и ядре , соответственно, ⁠ ⁠ , ${\displaystyle \mathbf {M} ,}$ которые по теореме о ранге–нуле не могут быть одинаковой размерности, если ⁠ ⁠ ${\displaystyle m\neq n.}$ Даже если все сингулярные значения не равны нулю, если ⁠ ⁠ ${\displaystyle m>n}$ то коядро нетривиально, и в этом случае ⁠ ⁠ ${\displaystyle \mathbf {U} }$ дополняется ⁠ ⁠ ${\displaystyle m-n}$ ортогональными векторами из коядра. И наоборот, если ⁠ ⁠ ${\displaystyle m<n,}$ то ⁠ ⁠ ${\displaystyle \mathbf {V} }$ дополняется ⁠ ⁠ ${\displaystyle n-m}$ ортогональными векторами из ядра. Однако, если сингулярное значение ⁠ ⁠ ${\displaystyle 0}$ существует, дополнительные столбцы ⁠ ⁠ ${\displaystyle \mathbf {U} }$ или ⁠ ⁠ ${\displaystyle \mathbf {V} }$ уже появляются как левые или правые сингулярные векторы.

Невырожденные сингулярные значения всегда имеют уникальные лево- и право-сингулярные векторы, с точностью до умножения на единично-фазовый множитель ⁠ ⁠ ${\displaystyle e^{i\varphi }}$ (для действительного случая с точностью до знака). Следовательно, если все сингулярные значения квадратной матрицы ⁠ ⁠ ${\displaystyle \mathbf {M} }$ невырождены и не равны нулю, то ее сингулярное разложение уникально с точностью до умножения столбца ⁠ ⁠ ${\displaystyle \mathbf {U} }$ на единично-фазовый множитель и одновременного умножения соответствующего столбца ⁠ ⁠ ${\displaystyle \mathbf {V} }$ на тот же единично-фазовый множитель. В общем случае SVD уникально с точностью до произвольных унитарных преобразований, применяемых равномерно к векторам-столбцам как ⁠ ⁠ , ${\displaystyle \mathbf {U} }$ так и ⁠ ⁠ , ${\displaystyle \mathbf {V} }$ охватывающим подпространства каждого сингулярного значения, и с точностью до произвольных унитарных преобразований над векторами ⁠ ⁠ ${\displaystyle \mathbf {U} }$ и ⁠ ⁠ , ${\displaystyle \mathbf {V} }$ охватывающими ядро ​​и коядро соответственно ⁠ ⁠ ${\displaystyle \mathbf {M} .}$

Связь с разложением собственных значений

Разложение по сингулярным значениям является очень общим в том смысле, что его можно применить к любой матрице , ${\displaystyle m\times n}$ тогда как разложение по собственным значениям можно применить только к квадратным диагонализируемым матрицам . Тем не менее, эти два разложения связаны.

Если ⁠ ⁠ ${\displaystyle \mathbf {M} }$ имеет SVD ⁠ ⁠, ${\displaystyle \mathbf {M} =\mathbf {U} \mathbf {\Sigma } \mathbf {V} ^{*},}$ то выполняются следующие два соотношения:

$${\displaystyle {\begin{aligned}\mathbf {M} ^{*}\mathbf {M} &=\mathbf {V} \mathbf {\Sigma } ^{*}\mathbf {U} ^{*}\,\mathbf {U} \mathbf {\Sigma } \mathbf {V} ^{*}=\mathbf {V} (\mathbf {\Sigma } ^{*}\mathbf {\Sigma } )\mathbf {V} ^{*},\\[3mu]\mathbf {M} \mathbf {M} ^{*}&=\mathbf {U} \mathbf {\Sigma } \mathbf {V} ^{*}\,\mathbf {V} \mathbf {\Sigma } ^{*}\mathbf {U} ^{*}=\mathbf {U} (\mathbf {\Sigma } \mathbf {\Sigma } ^{*})\mathbf {U} ^{*}.\end{aligned}}}$$

Правые части этих соотношений описывают разложения собственных значений левых частей. Следовательно:

• Столбцы ⁠ ⁠ ${\displaystyle \mathbf {V} }$( называемые правыми сингулярными векторами) являются собственными векторами ⁠ ⁠ ${\displaystyle \mathbf {M} ^{*}\mathbf {M} .}$
• Столбцы ⁠ ⁠ ${\displaystyle \mathbf {U} }$ (называемые левыми сингулярными векторами) являются собственными векторами ⁠ ⁠ ${\displaystyle \mathbf {M} \mathbf {M} ^{*}.}$
• Ненулевые элементы ⁠ ⁠ (ненулевые сингулярные значения) ${\displaystyle \mathbf {\Sigma } }$являются квадратными корнями ненулевых собственных значений ⁠ ⁠ ${\displaystyle \mathbf {M} ^{*}\mathbf {M} }$ или ⁠ ⁠ ${\displaystyle \mathbf {M} \mathbf {M} ^{*}.}$

В частном случае ⁠ ⁠ ${\displaystyle \mathbf {M} }$ будучи нормальной матрицей , и, следовательно, также квадратной, спектральная теорема гарантирует, что она может быть унитарно диагонализирована с использованием базиса собственных векторов , и, таким образом, разложена как ⁠ ⁠ ${\displaystyle \mathbf {M} =\mathbf {U} \mathbf {D} \mathbf {U} ^{*}}$ для некоторой унитарной матрицы ⁠ ⁠ ${\displaystyle \mathbf {U} }$ и диагональной матрицы ⁠ ⁠ ${\displaystyle \mathbf {D} }$ с комплексными элементами ⁠ ⁠ ${\displaystyle \sigma _{i}}$ вдоль диагонали. Когда ⁠ ⁠ ${\displaystyle \mathbf {M} }$ является положительно полуопределенной , ⁠ ⁠ ${\displaystyle \sigma _{i}}$ будут неотрицательными действительными числами, так что разложение ⁠ ⁠ ${\displaystyle \mathbf {M} =\mathbf {U} \mathbf {D} \mathbf {U} ^{*}}$ также является разложением по сингулярным значениям. В противном случае его можно переформулировать как SVD, переместив фазу ⁠ ⁠ ${\displaystyle e^{i\varphi }}$ каждого ⁠ ⁠ ${\displaystyle \sigma _{i}}$ либо в соответствующую ⁠ ⁠ , ${\displaystyle \mathbf {V} _{i}}$ либо ⁠ ⁠ ${\displaystyle \mathbf {U} _{i}.}$ Естественная связь SVD с ненормальными матрицами осуществляется через теорему о полярном разложении : ⁠ ⁠ ${\displaystyle \mathbf {M} =\mathbf {S} \mathbf {R} ,}$ где ⁠ ⁠ ${\displaystyle \mathbf {S} =\mathbf {U} \mathbf {\Sigma } \mathbf {U} ^{*}}$ является положительно полуопределенной и нормальной, а ⁠ ⁠ ${\displaystyle \mathbf {R} =\mathbf {U} \mathbf {V} ^{*}}$ является унитарным.

Таким образом, за исключением положительно полуопределенных матриц, разложение по собственным значениям и SVD матрицы ⁠ ⁠ ${\displaystyle \mathbf {M} ,}$ хотя и связаны, различаются: разложение по собственным значениям ⁠ ⁠ ${\displaystyle {1}}$ где ⁠ ⁠ ${\displaystyle \mathbf {U} }$ не обязательно унитарно и ⁠ ⁠ ${\displaystyle \mathbf {D} }$ не обязательно положительно полуопределено, в то время как SVD ⁠ ⁠ где ${\displaystyle {1}}$ ⁠ ⁠ является ${\displaystyle \mathbf {\Sigma } }$ диагональным и положительно полуопределенным, а ⁠ ⁠ ${\displaystyle \mathbf {U} }$ и ⁠ ⁠ ${\displaystyle \mathbf {V} }$ являются унитарными матрицами, которые не обязательно связаны, за исключением матрицы ⁠ ⁠ ${\displaystyle \mathbf {M} .}$ В то время как только недефектные квадратные матрицы имеют разложение по собственным значениям, любая ⁠ ⁠ ${\displaystyle m\times n}$ матрица имеет SVD.

Применение СВД

Псевдообратный

Сингулярное разложение может быть использовано для вычисления псевдообратной матрицы. Псевдообратная матрица матрицы ⁠ ⁠ ${\displaystyle \mathbf {M} }$ с сингулярным разложением ⁠ ⁠ ${\displaystyle \mathbf {M} =\mathbf {U} \mathbf {\Sigma } \mathbf {V} ^{*}}$ имеет вид

$${\displaystyle \mathbf {M} ^{+}=\mathbf {V} {\boldsymbol {\Sigma }}^{+}\mathbf {U} ^{\ast },}$$

где — псевдообратная матрица , которая формируется путем замены каждого ненулевого диагонального элемента на его обратную величину и транспонирования полученной матрицы. Псевдообратная матрица — один из способов решения линейных задач наименьших квадратов . ${\displaystyle {\boldsymbol {\Sigma }}^{+}}$ ${\displaystyle {\boldsymbol {\Sigma }}}$

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

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

Минимизация методом наименьших квадратов

Задача наименьших квадратов ищет вектор ⁠ ⁠, ${\displaystyle \mathbf {x} }$ который минимизирует 2-норму вектора ⁠ ⁠ ${\displaystyle \mathbf {A} \mathbf {x} }$ при ограничении Решением оказывается право-сингулярный вектор ⁠ ⁠, соответствующий наименьшему сингулярному значению. ${\displaystyle \|\mathbf {x} \|=1.}$ ${\displaystyle \mathbf {A} }$

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

Другое применение SVD заключается в том, что оно обеспечивает явное представление диапазона и нулевого пространства матрицы ⁠ ⁠ ${\displaystyle \mathbf {M} .}$ Правые сингулярные векторы, соответствующие исчезающим сингулярным значениям ⁠ ⁠, ${\displaystyle \mathbf {M} }$ охватывают нулевое пространство ⁠ ⁠, ${\displaystyle \mathbf {M} }$ а левые сингулярные векторы, соответствующие ненулевым сингулярным значениям ⁠ ⁠, ${\displaystyle \mathbf {M} }$ охватывают диапазон ⁠ ⁠ ${\displaystyle \mathbf {M} .}$ Например, в приведенном выше примере нулевое пространство охватывается последней строкой ⁠ ⁠, ${\displaystyle \mathbf {V} ^{*}}$ а диапазон охватывается первыми тремя столбцами ⁠ ⁠ ${\displaystyle \mathbf {U} .}$

Как следствие, ранг ⁠ ⁠ ${\displaystyle \mathbf {M} }$ равен числу ненулевых сингулярных значений, что равно числу ненулевых диагональных элементов в . В числовой линейной алгебре сингулярные значения могут использоваться для определения эффективного ранга матрицы, поскольку ошибка округления может привести к небольшим , но ненулевым сингулярным значениям в матрице с дефицитом ранга. Предполагается, что сингулярные значения за пределами значительного промежутка численно эквивалентны нулю. ${\displaystyle \mathbf {\Sigma } }$

Низкоранговая аппроксимация матрицы

Некоторые практические приложения требуют решения задачи аппроксимации матрицы ⁠ ⁠ ${\displaystyle \mathbf {M} }$ другой матрицей , называемой усеченной, которая имеет определенный ранг ⁠ ⁠ . В случае, если аппроксимация основана на минимизации нормы Фробениуса разности между ⁠ ⁠ и ⁠ ⁠ при ограничении, что оказывается, что решение дается SVD ⁠ ⁠ а именно ${\displaystyle {\tilde {\mathbf {M} }}}$ ${\displaystyle r}$ ${\displaystyle \mathbf {M} }$ ${\displaystyle {\tilde {\mathbf {M} }}}$ ${\displaystyle \operatorname {rank} {\bigl (}{\tilde {\mathbf {M} }}{\bigr )}=r,}$ ${\displaystyle \mathbf {M} ,}$

$${\displaystyle {\tilde {\mathbf {M} }}=\mathbf {U} {\tilde {\mathbf {\Sigma } }}\mathbf {V} ^{*},}$$

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

Разборные модели

SVD можно рассматривать как разложение матрицы на взвешенную, упорядоченную сумму разделимых матриц. Под разделимой мы подразумеваем, что матрица ⁠ ⁠ ${\displaystyle \mathbf {A} }$ может быть записана как внешнее произведение двух векторов ⁠ ⁠ ${\displaystyle \mathbf {A} =\mathbf {u} \otimes \mathbf {v} ,}$ или, в координатах, ⁠ ⁠ ${\displaystyle A_{ij}=u_{i}v_{j}.}$ В частности, матрица ⁠ ⁠ ${\displaystyle \mathbf {M} }$ может быть разложена как,

$${\displaystyle \mathbf {M} =\sum _{i}\mathbf {A} _{i}=\sum _{i}\sigma _{i}\mathbf {U} _{i}\otimes \mathbf {V} _{i}.}$$

Здесь ⁠ ⁠ ${\displaystyle \mathbf {U} _{i}}$ и ⁠ ⁠ ${\displaystyle \mathbf {V} _{i}}$ являются ⁠ ⁠ ${\displaystyle i}$ -ыми столбцами соответствующих матриц SVD, ⁠ ⁠ ${\displaystyle \sigma _{i}}$ являются упорядоченными сингулярными значениями, и каждое ⁠ ⁠ ${\displaystyle \mathbf {A} _{i}}$ является разделимым. SVD можно использовать для нахождения разложения фильтра обработки изображений на разделимые горизонтальные и вертикальные фильтры. Обратите внимание, что количество ненулевых ⁠ ⁠ ${\displaystyle \sigma _{i}}$ в точности равно рангу матрицы. ^{[ необходима цитата ]} Разделимые модели часто возникают в биологических системах, и факторизация SVD полезна для анализа таких систем. Например, некоторые рецептивные поля простых клеток зрительной области V1 могут быть хорошо описаны ^[1] фильтром Габора в пространственной области, умноженным на функцию модуляции во временной области. Таким образом, учитывая линейный фильтр, оцененный, например, через обратную корреляцию , можно перестроить два пространственных измерения в одно измерение, тем самым получив двумерный фильтр (пространство, время), который можно разложить с помощью SVD. Первый столбец ⁠ ⁠ ${\displaystyle \mathbf {U} }$ в факторизации SVD тогда является Габором, в то время как первый столбец ⁠ ⁠ ${\displaystyle \mathbf {V} }$ представляет собой модуляцию времени (или наоборот). Затем можно определить индекс разделимости

$${\displaystyle \alpha ={\frac {\sigma _{1}^{2}}{\sum _{i}\sigma _{i}^{2}}},}$$

что является долей мощности в матрице M, которая учитывается первой разделимой матрицей в разложении. ^[2]

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

Можно использовать SVD квадратной матрицы ⁠ ⁠ ${\displaystyle \mathbf {A} }$ для определения ортогональной матрицы ⁠ ⁠, ${\displaystyle \mathbf {O} }$ ближайшей к ⁠ ⁠ ${\displaystyle \mathbf {A} .}$ Близость соответствия измеряется нормой Фробениуса ⁠ ⁠ Решением ${\displaystyle \mathbf {O} -\mathbf {A} .}$ является произведение ⁠ ⁠ ${\displaystyle \mathbf {U} \mathbf {V} ^{*}.}$^[3] Это интуитивно имеет смысл, поскольку ортогональная матрица имела бы разложение ⁠ ⁠ ${\displaystyle \mathbf {U} \mathbf {I} \mathbf {V} ^{*}}$ где ⁠ ⁠ ${\displaystyle \mathbf {I} }$ — единичная матрица, так что если ⁠ ⁠ ${\displaystyle \mathbf {A} =\mathbf {U} \mathbf {\Sigma } \mathbf {V} ^{*}}$ то произведение ⁠ ⁠ ${\displaystyle \mathbf {A} =\mathbf {U} \mathbf {V} ^{*}}$ равнозначно замене сингулярных значений на единицы. Эквивалентно, решением является унитарная матрица ⁠ ⁠ ${\displaystyle \mathbf {R} =\mathbf {U} \mathbf {V} ^{*}}$ полярного разложения в любом порядке растяжения и вращения, как описано выше. ${\displaystyle \mathbf {M} =\mathbf {R} \mathbf {P} =\mathbf {P} '\mathbf {R} }$

Похожая задача, имеющая интересное применение в анализе формы , — это ортогональная задача Прокруста , которая состоит в нахождении ортогональной матрицы ⁠ ⁠, ${\displaystyle \mathbf {O} }$ которая наиболее точно отображает ⁠ ⁠ ${\displaystyle \mathbf {A} }$ в ⁠ ⁠ ${\displaystyle \mathbf {B} .}$ В частности,

$${\displaystyle \mathbf {O} ={\underset {\Omega }{\operatorname {argmin} }}\|\mathbf {A} {\boldsymbol {\Omega }}-\mathbf {B} \|_{F}\quad {\text{subject to}}\quad {\boldsymbol {\Omega }}^{\operatorname {T} }{\boldsymbol {\Omega }}=\mathbf {I} ,}$$

где обозначает норму Фробениуса. ${\displaystyle \|\cdot \|_{F}}$

Эта задача эквивалентна нахождению ближайшей ортогональной матрицы к заданной матрице . ${\displaystyle \mathbf {M} =\mathbf {A} ^{\operatorname {T} }\mathbf {B} }$

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

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

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

SVD и псевдообратное преобразование успешно применяются для обработки сигналов ^[4] , обработки изображений ^[5] и больших данных (например, при обработке геномных сигналов). ^{[6] [7] [8] [9]}

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

SVD также широко применяется для изучения линейных обратных задач и полезен при анализе методов регуляризации, таких как метод Тихонова . Он широко используется в статистике, где он связан с анализом главных компонент и анализом соответствий , а также в обработке сигналов и распознавании образов . Он также используется в модальном анализе только на выходе , где немасштабированные формы мод могут быть определены из сингулярных векторов. Еще одно применение — это скрытое семантическое индексирование в обработке текстов на естественном языке.

В общем численном вычислении, включающем линейные или линеаризованные системы, существует универсальная константа, которая характеризует регулярность или сингулярность проблемы, которая является «числом состояния» системы . Она часто контролирует частоту ошибок или скорость сходимости заданной вычислительной схемы в таких системах. ^{[10] [11]} ${\displaystyle \kappa :=\sigma _{\text{max}}/\sigma _{\text{min}}}$

SVD также играет важную роль в области квантовой информации , в форме, часто называемой разложением Шмидта . С его помощью состояния двух квантовых систем естественным образом разлагаются, обеспечивая необходимое и достаточное условие для их запутывания : если ранг матрицы больше единицы. ${\displaystyle \mathbf {\Sigma } }$

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

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

Интересно, что SVD использовался для улучшения моделирования формы гравитационных волн с помощью наземного гравитационно-волнового интерферометра aLIGO. ^[13] SVD может помочь повысить точность и скорость генерации формы волн для поддержки поиска гравитационных волн и обновления двух различных моделей формы волн.

Разложение по сингулярным значениям используется в рекомендательных системах для прогнозирования оценок товаров людьми. ^[14] Распределенные алгоритмы были разработаны для расчета SVD на кластерах товарных машин. ^[15]

Низкоранговый SVD применялся для обнаружения очагов в пространственно-временных данных с применением к обнаружению вспышек заболеваний . ^[16] Сочетание SVD и SVD более высокого порядка также применялось для обнаружения событий в реальном времени в сложных потоках данных (многомерные данные с пространственными и временными измерениями) при наблюдении за заболеваниями . ^[17]

В астродинамике СВД и его варианты используются в качестве опции для определения подходящих направлений маневра при проектировании траектории перехода ^[18] и удержании орбитальной станции ^[19] .

Доказательство существования

Собственное значение ⁠ ⁠ ${\displaystyle \lambda }$ матрицы ⁠ ⁠ характеризуется ${\displaystyle \mathbf {M} }$ алгебраическим соотношением ⁠ ⁠ ${\displaystyle \mathbf {M} \mathbf {u} =\lambda \mathbf {u} .}$ Когда ⁠ ⁠ ${\displaystyle \mathbf {M} }$ является эрмитовым , вариационная характеристика также доступна. Пусть ⁠ ⁠ ${\displaystyle \mathbf {M} }$ будет действительной ⁠ ⁠ ${\displaystyle n\times n}$ симметричной матрицей . Определим

$${\displaystyle f:\left\{{\begin{aligned}\mathbb {R} ^{n}&\to \mathbb {R} \\\mathbf {x} &\mapsto \mathbf {x} ^{\operatorname {T} }\mathbf {M} \mathbf {x} \end{aligned}}\right.}$$

По теореме об экстремальных значениях эта непрерывная функция достигает максимума в некоторой точке ⁠ ⁠ ${\displaystyle \mathbf {u} }$ при ограничении единичной сферой. По теореме о множителях Лагранжа ⁠ ⁠ обязательно удовлетворяет ${\displaystyle \{\|\mathbf {x} \|=1\}.}$ ${\displaystyle \mathbf {u} }$

$${\displaystyle \nabla \mathbf {u} ^{\operatorname {T} }\mathbf {M} \mathbf {u} -\lambda \cdot \nabla \mathbf {u} ^{\operatorname {T} }\mathbf {u} =0}$$

для некоторого действительного числа ⁠ ⁠ ${\displaystyle \lambda .}$ Символ набла, ⁠ ⁠ ${\displaystyle \nabla }$ , является оператором del (дифференцирование по ⁠ ⁠ ${\displaystyle \mathbf {x} }$ ). Используя симметрию ⁠ ⁠ , ${\displaystyle \mathbf {M} }$ получаем

$${\displaystyle \nabla \mathbf {x} ^{\operatorname {T} }\mathbf {M} \mathbf {x} -\lambda \cdot \nabla \mathbf {x} ^{\operatorname {T} }\mathbf {x} =2(\mathbf {M} -\lambda \mathbf {I} )\mathbf {x} .}$$

Следовательно ⁠ ⁠ ${\displaystyle \mathbf {M} \mathbf {u} =\lambda \mathbf {u} ,}$ so ⁠ ⁠ ${\displaystyle \mathbf {u} }$ является собственным вектором единичной длины ⁠ ⁠ ${\displaystyle \mathbf {M} .}$ Для каждого собственного вектора единичной длины ⁠ ⁠ ${\displaystyle \mathbf {v} }$⁠ ⁠ ${\displaystyle \mathbf {M} }$ его собственное значение равно ⁠ ⁠ so ${\displaystyle f(\mathbf {v} ),}$ ⁠ ⁠ является ${\displaystyle \lambda }$ наибольшим собственным значением ⁠ ⁠ ${\displaystyle \mathbf {M} .}$ Такое же вычисление, выполненное для ортогонального дополнения ⁠ ⁠, ${\displaystyle \mathbf {u} }$ дает следующее наибольшее собственное значение и т. д. Комплексный эрмитов случай аналогичен; существует ⁠ ⁠ ${\displaystyle f(\mathbf {x} )=\mathbf {x} ^{*}\mathbf {M} \mathbf {x} }$ действительная функция ⁠ ⁠ ${\displaystyle 2n}$ действительных переменных.

Сингулярные значения похожи тем, что их можно описать алгебраически или из вариационных принципов. Хотя, в отличие от случая собственных значений, эрмитовость или симметрия ⁠ ⁠ ${\displaystyle \mathbf {M} }$ больше не требуется.

В этом разделе приводятся два аргумента в пользу существования сингулярного разложения.

На основе спектральной теоремы

Пусть будет ⁠ ⁠ комплексной матрицей. Поскольку является положительно полуопределенной и эрмитовой, по спектральной теореме существует ⁠ ⁠ унитарная матрица такая, что ${\displaystyle \mathbf {M} }$ ${\displaystyle m\times n}$ ${\displaystyle \mathbf {M} ^{*}\mathbf {M} }$ ${\displaystyle n\times n}$ ${\displaystyle \mathbf {V} }$

$${\displaystyle \mathbf {V} ^{*}\mathbf {M} ^{*}\mathbf {M} \mathbf {V} ={\bar {\mathbf {D} }}={\begin{bmatrix}\mathbf {D} &0\\0&0\end{bmatrix}},}$$

где диагональна и положительно определена, размерности , с числом ненулевых собственных значений (что можно показать для проверки ). Обратите внимание, что здесь по определению является матрицей, -й столбец которой является -м собственным вектором , соответствующим собственному значению . Более того, -й столбец , для , является собственным вектором с собственным значением . Это можно выразить, записав как , где столбцы и , следовательно, содержат собственные векторы , соответствующие ненулевым и нулевым собственным значениям соответственно. Используя эту переписывание , уравнение становится: ${\displaystyle \mathbf {D} }$ ${\displaystyle \ell \times \ell }$ ${\displaystyle \ell }$ ${\displaystyle \mathbf {M} ^{*}\mathbf {M} }$ ${\displaystyle \ell \leq \min(n,m)}$ ${\displaystyle \mathbf {V} }$ ${\displaystyle i}$ ${\displaystyle i}$ ${\displaystyle \mathbf {M} ^{*}\mathbf {M} }$ ${\displaystyle {\bar {\mathbf {D} }}_{ii}}$ ${\displaystyle j}$ ${\displaystyle \mathbf {V} }$ ${\displaystyle j>\ell }$ ${\displaystyle \mathbf {M} ^{*}\mathbf {M} }$ ${\displaystyle {\bar {\mathbf {D} }}_{jj}=0}$ ${\displaystyle \mathbf {V} }$ ${\displaystyle \mathbf {V} ={\begin{bmatrix}\mathbf {V} _{1}&\mathbf {V} _{2}\end{bmatrix}}}$ ${\displaystyle \mathbf {V} _{1}}$ ${\displaystyle \mathbf {V} _{2}}$ ${\displaystyle \mathbf {M} ^{*}\mathbf {M} }$ ${\displaystyle \mathbf {V} }$

$${\displaystyle {\begin{bmatrix}\mathbf {V} _{1}^{*}\\\mathbf {V} _{2}^{*}\end{bmatrix}}\mathbf {M} ^{*}\mathbf {M} \,{\begin{bmatrix}\mathbf {V} _{1}&\!\!\mathbf {V} _{2}\end{bmatrix}}={\begin{bmatrix}\mathbf {V} _{1}^{*}\mathbf {M} ^{*}\mathbf {M} \mathbf {V} _{1}&\mathbf {V} _{1}^{*}\mathbf {M} ^{*}\mathbf {M} \mathbf {V} _{2}\\\mathbf {V} _{2}^{*}\mathbf {M} ^{*}\mathbf {M} \mathbf {V} _{1}&\mathbf {V} _{2}^{*}\mathbf {M} ^{*}\mathbf {M} \mathbf {V} _{2}\end{bmatrix}}={\begin{bmatrix}\mathbf {D} &0\\0&0\end{bmatrix}}.}$$

Это подразумевает, что

$${\displaystyle \mathbf {V} _{1}^{*}\mathbf {M} ^{*}\mathbf {M} \mathbf {V} _{1}=\mathbf {D} ,\quad \mathbf {V} _{2}^{*}\mathbf {M} ^{*}\mathbf {M} \mathbf {V} _{2}=\mathbf {0} .}$$

Более того, второе уравнение подразумевает . ^[20] Наконец, унитарность переводится, в терминах и , в следующие условия: ${\displaystyle \mathbf {M} \mathbf {V} _{2}=\mathbf {0} }$ ${\displaystyle \mathbf {V} }$ ${\displaystyle \mathbf {V} _{1}}$ ${\displaystyle \mathbf {V} _{2}}$

$${\displaystyle {\begin{aligned}\mathbf {V} _{1}^{*}\mathbf {V} _{1}&=\mathbf {I} _{1},\\\mathbf {V} _{2}^{*}\mathbf {V} _{2}&=\mathbf {I} _{2},\\\mathbf {V} _{1}\mathbf {V} _{1}^{*}+\mathbf {V} _{2}\mathbf {V} _{2}^{*}&=\mathbf {I} _{12},\end{aligned}}}$$

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

Давайте теперь определим

$${\displaystyle \mathbf {U} _{1}=\mathbf {M} \mathbf {V} _{1}\mathbf {D} ^{-{\frac {1}{2}}}.}$$

Затем,

$${\displaystyle \mathbf {U} _{1}\mathbf {D} ^{\frac {1}{2}}\mathbf {V} _{1}^{*}=\mathbf {M} \mathbf {V} _{1}\mathbf {D} ^{-{\frac {1}{2}}}\mathbf {D} ^{\frac {1}{2}}\mathbf {V} _{1}^{*}=\mathbf {M} (\mathbf {I} -\mathbf {V} _{2}\mathbf {V} _{2}^{*})=\mathbf {M} -(\mathbf {M} \mathbf {V} _{2})\mathbf {V} _{2}^{*}=\mathbf {M} ,}$$

поскольку Это также можно рассматривать как непосредственное следствие того факта, что . Это эквивалентно наблюдению, что если — набор собственных векторов , соответствующих неисчезающим собственным значениям , то — набор ортогональных векторов, а — (как правило, не полный) набор ортонормированных векторов. Это соответствует матричному формализму, использованному выше, обозначающему матрицу , столбцы которой , матрицу , столбцы которой являются собственными векторами , с исчезающим собственным значением, и матрицу , столбцы которой являются векторами . ${\displaystyle \mathbf {M} \mathbf {V} _{2}=\mathbf {0} .}$ ${\displaystyle \mathbf {M} \mathbf {V} _{1}\mathbf {V} _{1}^{*}=\mathbf {M} }$ ${\displaystyle \{{\boldsymbol {v}}_{i}\}_{i=1}^{\ell }}$ ${\displaystyle \mathbf {M} ^{*}\mathbf {M} }$ ${\displaystyle \{\lambda _{i}\}_{i=1}^{\ell }}$ ${\displaystyle \{\mathbf {M} {\boldsymbol {v}}_{i}\}_{i=1}^{\ell }}$ ${\displaystyle {\bigl \{}\lambda _{i}^{-1/2}\mathbf {M} {\boldsymbol {v}}_{i}{\bigr \}}{\vphantom {|}}_{i=1}^{\ell }}$ ${\displaystyle \mathbf {V} _{1}}$ ${\displaystyle \{{\boldsymbol {v}}_{i}\}_{i=1}^{\ell }}$ ${\displaystyle \mathbf {V} _{2}}$ ${\displaystyle \mathbf {M} ^{*}\mathbf {M} }$ ${\displaystyle \mathbf {U} _{1}}$ ${\displaystyle {\bigl \{}\lambda _{i}^{-1/2}\mathbf {M} {\boldsymbol {v}}_{i}{\bigr \}}{\vphantom {|}}_{i=1}^{\ell }}$

Мы видим, что это почти желаемый результат, за исключением того, что и в общем случае не являются унитарными, поскольку они могут не быть квадратными. Однако мы знаем, что число строк не меньше числа столбцов, поскольку размерность не больше и . Кроме того, поскольку ${\displaystyle \mathbf {U} _{1}}$ ${\displaystyle \mathbf {V} _{1}}$ ${\displaystyle \mathbf {U} _{1}}$ ${\displaystyle \mathbf {D} }$ ${\displaystyle m}$ ${\displaystyle n}$

$${\displaystyle \mathbf {U} _{1}^{*}\mathbf {U} _{1}=\mathbf {D} ^{-{\frac {1}{2}}}\mathbf {V} _{1}^{*}\mathbf {M} ^{*}\mathbf {M} \mathbf {V} _{1}\mathbf {D} ^{-{\frac {1}{2}}}=\mathbf {D} ^{-{\frac {1}{2}}}\mathbf {D} \mathbf {D} ^{-{\frac {1}{2}}}=\mathbf {I_{1}} ,}$$

столбцы в ортонормальны и могут быть расширены до ортонормального базиса. Это означает, что мы можем выбрать такой, который является унитарным. ${\displaystyle \mathbf {U} _{1}}$ ${\displaystyle \mathbf {U} _{2}}$ ${\displaystyle \mathbf {U} ={\begin{bmatrix}\mathbf {U} _{1}&\mathbf {U} _{2}\end{bmatrix}}}$

Для ⁠ ⁠ ${\displaystyle \mathbf {V} _{1}}$ у нас уже есть ⁠ ⁠ ${\displaystyle \mathbf {V} _{2}}$ сделать его унитарным. Теперь, определим

$${\displaystyle \mathbf {\Sigma } ={\begin{bmatrix}{\begin{bmatrix}\mathbf {D} ^{\frac {1}{2}}&0\\0&0\end{bmatrix}}\\0\end{bmatrix}},}$$

где лишние нулевые строки добавляются или удаляются, чтобы сделать количество нулевых строк равным количеству столбцов ⁠ ⁠ ${\displaystyle \mathbf {U} _{2},}$ и, следовательно, общие размеры равными . Тогда ${\displaystyle \mathbf {\Sigma } }$ ${\displaystyle m\times n}$

$${\displaystyle {\begin{bmatrix}\mathbf {U} _{1}&\mathbf {U} _{2}\end{bmatrix}}{\begin{bmatrix}{\begin{bmatrix}\mathbf {} D^{\frac {1}{2}}&0\\0&0\end{bmatrix}}\\0\end{bmatrix}}{\begin{bmatrix}\mathbf {V} _{1}&\mathbf {V} _{2}\end{bmatrix}}^{*}={\begin{bmatrix}\mathbf {U} _{1}&\mathbf {U} _{2}\end{bmatrix}}{\begin{bmatrix}\mathbf {D} ^{\frac {1}{2}}\mathbf {V} _{1}^{*}\\0\end{bmatrix}}=\mathbf {U} _{1}\mathbf {D} ^{\frac {1}{2}}\mathbf {V} _{1}^{*}=\mathbf {M} ,}$$

что является желаемым результатом:

$${\displaystyle \mathbf {M} =\mathbf {U} \mathbf {\Sigma } \mathbf {V} ^{*}.}$$

Обратите внимание, что аргумент можно было бы начать с диагонализации ⁠ ⁠, ${\displaystyle \mathbf {M} \mathbf {M} ^{*}}$ а не ⁠ ⁠ ${\displaystyle \mathbf {M} ^{*}\mathbf {M} }$ (это напрямую показывает, что ⁠ ⁠ ${\displaystyle \mathbf {M} \mathbf {M} ^{*}}$ и ⁠ ⁠ ${\displaystyle \mathbf {M} ^{*}\mathbf {M} }$ имеют одинаковые ненулевые собственные значения).

На основе вариационной характеристики

Сингулярные значения также можно охарактеризовать как максимумы ⁠ ⁠ , ${\displaystyle \mathbf {u} ^{\mathrm {T} }\mathbf {M} \mathbf {v} ,}$ рассматриваемые как функции ⁠ ⁠ ${\displaystyle \mathbf {U} }$ и ⁠ ⁠ ${\displaystyle \mathbf {V} ,}$ по определенным подпространствам. Сингулярные векторы — это значения ⁠ ⁠ ${\displaystyle \mathbf {U} }$ и ⁠ ⁠ , ${\displaystyle \mathbf {V} }$ где достигаются эти максимумы.

Пусть ⁠ ⁠ ${\displaystyle \mathbf {M} }$ обозначает ⁠ ⁠ ${\displaystyle m\times n}$ матрицу с действительными элементами. Пусть ⁠ ⁠ ${\displaystyle S^{k-1}}$ будет единичной -сферой в , и определите ${\displaystyle (k-1)}$ ${\displaystyle \mathbb {R} ^{k}}$ ${\displaystyle \sigma (\mathbf {u} ,\mathbf {v} )=\mathbf {u} ^{\operatorname {T} }\mathbf {M} \mathbf {v} ,}$ ${\displaystyle \mathbf {u} \in S^{m-1},}$ ${\displaystyle \mathbf {v} \in S^{n-1}.}$

Рассмотрим функцию ⁠ ⁠ ${\displaystyle \sigma }$ ограниченную ⁠ ⁠ ${\displaystyle S^{m-1}\times S^{n-1}.}$ Поскольку и ⁠ ⁠ ${\displaystyle S^{m-1}}$ и ⁠ ⁠ ${\displaystyle S^{n-1}}$ являются компактными множествами, их произведение также компактно. Более того, поскольку ⁠ ⁠ ${\displaystyle \sigma }$ непрерывно, оно достигает наибольшего значения по крайней мере для одной пары векторов ⁠ ⁠ ${\displaystyle \mathbf {u} }$ в ⁠ ⁠ ${\displaystyle S^{m-1}}$ и ⁠ ⁠ ${\displaystyle \mathbf {v} }$ в ⁠ ⁠ ${\displaystyle S^{n-1}.}$ Это наибольшее значение обозначается ⁠ ⁠, ${\displaystyle \sigma _{1}}$ а соответствующие векторы обозначаются ⁠ ⁠ ${\displaystyle \mathbf {u} _{1}}$ и ⁠ ⁠ ${\displaystyle \mathbf {v} _{1}.}$ Поскольку ⁠ ⁠ ${\displaystyle \sigma _{1}}$ является наибольшим значением ⁠ ⁠, ${\displaystyle \sigma (\mathbf {u} ,\mathbf {v} )}$ оно должно быть неотрицательным. Если бы оно было отрицательным, изменение знака либо ⁠ ⁠, ${\displaystyle \mathbf {u} _{1}}$ либо ⁠ ⁠ ${\displaystyle \mathbf {v} _{1}}$ сделало бы его положительным и, следовательно, большим.

Утверждение. ⁠ ⁠ ${\displaystyle \mathbf {u} _{1}}$ и ⁠ ⁠ ${\displaystyle \mathbf {v} _{1}}$ — лево- и право-сингулярные векторы ⁠ ⁠ ${\displaystyle \mathbf {M} }$ с соответствующим сингулярным значением ⁠ ⁠ ${\displaystyle \sigma _{1}.}$

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

$${\displaystyle \nabla \sigma =\nabla \mathbf {u} ^{\operatorname {T} }\mathbf {M} \mathbf {v} -\lambda _{1}\cdot \nabla \mathbf {u} ^{\operatorname {T} }\mathbf {u} -\lambda _{2}\cdot \nabla \mathbf {v} ^{\operatorname {T} }\mathbf {v} }$$

После некоторой алгебры это становится

$${\displaystyle {\begin{aligned}\mathbf {M} \mathbf {v} _{1}&=2\lambda _{1}\mathbf {u} _{1}+0,\\\mathbf {M} ^{\operatorname {T} }\mathbf {u} _{1}&=0+2\lambda _{2}\mathbf {v} _{1}.\end{aligned}}}$$

Умножая первое уравнение слева на ⁠ ⁠ ${\displaystyle \mathbf {u} _{1}^{\textrm {T}}}$ и второе уравнение слева на ⁠ ⁠ ${\displaystyle \mathbf {v} _{1}^{\textrm {T}}}$ и учитывая , получаем ${\displaystyle \|\mathbf {u} \|=\|\mathbf {v} \|=1}$

$${\displaystyle \sigma _{1}=2\lambda _{1}=2\lambda _{2}.}$$

Подставляя это в пару уравнений выше, мы имеем

$${\displaystyle {\begin{aligned}\mathbf {M} \mathbf {v} _{1}&=\sigma _{1}\mathbf {u} _{1},\\\mathbf {M} ^{\operatorname {T} }\mathbf {u} _{1}&=\sigma _{1}\mathbf {v} _{1}.\end{aligned}}}$$

Это доказывает утверждение.

Больше сингулярных векторов и сингулярных значений можно найти, максимизируя ⁠ ⁠ ${\displaystyle \sigma (\mathbf {u} ,\mathbf {v} )}$ по нормализованным ⁠ ⁠ ${\displaystyle \mathbf {u} }$ и ⁠ ⁠ , ${\displaystyle \mathbf {v} }$ которые ортогональны ⁠ ⁠ ${\displaystyle \mathbf {u} _{1}}$ и ⁠ ⁠ ${\displaystyle \mathbf {v} _{1},}$ соответственно.

Переход от действительного числа к комплексному аналогичен случаю собственных значений.

Расчет СВД

Односторонний алгоритм Якоби

Односторонний алгоритм Якоби — это итеративный алгоритм, ^[21] где матрица итеративно преобразуется в матрицу с ортогональными столбцами. Элементарная итерация задается как вращение Якоби ,

$${\displaystyle M\leftarrow MJ(p,q,\theta ),}$$

где угол матрицы поворота Якоби выбирается таким образом, чтобы после поворота столбцы с номерами и стали ортогональными. Индексы циклически просматриваются, , где - число столбцов. ${\displaystyle \theta }$ ${\displaystyle J(p,q,\theta )}$ ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle (p,q)}$ ${\displaystyle (p=1\dots m,q=p+1\dots m)}$ ${\displaystyle m}$

После сходимости алгоритма сингулярное разложение восстанавливается следующим образом: матрица представляет собой накопление матриц вращения Якоби, матрица задается путем нормализации столбцов преобразованной матрицы , а сингулярные значения задаются как нормы столбцов преобразованной матрицы . ${\displaystyle M=USV^{T}}$ ${\displaystyle V}$ ${\displaystyle U}$ ${\displaystyle M}$ ${\displaystyle M}$

Двусторонний алгоритм Якоби

Двусторонний алгоритм Jacobi SVD — обобщение алгоритма Jacobi eigenvalue — это итеративный алгоритм, в котором квадратная матрица итеративно преобразуется в диагональную матрицу. Если матрица не квадратная, сначала выполняется QR-разложение , а затем алгоритм применяется к матрице. Элементарная итерация обнуляет пару недиагональных элементов, сначала применяя вращение Гивенса для симметризации пары элементов, а затем применяя преобразование Jacobi для их обнуления, ${\displaystyle R}$

$${\displaystyle M\leftarrow J^{T}GMJ}$$

где — матрица вращения Гивенса с углом, выбранным таким образом, чтобы заданная пара недиагональных элементов стала равной после вращения, а где — матрица преобразования Якоби, которая обнуляет эти недиагональные элементы. Итерации происходят точно так же, как в алгоритме собственных значений Якоби: циклическими проходами по всем недиагональным элементам. ${\displaystyle G}$ ${\displaystyle J}$

После сходимости алгоритма результирующая диагональная матрица содержит сингулярные значения. Матрицы и накапливаются следующим образом: , . ${\displaystyle U}$ ${\displaystyle V}$ ${\displaystyle U\leftarrow UG^{T}J}$ ${\displaystyle V\leftarrow VJ}$

Численный подход

Разложение по сингулярным значениям можно вычислить, используя следующие наблюдения:

• Левые сингулярные векторы ⁠ ⁠ ${\displaystyle \mathbf {M} }$ представляют собой набор ортонормированных собственных векторов ⁠ ${\displaystyle \mathbf {M} \mathbf {M} ^{*}}$ ⁠ .
• Правосингулярные векторы ⁠ ⁠ ${\displaystyle \mathbf {M} }$ представляют собой набор ортонормированных собственных векторов ⁠ ⁠ ${\displaystyle \mathbf {M} ^{*}\mathbf {M} }$ .
• Ненулевые сингулярные значения ⁠ ⁠ ${\displaystyle \mathbf {M} }$ (находящиеся на диагональных элементах ) являются квадратными корнями ненулевых собственных значений как ⁠ ⁠ , так и ⁠ ⁠ . ${\displaystyle \mathbf {\Sigma } }$ ${\displaystyle \mathbf {M} ^{*}\mathbf {M} }$ ${\displaystyle \mathbf {M} \mathbf {M} ^{*}}$

SVD матрицы ⁠ ⁠ ${\displaystyle \mathbf {M} }$ обычно вычисляется с помощью двухэтапной процедуры. На первом этапе матрица сводится к двухдиагональной матрице . Это занимает порядка ⁠ ⁠ ${\displaystyle O(mn^{2})}$ операций с плавающей точкой (флоп), предполагая, что ⁠ ⁠ ${\displaystyle m\geq n.}$ Вторым этапом является вычисление SVD двухдиагональной матрицы. Этот этап можно выполнить только итеративным методом (как в алгоритмах собственных значений ). Однако на практике достаточно вычислить SVD с определенной точностью, например, машинного эпсилона . Если эта точность считается постоянной, то второй этап занимает ⁠ ⁠ ${\displaystyle O(n)}$ итераций, каждая из которых стоит ⁠ ⁠ ${\displaystyle O(n)}$ флопов. Таким образом, первый этап более затратный, и общая стоимость составляет ⁠ ⁠ ${\displaystyle O(mn^{2})}$ флопов (Trefethen & Bau III 1997, Lecture 31).

Первый шаг можно сделать с помощью отражений Хаусхолдера за стоимость ⁠ ⁠ ${\displaystyle 4mn^{2}-4n^{3}/3}$ флопов, предполагая, что нужны только сингулярные значения, а не сингулярные векторы. Если ⁠ ⁠ ${\displaystyle m}$ намного больше ⁠ ⁠, ${\displaystyle n}$ то выгодно сначала свести матрицу ⁠ ⁠ ${\displaystyle \mathbf {M} }$ к треугольной матрице с помощью QR-разложения , а затем использовать отражения Хаусхолдера для дальнейшего сведения матрицы к двухдиагональной форме; общая стоимость составляет ⁠ ⁠ ${\displaystyle 2mn^{2}+2n^{3}}$ флопов (Trefethen & Bau III 1997, Lecture 31).

Второй шаг может быть выполнен с помощью варианта алгоритма QR для вычисления собственных значений, который был впервые описан Голубом и Каханом (1965). Подпрограмма LAPACK DBDSQR ^[22] реализует этот итерационный метод с некоторыми модификациями для покрытия случая, когда сингулярные значения очень малы (Demmel & Kahan 1990). Вместе с первым шагом, использующим отражения Хаусхолдера и, при необходимости, разложение QR, это формирует процедуру DGESVD ^[23] для вычисления разложения сингулярных значений.

Тот же алгоритм реализован в GNU Scientific Library (GSL). GSL также предлагает альтернативный метод, который использует одностороннюю ортогонализацию Якоби на шаге 2 (GSL Team 2007). Этот метод вычисляет SVD двухдиагональной матрицы, решая последовательность ⁠ ⁠ ${\displaystyle 2\times 2}$ задач SVD, аналогично тому, как алгоритм собственных значений Якоби решает последовательность ⁠ ⁠ ${\displaystyle 2\times 2}$ методов собственных значений (Golub & Van Loan 1996, §8.6.3). Еще один метод для шага 2 использует идею алгоритмов собственных значений «разделяй и властвуй» (Trefethen & Bau III 1997, Lecture 31).

Существует альтернативный способ, который явно не использует разложение собственных значений. ^[24] Обычно проблема сингулярных значений матрицы ⁠ ⁠ ${\displaystyle \mathbf {M} }$ преобразуется в эквивалентную симметричную проблему собственных значений, такую ​​как ⁠ ⁠ ${\displaystyle \mathbf {M} \mathbf {M} ^{*},}$ ⁠ ⁠ ${\displaystyle \mathbf {M} ^{*}\mathbf {M} ,}$ или

$${\displaystyle {\begin{bmatrix}\mathbf {0} &\mathbf {M} \\\mathbf {M} ^{*}&\mathbf {0} \end{bmatrix}}.}$$

Подходы, использующие разложения собственных значений, основаны на алгоритме QR , который хорошо разработан, чтобы быть стабильным и быстрым. Обратите внимание, что сингулярные значения являются действительными, а правые и левые сингулярные векторы не требуются для формирования преобразований подобия. Можно итеративно чередовать разложение QR и разложение LQ , чтобы найти действительные диагональные эрмитовы матрицы . Разложение QR дает ⁠ ⁠, ${\displaystyle \mathbf {M} \Rightarrow \mathbf {Q} \mathbf {R} }$ а разложение LQ ⁠ ${\displaystyle \mathbf {R} }$ ⁠ дает ⁠ ⁠ ${\displaystyle \mathbf {R} \Rightarrow \mathbf {L} \mathbf {P} ^{*}.}$ Таким образом, на каждой итерации мы имеем ⁠ ⁠ ${\displaystyle \mathbf {M} \Rightarrow \mathbf {Q} \mathbf {L} \mathbf {P} ^{*},}$ обновление ⁠ ${\displaystyle \mathbf {M} \Leftarrow \mathbf {L} }$⁠ и повторение ортогонализаций. В конечном итоге ^{[ необходимо разъяснение ]} эта итерация между разложением QR и разложением LQ дает левые и правые унитарные сингулярные матрицы. Этот подход не может быть легко ускорен, как алгоритм QR может со спектральными сдвигами или дефляцией. Это связано с тем, что метод сдвига нелегко определить без использования преобразований подобия. Однако этот итеративный подход очень прост в реализации, поэтому является хорошим выбором, когда скорость не имеет значения. Этот метод также дает представление о том, как чисто ортогональные/унитарные преобразования могут получить SVD.

Аналитический результат 2 × 2 SVD

Сингулярные значения матрицы ⁠ ⁠ ${\displaystyle 2\times 2}$ можно найти аналитически. Пусть матрица будет ${\displaystyle \mathbf {M} =z_{0}\mathbf {I} +z_{1}\sigma _{1}+z_{2}\sigma _{2}+z_{3}\sigma _{3}}$

где — комплексные числа, параметризующие матрицу, ⁠ ⁠ — единичная матрица, а обозначают матрицы Паули . Тогда ее два сингулярных значения задаются как ${\displaystyle z_{i}\in \mathbb {C} }$ ${\displaystyle \mathbf {I} }$ ${\displaystyle \sigma _{i}}$

$${\displaystyle {\begin{aligned}\sigma _{\pm }&={\sqrt {|z_{0}|^{2}+|z_{1}|^{2}+|z_{2}|^{2}+|z_{3}|^{2}\pm {\sqrt {{\bigl (}|z_{0}|^{2}+|z_{1}|^{2}+|z_{2}|^{2}+|z_{3}|^{2}{\bigr )}^{2}-|z_{0}^{2}-z_{1}^{2}-z_{2}^{2}-z_{3}^{2}|^{2}}}}}\\&={\sqrt {|z_{0}|^{2}+|z_{1}|^{2}+|z_{2}|^{2}+|z_{3}|^{2}\pm 2{\sqrt {(\operatorname {Re} z_{0}z_{1}^{*})^{2}+(\operatorname {Re} z_{0}z_{2}^{*})^{2}+(\operatorname {Re} z_{0}z_{3}^{*})^{2}+(\operatorname {Im} z_{1}z_{2}^{*})^{2}+(\operatorname {Im} z_{2}z_{3}^{*})^{2}+(\operatorname {Im} z_{3}z_{1}^{*})^{2}}}}}\end{aligned}}}$$

Сокращенные СВД

Визуализация сокращенных вариантов SVD. Сверху вниз: 1: Полный SVD, 2: Тонкий SVD (удаление столбцов U, не соответствующих строкам V ^* ), 3: Компактный SVD (удаление исчезающих сингулярных значений и соответствующих столбцов/строк в U и V ^* ), 4: Усеченный SVD (сохранение только наибольших сингулярных значений t и соответствующих столбцов/строк в U и V ^* )

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

Тонкий СВД

Тонкий, или экономичный, SVD матрицы ⁠ ⁠ ${\displaystyle \mathbf {M} }$ определяется по формуле ^[25]

$${\displaystyle \mathbf {M} =\mathbf {U} _{k}\mathbf {\Sigma } _{k}\mathbf {V} _{k}^{*},}$$

где матрицы ⁠ ⁠ и ⁠ ⁠ содержат только первые ⁠ ⁠ столбцы ⁠ ⁠ и ⁠ ⁠ и ⁠ ⁠ содержит только первые ⁠ ⁠ сингулярные значения из ⁠ ⁠ Матрица ⁠ ⁠, таким образом , ⁠ ⁠ ⁠ ⁠ является ⁠ ⁠ диагональной, и ⁠ ⁠ является ⁠ ⁠ ${\displaystyle k=\min(m,n),}$ ${\displaystyle \mathbf {U} _{k}}$ ${\displaystyle \mathbf {V} _{k}}$ ${\displaystyle k}$ ${\displaystyle \mathbf {U} }$ ${\displaystyle \mathbf {V} ,}$ ${\displaystyle \mathbf {\Sigma } _{k}}$ ${\displaystyle k}$ ${\displaystyle \mathbf {\Sigma } .}$ ${\displaystyle \mathbf {U} _{k}}$ ${\displaystyle m\times k,}$ ${\displaystyle \mathbf {\Sigma } _{k}}$ ${\displaystyle k\times k}$ ${\displaystyle \mathbf {V} _{k}^{*}}$ ${\displaystyle k\times n.}$

Тонкий SVD использует значительно меньше пространства и времени вычислений, если ⁠ ⁠ ${\displaystyle k\ll \max(m,n).}$ Первым этапом его вычислений обычно будет QR-разложение ⁠ ⁠ , ${\displaystyle \mathbf {M} ,}$ что может значительно ускорить вычисления в этом случае.

Компактная СВД

Компактное SVD матрицы ⁠ ⁠ ${\displaystyle \mathbf {M} }$ задается выражением

$${\displaystyle \mathbf {M} =\mathbf {U} _{r}\mathbf {\Sigma } _{r}\mathbf {V} _{r}^{*}.}$$

Вычисляются только ⁠ ⁠ ${\displaystyle r}$ векторы-столбцы ⁠ ⁠ ${\displaystyle \mathbf {U} }$ и ⁠ ⁠ ${\displaystyle r}$ векторы-строки ⁠ ⁠, ${\displaystyle \mathbf {V} ^{*}}$ соответствующие ненулевым сингулярным значениям ⁠ ⁠ . Остальные векторы ${\displaystyle \mathbf {\Sigma } _{r}}$⁠ ⁠ ${\displaystyle \mathbf {U} }$ и ⁠ ⁠ ${\displaystyle \mathbf {V} ^{*}}$ не вычисляются. Это быстрее и экономичнее, чем тонкий SVD, если ⁠ ⁠ ${\displaystyle r\ll \min(m,n).}$ Матрица ⁠ ⁠, ${\displaystyle \mathbf {U} _{r}}$ таким образом , ⁠ ⁠ ${\displaystyle m\times r,}$ ⁠ ⁠ ${\displaystyle \mathbf {\Sigma } _{r}}$ является ⁠ ⁠ ${\displaystyle r\times r}$ диагональной, и ⁠ ⁠ ${\displaystyle \mathbf {V} _{r}^{*}}$ является ⁠ ⁠ ${\displaystyle r\times n.}$

Укороченная СВД

Во многих приложениях число ⁠ ⁠ ${\displaystyle r}$ ненулевых сингулярных значений велико, что делает даже Compact SVD непрактичным для вычисления. В таких случаях наименьшие сингулярные значения могут потребоваться усечь, чтобы вычислить только ⁠ ⁠ ${\displaystyle t\ll r}$ ненулевые сингулярные значения. Усеченный SVD больше не является точным разложением исходной матрицы ⁠ ⁠, ${\displaystyle \mathbf {M} ,}$ а скорее обеспечивает оптимальное приближение матрицы низкого ранга ⁠ ⁠ ${\displaystyle {\tilde {\mathbf {M} }}}$ любой матрицей фиксированного ранга ⁠ ⁠ ${\displaystyle t}$

$${\displaystyle {\tilde {\mathbf {M} }}=\mathbf {U} _{t}\mathbf {\Sigma } _{t}\mathbf {V} _{t}^{*},}$$

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

В приложениях, требующих приближения к обратной матрице Мура–Пенроуза , ⁠ ⁠ ${\displaystyle \mathbf {M} ,}$ представляют интерес наименьшие сингулярные значения ⁠ ⁠ ${\displaystyle \mathbf {M} }$ , вычислить которые сложнее, чем наибольшие.

Усеченный SVD используется в скрытой семантической индексации . ^[26]

Нормы

Нормы Ки Фана

Сумма наибольших ${\displaystyle k}$ сингулярных значений ⁠ ${\displaystyle \mathbf {M} }$⁠ является матричной нормой , нормой Ки Фана ⁠ ⁠ ⁠ ${\displaystyle k}$⁠ [ ${\displaystyle \mathbf {M} .}$27 ^]

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

$${\displaystyle \|\mathbf {M} \|=\|\mathbf {M} ^{*}\mathbf {M} \|^{\frac {1}{2}}}$$

Но в случае матрицы ⁠ ⁠ ${\displaystyle (\mathbf {M} ^{*}\mathbf {M} )^{1/2}}$ является нормальной матрицей , поэтому наибольшее собственное значение ⁠ ⁠ т.е. наибольшее сингулярное значение ⁠ ⁠ ${\displaystyle \|\mathbf {M} ^{*}\mathbf {M} \|^{1/2}}$ ${\displaystyle (\mathbf {M} ^{*}\mathbf {M} )^{1/2},}$ ${\displaystyle \mathbf {M} .}$

Последняя из норм Ки Фана, сумма всех сингулярных значений, является следовой нормой (также известной как «ядерная норма»), определяемой как (собственные значения ⁠ ⁠ являются квадратами сингулярных значений). ${\displaystyle \|\mathbf {M} \|=\operatorname {Tr} (\mathbf {M} ^{*}\mathbf {M} )^{1/2}}$ ${\displaystyle \mathbf {M} ^{*}\mathbf {M} }$

Норма Гильберта–Шмидта

Сингулярные значения связаны с другой нормой на пространстве операторов. Рассмотрим скалярное произведение Гильберта–Шмидта на матрицах ⁠ ⁠ ${\displaystyle n\times n}$ , определенное как

$${\displaystyle \langle \mathbf {M} ,\mathbf {N} \rangle =\operatorname {tr} \left(\mathbf {N} ^{*}\mathbf {M} \right).}$$

Итак, индуцированная норма равна

$${\displaystyle \|\mathbf {M} \|={\sqrt {\langle \mathbf {M} ,\mathbf {M} \rangle }}={\sqrt {\operatorname {tr} \left(\mathbf {M} ^{*}\mathbf {M} \right)}}.}$$

Поскольку след инвариантен относительно унитарной эквивалентности, это показывает,

$${\displaystyle \|\mathbf {M} \|={\sqrt {{\vphantom {\bigg |}}\sum _{i}\sigma _{i}^{2}}}}$$

где ⁠ ⁠ ${\displaystyle \sigma _{i}}$ — сингулярные значения ⁠ ⁠ ${\displaystyle \mathbf {M} .}$ Это называется нормой Фробениуса , 2-нормой Шаттена или нормой Гильберта–Шмидта ⁠ ⁠ ${\displaystyle \mathbf {M} .}$ Прямое вычисление показывает, что норма Фробениуса ⁠ ⁠ ${\displaystyle \mathbf {M} =(m_{ij})}$ совпадает с:

$${\displaystyle {\sqrt {{\vphantom {\bigg |}}\sum _{ij}|m_{ij}|^{2}}}.}$$

Кроме того, норма Фробениуса и норма следа (ядерная норма) являются частными случаями нормы Шаттена .

Вариации и обобщения

Масштабно-инвариантный SVD

Сингулярные значения матрицы ⁠ ⁠ ${\displaystyle \mathbf {A} }$ определяются однозначно и инвариантны относительно левых и/или правых унитарных преобразований ⁠ ⁠ ${\displaystyle \mathbf {A} .}$ Другими словами, сингулярные значения ⁠ ⁠ ${\displaystyle \mathbf {U} \mathbf {A} \mathbf {V} ,}$ для унитарных матриц ⁠ ⁠ ${\displaystyle \mathbf {U} }$ и ⁠ ⁠ ${\displaystyle \mathbf {V} ,}$ равны сингулярным значениям ⁠ ⁠ ${\displaystyle \mathbf {A} .}$ Это важное свойство для приложений, в которых необходимо сохранять евклидовы расстояния и инвариантность относительно вращений.

Масштабно-инвариантный SVD, или SI-SVD, ^[28] аналогичен обычному SVD, за исключением того, что его однозначно определенные сингулярные значения инвариантны относительно диагональных преобразований ⁠ ⁠ ${\displaystyle \mathbf {A} .}$ Другими словами, сингулярные значения ⁠ ⁠ ${\displaystyle \mathbf {D} \mathbf {A} \mathbf {E} ,}$ для обратимых диагональных матриц ⁠ ⁠ ${\displaystyle \mathbf {D} }$ и ⁠ ⁠ ${\displaystyle \mathbf {E} ,}$ равны сингулярным значениям ⁠ ⁠ ${\displaystyle \mathbf {A} .}$ Это важное свойство для приложений, для которых требуется инвариантность к выбору единиц измерения переменных (например, метрические или имперские единицы).

Ограниченные операторы в гильбертовых пространствах

Факторизацию ⁠ ⁠ ${\displaystyle \mathbf {M} =\mathbf {U} \mathbf {\Sigma } \mathbf {V} ^{*}}$ можно расширить до ограниченного оператора ⁠ ⁠ ${\displaystyle \mathbf {M} }$ в сепарабельном гильбертовом пространстве ⁠ ⁠ ${\displaystyle H.}$ А именно, для любого ограниченного оператора ⁠ ⁠ ${\displaystyle \mathbf {M} ,}$ существуют частичная изометрия ⁠ ⁠ ${\displaystyle \mathbf {U} ,}$ унитарное ⁠ ⁠ ${\displaystyle \mathbf {V} ,}$ пространство с мерой ⁠ ⁠ ${\displaystyle (X,\mu ),}$ и неотрицательная измеримая ⁠ ⁠ ${\displaystyle f}$ такая, что

$${\displaystyle \mathbf {M} =\mathbf {U} T_{f}\mathbf {V} ^{*}}$$

где ⁠ ⁠ ${\displaystyle T_{f}}$ — это умножение на ⁠ ⁠ ${\displaystyle f}$ на ⁠ ⁠ ${\displaystyle L^{2}(X,\mu ).}$

Это можно показать, имитируя линейный алгебраический аргумент для матричного случая выше. ⁠ ⁠ ${\displaystyle \mathbf {V} T_{f}\mathbf {V} ^{*}}$ является единственным положительным квадратным корнем ⁠ ⁠, ${\displaystyle \mathbf {M} ^{*}\mathbf {M} ,}$ как дано функциональным исчислением Бореля для самосопряженных операторов . Причина, по которой ⁠ ⁠ ${\displaystyle \mathbf {U} }$ не обязательно должен быть унитарным, заключается в том, что, в отличие от конечномерного случая, при заданной изометрии ⁠ ⁠ ${\displaystyle U_{1}}$ с нетривиальным ядром, подходящее ⁠ ⁠ ${\displaystyle U_{2}}$ может не быть найдено таким образом, что

$${\displaystyle {\begin{bmatrix}U_{1}\\U_{2}\end{bmatrix}}}$$

является унитарным оператором.

Что касается матриц, то факторизация по сингулярным значениям эквивалентна полярному разложению для операторов: мы можем просто записать

$${\displaystyle \mathbf {M} =\mathbf {U} \mathbf {V} ^{*}\cdot \mathbf {V} T_{f}\mathbf {V} ^{*}}$$

и обратите внимание, что ⁠ ⁠ ${\displaystyle \mathbf {U} \mathbf {V} ^{*}}$ по-прежнему является частичной изометрией, в то время как ⁠ ⁠ ${\displaystyle \mathbf {V} T_{f}\mathbf {V} ^{*}}$ является положительным.

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

Понятие сингулярных значений и лево/право-сингулярных векторов может быть расширено до компактного оператора в гильбертовом пространстве , поскольку они имеют дискретный спектр. Если ⁠ ⁠ ${\displaystyle T}$ компактно, каждое ненулевое ⁠ ⁠ ${\displaystyle \lambda }$ в его спектре является собственным значением. Более того, компактный самосопряженный оператор может быть диагонализирован его собственными векторами. Если ⁠ ⁠ ${\displaystyle \mathbf {M} }$ компактно, то и ⁠ ⁠ ${\displaystyle \mathbf {M} ^{*}\mathbf {M} }$ . Применяя результат диагонализации, унитарный образ его положительного квадратного корня ⁠ ⁠ ${\displaystyle T_{f}}$ имеет набор ортонормированных собственных векторов ⁠ ⁠, ${\displaystyle \{e_{i}\}}$ соответствующих строго положительным собственным значениям ⁠ ⁠ ${\displaystyle \{\sigma _{i}\}}$ . Для любого ⁠ ⁠ ${\displaystyle \psi }$ в ⁠ ⁠ ${\displaystyle H,}$

$${\displaystyle \mathbf {M} \psi =\mathbf {U} T_{f}\mathbf {V} ^{*}\psi =\sum _{i}\left\langle \mathbf {U} T_{f}\mathbf {V} ^{*}\psi ,\mathbf {U} e_{i}\right\rangle \mathbf {U} e_{i}=\sum _{i}\sigma _{i}\left\langle \psi ,\mathbf {V} e_{i}\right\rangle \mathbf {U} e_{i},}$$

где ряд сходится в топологии нормы на ⁠ ⁠ ${\displaystyle H.}$ Обратите внимание, как это напоминает выражение из конечномерного случая. ⁠ ⁠ ${\displaystyle \sigma _{i}}$ называются сингулярными значениями ⁠ ⁠ ${\displaystyle \mathbf {M} .}$ ⁠ ⁠ ${\displaystyle \{\mathbf {U} e_{i}\}}$ (соответственно ⁠ ⁠ ${\displaystyle \{\mathbf {U} e_{i}\}}$ ) можно считать левосингулярными (соответственно правосингулярными) векторами ⁠ ⁠ ${\displaystyle \mathbf {M} .}$

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

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

История

Сингулярное разложение было первоначально разработано дифференциальными геометрами , которые хотели определить, можно ли сделать действительную билинейную форму равной другой посредством независимых ортогональных преобразований двух пространств, на которых она действует. Эудженио Бельтрами и Камиль Джордан независимо друг от друга в 1873 и 1874 годах соответственно открыли, что сингулярные значения билинейных форм, представленные в виде матрицы, образуют полный набор инвариантов для билинейных форм при ортогональных подстановках. Джеймс Джозеф Сильвестр также пришел к сингулярному разложению для действительных квадратных матриц в 1889 году, по-видимому, независимо как от Бельтрами, так и от Джордана. Сильвестр назвал сингулярные значения каноническими множителями матрицы ⁠ ⁠ Четвертым математиком, независимо открывшим сингулярное разложение, был Отонн в 1915 году, который пришел к нему с помощью полярного разложения . Первое доказательство сингулярного разложения для прямоугольных и комплексных матриц, по-видимому, было получено Карлом Эккартом и Гейлом Дж. Янгом в 1936 году; ^[29] они рассматривали это как обобщение преобразования главной оси для эрмитовых матриц . ${\displaystyle \mathbf {A} .}$

В 1907 году Эрхард Шмидт определил аналог сингулярных значений для интегральных операторов (которые являются компактными при некоторых слабых технических предположениях); по-видимому, он не знал о параллельной работе по сингулярным значениям конечных матриц. Эта теория была далее развита Эмилем Пикаром в 1910 году, который первым назвал числа сингулярными значениями (или по-французски valeurs singulières ). ${\displaystyle \sigma _{k}}$

Практические методы вычисления SVD восходят к Когбетлянцу в 1954–1955 годах и Хестенсу в 1958 году ^[30], очень похожим на алгоритм собственных значений Якоби , который использует вращения плоскости или вращения Гивенса . Однако они были заменены методом Джина Голуба и Уильяма Кахана, опубликованным в 1965 году ^[31] , который использует преобразования Хаусхолдера или отражения. В 1970 году Голуб и Кристиан Рейнш ^[32] опубликовали вариант алгоритма Голуба/Кахана, который до сих пор является наиболее используемым сегодня.

Смотрите также

• Каноническая корреляция
• Каноническая форма
• Анализ соответствия (CA)
• Проклятие размерности
• Цифровая обработка сигнала
• Уменьшение размерности
• Собственное разложение матрицы
• Эмпирические ортогональные функции (EOF)
• анализ Фурье
• Обобщенное сингулярное разложение
• Неравенства относительно сингулярных значений
• К-СВД
• Латентный семантический анализ
• Скрытая семантическая индексация
• Линейный метод наименьших квадратов
• Список преобразований Фурье
• Хеширование, чувствительное к местоположению
• Низкоранговое приближение
• Матричное разложение
• Многолинейный анализ главных компонент (MPCA)
• Поиск ближайшего соседа
• Нелинейный итеративный метод частичных наименьших квадратов
• Полярное разложение
• Анализ главных компонент (PCA)
• разложение Шмидта
• Нормальная форма Смита
• Единственное значение
• Временной ряд
• Двумерное сингулярное разложение (2DSVD)
• неравенство следов фон Неймана
• Вейвлет-сжатие

Примечания

1. DeAngelis, GC; Ohzawa, I.; Freeman, RD (октябрь 1995 г.). «Динамика рецептивного поля в центральных зрительных путях». Trends Neurosci . 18 (10): 451–8. doi :10.1016/0166-2236(95)94496-R. PMID  8545912. S2CID  12827601.
2. Depireux, DA; Simon, JZ; Klein, DJ; Shamma, SA (март 2001 г.). «Характеристика спектрально-временного поля ответа с динамическими рябями в первичной слуховой коре хорька». J. Neurophysiol . 85 (3): 1220–34. doi :10.1152/jn.2001.85.3.1220. PMID  11247991.
3. Разложение сингулярных значений в симметричной (Lowdin) ортогонализации и сжатии данных
4. Sahidullah, Md.; Kinnunen, Tomi (март 2016). «Локальные спектральные характеристики изменчивости для проверки говорящего». Цифровая обработка сигналов . 50 : 1–11. doi :10.1016/j.dsp.2015.10.011.
5. Mademlis, Ioannis; Tefas, Anastasios; Pitas, Ioannis (2018). «Регуляризированная значимость видеокадра на основе SVD для неконтролируемого суммирования видео активности». Международная конференция IEEE по акустике, речи и обработке сигналов (ICASSP) 2018 года. IEEE. стр. 2691–2695. doi :10.1109/ICASSP.2018.8462274. ISBN 978-1-5386-4658-8. S2CID  52286352 . Получено 19 января 2023 г. .
6. O. Alter, PO Brown и D. Botstein (сентябрь 2000 г.). «Разложение сингулярных значений для обработки и моделирования данных экспрессии генома». PNAS . 97 (18): 10101–10106. Bibcode :2000PNAS...9710101A. doi : 10.1073/pnas.97.18.10101 . PMC 27718 . PMID  10963673. 
7. O. Alter; GH Golub (ноябрь 2004 г.). «Интегративный анализ данных в масштабе генома с использованием псевдообратной проекции предсказывает новую корреляцию между репликацией ДНК и транскрипцией РНК». PNAS . 101 (47): 16577–16582. Bibcode :2004PNAS..10116577A. doi : 10.1073/pnas.0406767101 . PMC 534520 . PMID  15545604. 
8. O. Alter; GH Golub (август 2006 г.). «Разложение сингулярных значений распределения длин мРНК в масштабе генома выявляет асимметрию в расширении полос электрофореза РНК в геле». PNAS . 103 (32): 11828–11833. Bibcode :2006PNAS..10311828A. doi : 10.1073/pnas.0604756103 . PMC 1524674 . PMID  16877539. 
9. Bertagnolli, NM; Drake, JA; Tennessen, JM; Alter, O. (ноябрь 2013 г.). "SVD идентифицирует функции распределения длины транскрипта из данных ДНК-микрочипов и выявляет эволюционные силы, глобально влияющие на метаболизм ГБМ". PLOS ONE . ​​8 (11): e78913. Bibcode :2013PLoSO...878913B. doi : 10.1371/journal.pone.0078913 . PMC 3839928 . PMID  24282503. Выделение. 
10. Эдельман, Алан (1992). «О распределении масштабированного числа обусловленности» (PDF) . Math. Comp . 58 (197): 185–190. Bibcode :1992MaCom..58..185E. doi : 10.1090/S0025-5718-1992-1106966-2 .
11. Шен, Цзяньхун (Джеки) (2001). «О сингулярных значениях гауссовых случайных матриц». Linear Alg. Appl . 326 (1–3): 1–14. doi : 10.1016/S0024-3795(00)00322-0 .
12. Уолтон, С.; Хассан, О.; Морган, К. (2013). «Моделирование пониженного порядка для нестационарного потока жидкости с использованием надлежащего ортогонального разложения и радиальных базисных функций». Прикладное математическое моделирование . 37 (20–21): 8930–8945. doi : 10.1016/j.apm.2013.04.025 .
13. Setyawati, Y.; Ohme, F.; Khan, S. (2019). «Улучшение модели гравитационной волны с помощью динамической калибровки». Physical Review D. 99 ( 2): 024010. arXiv : 1810.07060 . Bibcode : 2019PhRvD..99b4010S. doi : 10.1103/PhysRevD.99.024010. S2CID  118935941.
14. Сарвар, Бадрул; Карипис, Джордж; Констан, Джозеф А. и Ридл, Джон Т. (2000). «Применение снижения размерности в рекомендательной системе – пример» (PDF) . Университет Миннесоты . {{cite journal}}: Цитировать журнал требует |journal=( помощь )
15. Босаг Заде, Реза; Карлссон, Гуннар (2013). «Квадрат матрицы, не зависящей от размерности, с использованием MapReduce» (PDF) . arXiv : 1304.1467 . Bibcode :2013arXiv1304.1467B. {{cite journal}}: Цитировать журнал требует |journal=( помощь )
16. Хади Фанаи Торк; Жуан Гама (сентябрь 2014 г.). «Метод собственного пространства для обнаружения пространственно-временных горячих точек». Expert Systems . 32 (3): 454–464. arXiv : 1406.3506 . Bibcode :2014arXiv1406.3506F. doi :10.1111/exsy.12088. S2CID  15476557.
17. Хади Фанаи Торк; Жуан Гама (май 2015 г.). «EigenEvent: алгоритм обнаружения событий из сложных потоков данных в синдромном наблюдении». Интеллектуальный анализ данных . 19 (3): 597–616. arXiv : 1406.3496 . doi : 10.3233/IDA-150734. S2CID  17966555.
18. Муралидхаран, Вивек; Хауэлл, Кэтлин (2023). «Растяжение направлений в цислунарном пространстве: применение для отправлений и проектирования трансферов». Астродинамика . 7 (2): 153–178. Bibcode : 2023AsDyn...7..153M. doi : 10.1007/s42064-022-0147-z. S2CID  252637213.
19. Муралидхаран, Вивек; Хауэлл, Кэтлин (2022). «Использование направлений растяжения для поддержания стационарности на гало-орбитах Земля-Луна». Достижения в космических исследованиях . 69 (1): 620–646. Bibcode : 2022AdSpR..69..620M. doi : 10.1016/j.asr.2021.10.028. S2CID  239490016.
20. Чтобы увидеть это, нам просто нужно это заметить и запомнить . ${\displaystyle \operatorname {Tr} (\mathbf {V} _{2}^{*}\mathbf {M} ^{*}\mathbf {M} \mathbf {V} _{2})=\|\mathbf {M} \mathbf {V} _{2}\|^{2}}$ ${\displaystyle \|A\|=0\Leftrightarrow A=0}$
21. Rijk, PPM de (1989). «Односторонний алгоритм Якоби для вычисления разложения сингулярных значений на векторном компьютере». SIAM J. Sci. Stat. Comput . 10 : 359.
22. Netlib.org
23. Netlib.org
24. mathworks.co.kr/matlabcentral/fileexchange/12674-simple-svd
25. Деммель, Джеймс (2000). «Разложения». Шаблоны для решения алгебраических задач на собственные значения. Бай, Чжаоцзюнь; Деммель, Джеймс; Донгарра, Джек Дж.; Руэ, Аксель; ван дер Ворст, Хенк А. Общество промышленной и прикладной математики. дои : 10.1137/1.9780898719581. ISBN 978-0-89871-471-5.
26. Chicco, D; Masseroli, M (2015). «Программный пакет для прогнозирования аннотаций генов и белков и поиска сходства». Труды IEEE/ACM по вычислительной биологии и биоинформатике . 12 (4): 837–843. doi : 10.1109/TCBB.2014.2382127. hdl : 11311/959408 . PMID  26357324. S2CID  14714823.
27. Фань, Кентукки (1951). «Максимальные свойства и неравенства для собственных значений вполне непрерывных операторов». Труды Национальной академии наук Соединенных Штатов Америки . 37 (11): 760–766. Bibcode :1951PNAS...37..760F. doi : 10.1073/pnas.37.11.760 . PMC 1063464 . PMID  16578416. 
28. Ульманн, Джеффри (2018), Обобщенная обратная матрица, согласованная с диагональными преобразованиями (PDF) , SIAM Journal on Matrix Analysis, т. 239, стр. 781–800, архивировано из оригинала (PDF) 17 июня 2019 г.
29. Эккарт, К.; Янг, Г. (1936). «Аппроксимация одной матрицы другой более низкого ранга». Психометрика . 1 (3): 211–8. doi :10.1007/BF02288367. S2CID  10163399.
30. Хестенс, MR (1958). «Обращение матриц с помощью биортогонализации и связанные с этим результаты». Журнал Общества промышленной и прикладной математики . 6 (1): 51–90. doi :10.1137/0106005. JSTOR  2098862. MR  0092215.
31. (Голуб и Кахан 1965)
32. Голуб, Г.Х .; Рейнш, К. (1970). «Разложение по сингулярным значениям и решения методом наименьших квадратов». Нумерическая математика . 14 (5): 403–420. дои : 10.1007/BF02163027. MR  1553974. S2CID  123532178.

Ссылки

• Баннерджи, Судипто; Рой, Аниндья (2014), Линейная алгебра и матричный анализ для статистики , Тексты по статистической науке (1-е изд.), Chapman and Hall/CRC, ISBN 978-1420095388
• Бисгард, Джеймс (2021). Анализ и линейная алгебра: разложение сингулярных значений и приложения . Студенческая математическая библиотека (1-е изд.). AMS. ISBN 978-1-4704-6332-8.
• Chicco, D; Masseroli, M (2015). «Программный пакет для прогнозирования аннотаций генов и белков и поиска сходства». Труды IEEE/ACM по вычислительной биологии и биоинформатике . 12 (4): 837–843. doi : 10.1109/TCBB.2014.2382127. hdl : 11311/959408 . PMID  26357324. S2CID  14714823.
• Трефетен, Ллойд Н.; Бау III, Дэвид (1997). Численная линейная алгебра . Филадельфия: Общество промышленной и прикладной математики. ISBN 978-0-89871-361-9.
• Деммель, Джеймс ; Кахан, Уильям (1990). «Точные сингулярные значения двухдиагональных матриц». Журнал SIAM по научным и статистическим вычислениям . 11 (5): 873–912. CiteSeerX  10.1.1.48.3740 . doi :10.1137/0911052.
• Голуб, Джин Х.; Кахан , Уильям (1965). «Вычисление сингулярных значений и псевдообратной матрицы». Журнал Общества промышленной и прикладной математики, Серия B: Численный анализ . 2 (2): 205–224. Bibcode : 1965SJNA....2..205G. doi : 10.1137/0702016. JSTOR  2949777.
• Голуб, Джин Х.; Ван Лоан, Чарльз Ф. (1996). Матричные вычисления (3-е изд.). Университет Джонса Хопкинса. ISBN 978-0-8018-5414-9.
• GSL Team (2007). "§14.4 Разложение сингулярных значений". Научная библиотека GNU. Справочное руководство .
• Halldor, Bjornsson и Venegas, Silvia A. (1997). "Руководство по EOF и SVD-анализу климатических данных". Университет Макгилла, CCGCR Report No. 97-1, Монреаль, Квебек, 52 стр.
• Хансен, ПК (1987). «Усеченный SVD как метод регуляризации». BIT . 27 (4): 534–553. doi :10.1007/BF01937276. S2CID  37591557.
• Хорн, Роджер А.; Джонсон, Чарльз Р. (1985). "Раздел 7.3". Матричный анализ . Cambridge University Press. ISBN 978-0-521-38632-6.
• Хорн, Роджер А.; Джонсон, Чарльз Р. (1991). "Глава 3" . Темы анализа матриц . Cambridge University Press. ISBN 978-0-521-46713-1.
• Самет, Х. (2006). Основы многомерных и метрических структур данных . Морган Кауфманн. ISBN 978-0-12-369446-1.
• Стрэнг Г. (1998). "Раздел 6.7". Введение в линейную алгебру (3-е изд.). Wellesley-Cambridge Press. ISBN 978-0-9614088-5-5.
• Стюарт, GW (1993). «О ранней истории разложения сингулярных значений». SIAM Review . 35 (4): 551–566. CiteSeerX  10.1.1.23.1831 . doi :10.1137/1035134. hdl :1903/566. JSTOR  2132388.
• Wall, Michael E.; Rechtsteiner, Andreas; Rocha, Luis M. (2003). «Разложение сингулярных значений и анализ главных компонент». В DP Berrar; W. Dubitzky; M. Granzow (ред.). Практический подход к анализу данных микрочипов . Norwell, MA: Kluwer. стр. 91–109.
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), «Раздел 2.6», Numerical Recipes: The Art of Scientific Computing (3-е изд.), Нью-Йорк: Cambridge University Press, ISBN 978-0-521-88068-8

Внешние ссылки

• Онлайн-калькулятор SVD