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

Иллюстрация сингулярного разложения $UΣV ⁎$ вещественной $2 \times 2$ матрицы $M$ .
**Вверху:** действие $M$ , обозначенное его влиянием на единичный круг $D$ и два канонических единичных вектора $e 1$ и $e 2$ .
**Слева:** действие $Ви. ⁎$ , вращение на $D$ , $e 1$ и $e 2$ .
**Внизу:** действие $Σ$ , масштабирование сингулярными значениями $σ 1$ по горизонтали и $σ 2$ по вертикали.
**Справа:** действие $U$ , еще одно вращение.

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

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

Диагональные записи $\sigma _{i}=\Sigma _{ii}$ из $\mathbf {\Sigma }$ однозначно определяются $\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},$ и если они отсортированы так, что сингулярные значения $\sigma _{i}$ со значением 0, все находятся в столбцах (или строках) с наибольшим номером, разложение по сингулярным значениям можно записать как

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

где $r\leq \min\{m,n\}$ это ранг $\mathbf {M} .$

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

Термин иногда относится к компактной СВД , аналогичное разложение $\mathbf {M} =\mathbf {U\Sigma V} ^{*}$ в котором $\mathbf {\Sigma }$ квадратная диагональ размера $r\times r,$ где $r\leq \min\{m,n\}$ это ранг $\mathbf {M} ,$ и имеет только ненулевые сингулярные значения. В этом варианте $\mathbf {U}$ является $m\times r$ полуунитарная матрица и $\mathbf {V}$ является $>n\times r$ полуунитарная матрица такая, что $\mathbf {U} ^{*}\mathbf {U} =\mathbf {V} ^{*}\mathbf {V} =\mathbf {I} _{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 {V} ^{*}$ ), с последующим покоординатным масштабированием ( $\mathbf {\Sigma }$ ), за которым следует еще одно вращение или отражение ( $\mathbf {U}$ ).

В частности, если $\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-пространстве. Сингулярные значения кодируют величину полуоси, а сингулярные векторы кодируют направление. смотрите ниже Более подробную информацию .

Столбцы $U$ и $V$ ортонормированными . базисами являются

С $\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 {U}$ и $\mathbf {V}$ унитарны, мы знаем, что столбцы $\mathbf {U} _{1},\ldots ,\mathbf {U} _{m}$ из $\mathbf {U}$ получить базис ортонормированный $K^{m}$ и столбцы $\mathbf {V} _{1},\ldots ,\mathbf {V} _{n}$ из $\mathbf {V}$ получить ортонормированный базис $K^{n}$ (относительно стандартных скалярных произведений на этих пространствах).

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

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

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

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

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

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

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

Пример [ править ]

Рассмотрим $4\times 5$ матрица

\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}}

Разложение этой матрицы по сингулярным значениям имеет вид $\mathbf {U} \mathbf {\Sigma } \mathbf {V} ^{*}$

{\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}}

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

{\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}}

Это конкретное разложение по сингулярным значениям не уникально. Выбор $\mathbf {V}$ такой, что

\mathbf {V} ^{*}={\begin{bmatrix}\color {Violet}0&\color {Violet}1&\color {Violet}0&\color {Violet}0&\color {Violet}0\\\color {Plum}0&\color {Plum}0&\color {Plum}1&\color {Plum}0&\color {Plum}0\\\color {Magenta}{\sqrt {0.2}}&\color {Magenta}0&\color {Magenta}0&\color {Magenta}0&\color {Magenta}{\sqrt {0.8}}\\\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}}

также является допустимым разложением по сингулярным значениям.

СВД и спектральное разложение [ править ]

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

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

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

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

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

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

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

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

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

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

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

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

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

Если $\mathbf {M}$ есть СВД $\mathbf {M} =\mathbf {U} \mathbf {\Sigma } \mathbf {V} ^{*},$ имеют место следующие два соотношения:

{\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}}

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

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

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

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

Применение СВД [ править ]

Псевдообратный [ править ]

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

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

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

Решение однородных линейных уравнений [ править ]

Совокупность однородных линейных уравнений можно записать в виде $\mathbf {A} \mathbf {x} =\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 {x} \|=1.$ Решением оказывается правосингулярный вектор $\mathbf {A}$ соответствующий наименьшему единственному значению.

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

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

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

низкого ранга аппроксимация Матричная

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

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

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

Разделяемые модели [ править ]

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

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

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

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

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

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

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

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

\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} ,

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

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

Алгоритм Кабша [ править ]

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

Обработка сигналов [ править ]

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

Другие примеры [ править ]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

\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} .

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

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

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

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

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

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

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

{\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}}.

Это означает, что

\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} .

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

{\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}}

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

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

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

Затем,

\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} ,

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

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

\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}} ,

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

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

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

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

{\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} ,

какой желаемый результат:

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

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

На основе вариационной характеристики [ править ]

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

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

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

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

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

\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}

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

{\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}}

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

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

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

{\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}}

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

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

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

Расчет СВД [ править ]

Односторонний алгоритм Якоби [ править ]

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

M\leftarrow MJ(p,q,\theta ),

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

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

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

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

M\leftarrow J^{T}GMJ

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

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

Численный подход [ править ]

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

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

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

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

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

Тот же алгоритм реализован в Научной библиотеке GNU (GSL). GSL также предлагает альтернативный метод, который использует одностороннюю ортогонализацию Якоби на шаге 2 ( GSL Team 2007 ). Этот метод вычисляет SVD двудиагональной матрицы, решая последовательность $2\times 2$ Проблемы SVD, аналогичные тому, как алгоритм собственных значений Якоби решает последовательность $2\times 2$ методы собственных значений ( Голуб и Ван Лоан 1996 , §8.6.3). Еще один метод для шага 2 использует идею алгоритма собственных значений «разделяй и властвуй» ( Trfethen & Bau III 1997 , лекция 31).

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

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

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

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

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

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

{\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, включая полное унитарное разложение нулевого пространства матрицы. Вместо этого часто бывает достаточно (а также быстрее и экономичнее с точки зрения хранения) вычислить уменьшенную версию SVD. Для $m\times n$ матрица $\mathbf {M}$ ранга $r$ :

Тонкая СВД [ править ]

Тонкая или экономичная SVD-матрица $\mathbf {M}$ дан кем-то ^[25]

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

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

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

Компактная СВД [ править ]

Компактная СВД матрицы $\mathbf {M}$ дан кем-то

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

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

Усеченная СВД [ править ]

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

{\tilde {\mathbf {M} }}=\mathbf {U} _{t}\mathbf {\Sigma } _{t}\mathbf {V} _{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}$ рассчитываются. Это может быть намного быстрее и экономичнее, чем компактная СВД, если $t\ll r,$ но требует совершенно другого набора численных решателей.

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

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

Нормы [ править ]

Нормы Кай Фана [ править ]

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

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

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

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

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

Норма Гильберта – Шмидта [ править ]

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

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

Таким образом, индуцированная норма равна

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

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

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

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

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

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

Вариации и обобщения [ править ]

Масштабно-инвариантный СВД [ править ]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

\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},

где ряд сходится в топологии нормы на $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 году; ^[29] они видели в этом обобщение преобразования главной оси для эрмитовых матриц .

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

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

См. также [ править ]

Примечания [ править ]

^ ДеАнджелис, GC; Одзава, И.; Фриман, Р.Д. (октябрь 1995 г.). «Динамика рецептивных полей в центральных зрительных путях». Тенденции нейробиологии . 18 (10): 451–8. дои : 10.1016/0166-2236(95)94496-Р . ПМИД 8545912 . S2CID 12827601 .
^ Депирё, Д.А.; Саймон, Джей Зи; Кляйн, диджей; Шамма, SA (март 2001 г.). «Характеристика спектрально-временного поля реакции с динамическими пульсациями в первичной слуховой коре хорька». Дж. Нейрофизиология . 85 (3): 1220–34. дои : 10.1152/jn.2001.85.3.1220 . ПМИД 11247991 .
^ Разложение по сингулярным значениям при симметричной (Lowdin) ортогонализации и сжатии данных
^ Сахидулла, штат Мэриленд; Киннунен, Томи (март 2016 г.). «Функции локальной спектральной изменчивости для проверки динамиков» . Цифровая обработка сигналов . 50 : 1–11. дои : 10.1016/j.dsp.2015.10.011 .
^ Мадемлис, Иоаннис; Тефас, Анастасиос; Питас, Иоаннис (2018). «Регуляризованная значимость видеокадров на основе SVD для обобщения видео неконтролируемых действий». Международная конференция IEEE по акустике, речи и обработке сигналов (ICASSP) 2018 г. IEEE. стр. 2691–2695. дои : 10.1109/ICASSP.2018.8462274 . ISBN 978-1-5386-4658-8 . S2CID 52286352 . Проверено 19 января 2023 г.
^ О. Альтер, П.О. Браун и Д. Ботштейн (сентябрь 2000 г.). «Разложение по сингулярным значениям для обработки и моделирования данных полногеномной экспрессии» . ПНАС . 97 (18): 10101–10106. Бибкод : 2000PNAS...9710101A . дои : 10.1073/pnas.97.18.10101 . ПМК 27718 . ПМИД 10963673 .
^ О. Альтер; Голубь Г.Х. (ноябрь 2004 г.). «Интегративный анализ данных в масштабе генома с использованием псевдообратной проекции предсказывает новую корреляцию между репликацией ДНК и транскрипцией РНК» . ПНАС . 101 (47): 16577–16582. Бибкод : 2004PNAS..10116577A . дои : 10.1073/pnas.0406767101 . ПМК 534520 . ПМИД 15545604 .
^ О. Альтер; Голубь Г.Х. (август 2006 г.). «Разложение по сингулярным значениям распределения длин мРНК в масштабе генома выявляет асимметрию в расширении полосы гель-электрофореза РНК» . ПНАС . 103 (32): 11828–11833. Бибкод : 2006PNAS..10311828A . дои : 10.1073/pnas.0604756103 . ПМЦ 1524674 . ПМИД 16877539 .
^ Бертаньолли, Нью-Мексико; Дрейк, Дж.А.; Теннессен, Дж. М.; Альтер, О. (ноябрь 2013 г.). «SVD идентифицирует функции распределения длины транскрипта на основе данных микрочипов ДНК и выявляет эволюционные силы, глобально влияющие на метаболизм ГБМ» . ПЛОС ОДИН . 8 (11): е78913. Бибкод : 2013PLoSO...878913B . дои : 10.1371/journal.pone.0078913 . ПМЦ 3839928 . ПМИД 24282503 . Выделять .
^ Эдельман, Алан (1992). «О распределении масштабированного числа состояния» (PDF) . Математика. Комп . 58 (197): 185–190. Бибкод : 1992MaCom..58..185E . дои : 10.1090/S0025-5718-1992-1106966-2 .
^ Шен, Цзяньхун (Джеки) (2001). «Об сингулярных значениях гауссовских случайных матриц» . Линейный Алг. Приложение . 326 (1–3): 1–14. дои : 10.1016/S0024-3795(00)00322-0 .
^ Уолтон, С.; Хасан, О.; Морган, К. (2013). «Моделирование пониженного порядка нестационарного потока жидкости с использованием правильного ортогонального разложения и радиальных базисных функций» . Прикладное математическое моделирование . 37 (20–21): 8930–8945. дои : 10.1016/j.apm.2013.04.025 .
^ Сетьявати, Ю.; Оме, Ф.; Хан, С. (2019). «Улучшение модели гравитационных сигналов посредством динамической калибровки». Физический обзор D . 99 (2): 024010. arXiv : 1810.07060 . Бибкод : 2019PhRvD..99b4010S . дои : 10.1103/PhysRevD.99.024010 . S2CID 118935941 .
^ Сарвар, Бадрул; Карипис, Георгий; Констан, Джозеф А. и Ридл, Джон Т. (2000). «Применение уменьшения размерности в рекомендательной системе – практический пример» (PDF) . Университет Миннесоты . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )
^ Босах Заде, Реза; Карлссон, Гуннар (2013). «Квадрат матрицы, не зависящий от измерения, с использованием MapReduce» (PDF) . arXiv : 1304.1467 . Бибкод : 2013arXiv1304.1467B . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )
^ Хади Фанаи Торк; Жоау Гама (сентябрь 2014 г.). «Метод собственного пространства для обнаружения пространственно-временных горячих точек». Экспертные системы . 32 (3): 454–464. arXiv : 1406.3506 . Бибкод : 2014arXiv1406.3506F . дои : 10.1111/exsy.12088 . S2CID 15476557 .
^ Хади Фанаи Торк; Жоау Гама (май 2015 г.). «EigenEvent: алгоритм обнаружения событий из сложных потоков данных при синдромном наблюдении». Интеллектуальный анализ данных . 19 (3): 597–616. arXiv : 1406.3496 . дои : 10.3233/IDA-150734 . S2CID 17966555 .
^ Муралидхаран, Вивек; Хауэлл, Кэтлин (2023). «Направления растяжения в окололунном пространстве: Заявки на вылеты и проектирование трансферов». Астродинамика . 7 (2): 153–178. Бибкод : 2023AsDyn...7..153M . дои : 10.1007/s42064-022-0147-z . S2CID 252637213 .
^ Муралидхаран, Вивек; Хауэлл, Кэтлин (2022). «Использование направлений растяжения для поддержания положения на галоорбитах Земля-Луна». Достижения в космических исследованиях . 69 (1): 620–646. Бибкод : 2022AdSpR..69..620M . дои : 10.1016/j.asr.2021.10.028 . S2CID 239490016 .
^ Чтобы увидеть это, нам просто нужно заметить, что $\operatorname {Tr} (\mathbf {V} _{2}^{*}\mathbf {M} ^{*}\mathbf {M} \mathbf {V} _{2})=\|\mathbf {M} \mathbf {V} _{2}\|^{2}$ и помни это $\|A\|=0\Leftrightarrow A=0$ .
^ Райк, PPM де (1989). «Односторонний алгоритм Якоби для вычисления разложения по сингулярным значениям на векторном компьютере». СИАМ J. Sci. Стат. Вычислить . 10 : 359.
^ Netlib.org
^ Netlib.org
^ mathworks.co.kr/matlabcentral/fileexchange/12674-simple-svd
^ Деммель, Джеймс (2000). «Разложения» . Шаблоны для решения алгебраических задач на собственные значения . Бай, Чжаоцзюнь; Деммель, Джеймс; Донгарра, Джек Дж.; Руэ, Аксель; ван дер Ворст, Хенк А. Общество промышленной и прикладной математики. дои : 10.1137/1.9780898719581 . ISBN 978-0-89871-471-5 .
^ Чикко, Д; Массероли, М (2015). «Программный пакет для прогнозирования аннотаций генов и белков и поиска сходства» . Транзакции IEEE/ACM по вычислительной биологии и биоинформатике . 12 (4): 837–843. дои : 10.1109/TCBB.2014.2382127 . hdl : 11311/959408 . ПМИД 26357324 . S2CID 14714823 .
^ Фан, Кентукки (1951). «Максимальные свойства и неравенства для собственных значений вполне непрерывных операторов» . Труды Национальной академии наук Соединенных Штатов Америки . 37 (11): 760–766. Бибкод : 1951PNAS...37..760F . дои : 10.1073/pnas.37.11.760 . ПМЦ 1063464 . ПМИД 16578416 .
^ Ульманн, Джеффри (2018), Обобщенная обратная матрица, согласующаяся с диагональными преобразованиями (PDF) , SIAM Journal on Matrix Analysis, vol. 239, стр. 781–800, заархивировано из оригинала (PDF) 7 марта 2019 г.
^ Эккарт, К .; Янг, Г. (1936). «Приближение одной матрицы другой меньшего ранга». Психометрика . 1 (3): 211–8. дои : 10.1007/BF02288367 . S2CID 10163399 .
^ Хестенес, MR (1958). «Обращение матриц путем биортогонализации и связанные с этим результаты». Журнал Общества промышленной и прикладной математики . 6 (1): 51–90. дои : 10.1137/0106005 . JSTOR 2098862 . МР 0092215 .
^ ( Голуб и Кахан 1965 )
^ Голуб, GH ; Рейнш, К. (1970). «Разложение по сингулярным значениям и решения методом наименьших квадратов». Нумерическая математика . 14 (5): 403–420. дои : 10.1007/BF02163027 . МР 1553974 . S2CID 123532178 .

Ссылки [ править ]

Банерджи, Судипто; Рой, Аниндья (2014), Линейная алгебра и матричный анализ для статистики , Тексты по статистическим наукам (1-е изд.), Чепмен и Холл / CRC, ISBN 978-1420095388
Бисгард, Джеймс (2021). Анализ и линейная алгебра: разложение по сингулярным значениям и приложения . Студенческая математическая библиотека (1-е изд.). АМС. ISBN 978-1-4704-6332-8 .
Чикко, Д; Массероли, М (2015). «Программный пакет для прогнозирования аннотаций генов и белков и поиска сходства» . Транзакции IEEE/ACM по вычислительной биологии и биоинформатике . 12 (4): 837–843. дои : 10.1109/TCBB.2014.2382127 . hdl : 11311/959408 . ПМИД 26357324 . S2CID 14714823 .
Трефетен, Ллойд Н .; Бау III, Дэвид (1997). Численная линейная алгебра . Филадельфия: Общество промышленной и прикладной математики. ISBN 978-0-89871-361-9 .
Деммель, Джеймс ; Кахан, Уильям (1990). «Точные сингулярные значения двудиагональных матриц». Журнал SIAM по научным и статистическим вычислениям . 11 (5): 873–912. CiteSeerX 10.1.1.48.3740 . дои : 10.1137/0911052 .
Голуб, Джин Х .; Кахан, Уильям (1965). «Вычисление сингулярных значений и псевдообратной матрицы». Журнал Общества промышленной и прикладной математики, серия B: Численный анализ . 2 (2): 205–224. Бибкод : 1965SJNA....2..205G . дои : 10.1137/0702016 . JSTOR 2949777 .
Голуб, Джин Х .; Ван Лоан, Чарльз Ф. (1996). Матричные вычисления (3-е изд.). Джонс Хопкинс. ISBN 978-0-8018-5414-9 .
Команда GSL (2007). «§14.4 Разложение по сингулярным значениям» . Научная библиотека ГНУ. Справочное руководство .
Халлдор, Бьернссон и Венегас, Сильвия А. (1997). «Руководство по анализу климатических данных EOF и SVD» . Университет Макгилла, Отчет CCGCR № 97-1, Монреаль, Квебек, 52 стр.
Хансен, ПК (1987). «Усеченный СВД как метод регуляризации». КУСОЧЕК . 27 (4): 534–553. дои : 10.1007/BF01937276 . S2CID 37591557 .
Хорн, Роджер А.; Джонсон, Чарльз Р. (1985). «Раздел 7.3». Матричный анализ . Издательство Кембриджского университета. ISBN 978-0-521-38632-6 .
Хорн, Роджер А.; Джонсон, Чарльз Р. (1991). "Глава 3" . Темы матричного анализа . Издательство Кембриджского университета. ISBN 978-0-521-46713-1 .
Самет, Х. (2006). Основы многомерных и метрических структур данных . Морган Кауфманн. ISBN 978-0-12-369446-1 .
Стрэнг Г. (1998). «Раздел 6.7». Введение в линейную алгебру (3-е изд.). Уэлсли-Кембридж Пресс. ISBN 978-0-9614088-5-5 .
Стюарт, GW (1993). «О ранней истории разложения сингулярных значений» . Обзор СИАМ . 35 (4): 551–566. CiteSeerX 10.1.1.23.1831 . дои : 10.1137/1035134 . HDL : 1903/566 . JSTOR 2132388 .
Уолл, Майкл Э.; Рехтштайнер, Андреас; Роча, Луис М. (2003). «Разложение по сингулярным значениям и анализ главных компонент» . В ДП Беррар; В. Дубицкий; М. Гранцов (ред.). Практический подход к анализу данных микрочипов . Норвелл, Массачусетс: Клювер. стр. 91–109.
Пресс, WH; Теукольский, С.А.; Феттерлинг, WT; Фланнери, BP (2007), «Раздел 2.6» , Численные рецепты: искусство научных вычислений (3-е изд.), Нью-Йорк: Cambridge University Press, ISBN 978-0-521-88068-8

Внешние ссылки [ править ]

Онлайн калькулятор СВД

[1] ДеАнджелис, GC; Одзава, И.; Фриман, Р.Д. (октябрь 1995 г.). «Динамика рецептивных полей в центральных зрительных путях». Тенденции нейробиологии . 18 (10): 451–8. дои : 10.1016/0166-2236(95)94496-Р . ПМИД 8545912 . S2CID 12827601 .

[2] Депирё, Д.А.; Саймон, Джей Зи; Кляйн, диджей; Шамма, SA (март 2001 г.). «Характеристика спектрально-временного поля реакции с динамическими пульсациями в первичной слуховой коре хорька». Дж. Нейрофизиология . 85 (3): 1220–34. дои : 10.1152/jn.2001.85.3.1220 . ПМИД 11247991 .

[3] Разложение по сингулярным значениям при симметричной (Lowdin) ортогонализации и сжатии данных

[4] Сахидулла, штат Мэриленд; Киннунен, Томи (март 2016 г.). «Функции локальной спектральной изменчивости для проверки динамиков» . Цифровая обработка сигналов . 50 : 1–11. дои : 10.1016/j.dsp.2015.10.011 .

[Mademlis2018-5] Мадемлис, Иоаннис; Тефас, Анастасиос; Питас, Иоаннис (2018). «Регуляризованная значимость видеокадров на основе SVD для обобщения видео неконтролируемых действий». Международная конференция IEEE по акустике, речи и обработке сигналов (ICASSP) 2018 г. IEEE. стр. 2691–2695. дои : 10.1109/ICASSP.2018.8462274 . ISBN 978-1-5386-4658-8 . S2CID 52286352 . Проверено 19 января 2023 г.

[6] О. Альтер, П.О. Браун и Д. Ботштейн (сентябрь 2000 г.). «Разложение по сингулярным значениям для обработки и моделирования данных полногеномной экспрессии» . ПНАС . 97 (18): 10101–10106. Бибкод : 2000PNAS...9710101A . дои : 10.1073/pnas.97.18.10101 . ПМК 27718 . ПМИД 10963673 .

[7] О. Альтер; Голубь Г.Х. (ноябрь 2004 г.). «Интегративный анализ данных в масштабе генома с использованием псевдообратной проекции предсказывает новую корреляцию между репликацией ДНК и транскрипцией РНК» . ПНАС . 101 (47): 16577–16582. Бибкод : 2004PNAS..10116577A . дои : 10.1073/pnas.0406767101 . ПМК 534520 . ПМИД 15545604 .

[8] О. Альтер; Голубь Г.Х. (август 2006 г.). «Разложение по сингулярным значениям распределения длин мРНК в масштабе генома выявляет асимметрию в расширении полосы гель-электрофореза РНК» . ПНАС . 103 (32): 11828–11833. Бибкод : 2006PNAS..10311828A . дои : 10.1073/pnas.0604756103 . ПМЦ 1524674 . ПМИД 16877539 .

[9] Бертаньолли, Нью-Мексико; Дрейк, Дж.А.; Теннессен, Дж. М.; Альтер, О. (ноябрь 2013 г.). «SVD идентифицирует функции распределения длины транскрипта на основе данных микрочипов ДНК и выявляет эволюционные силы, глобально влияющие на метаболизм ГБМ» . ПЛОС ОДИН . 8 (11): е78913. Бибкод : 2013PLoSO...878913B . дои : 10.1371/journal.pone.0078913 . ПМЦ 3839928 . ПМИД 24282503 . Выделять .

[10] Эдельман, Алан (1992). «О распределении масштабированного числа состояния» (PDF) . Математика. Комп . 58 (197): 185–190. Бибкод : 1992MaCom..58..185E . дои : 10.1090/S0025-5718-1992-1106966-2 .

[11] Шен, Цзяньхун (Джеки) (2001). «Об сингулярных значениях гауссовских случайных матриц» . Линейный Алг. Приложение . 326 (1–3): 1–14. дои : 10.1016/S0024-3795(00)00322-0 .

[12] Уолтон, С.; Хасан, О.; Морган, К. (2013). «Моделирование пониженного порядка нестационарного потока жидкости с использованием правильного ортогонального разложения и радиальных базисных функций» . Прикладное математическое моделирование . 37 (20–21): 8930–8945. дои : 10.1016/j.apm.2013.04.025 .

[13] Сетьявати, Ю.; Оме, Ф.; Хан, С. (2019). «Улучшение модели гравитационных сигналов посредством динамической калибровки». Физический обзор D . 99 (2): 024010. arXiv : 1810.07060 . Бибкод : 2019PhRvD..99b4010S . дои : 10.1103/PhysRevD.99.024010 . S2CID 118935941 .

[14] Сарвар, Бадрул; Карипис, Георгий; Констан, Джозеф А. и Ридл, Джон Т. (2000). «Применение уменьшения размерности в рекомендательной системе – практический пример» (PDF) . Университет Миннесоты . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )

[15] Босах Заде, Реза; Карлссон, Гуннар (2013). «Квадрат матрицы, не зависящий от измерения, с использованием MapReduce» (PDF) . arXiv : 1304.1467 . Бибкод : 2013arXiv1304.1467B . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )

[16] Хади Фанаи Торк; Жоау Гама (сентябрь 2014 г.). «Метод собственного пространства для обнаружения пространственно-временных горячих точек». Экспертные системы . 32 (3): 454–464. arXiv : 1406.3506 . Бибкод : 2014arXiv1406.3506F . дои : 10.1111/exsy.12088 . S2CID 15476557 .

[17] Хади Фанаи Торк; Жоау Гама (май 2015 г.). «EigenEvent: алгоритм обнаружения событий из сложных потоков данных при синдромном наблюдении». Интеллектуальный анализ данных . 19 (3): 597–616. arXiv : 1406.3496 . дои : 10.3233/IDA-150734 . S2CID 17966555 .

[muralidharan2023stretching-18] Муралидхаран, Вивек; Хауэлл, Кэтлин (2023). «Направления растяжения в окололунном пространстве: Заявки на вылеты и проектирование трансферов». Астродинамика . 7 (2): 153–178. Бибкод : 2023AsDyn...7..153M . дои : 10.1007/s42064-022-0147-z . S2CID 252637213 .

[Muralidharan2021-19] Муралидхаран, Вивек; Хауэлл, Кэтлин (2022). «Использование направлений растяжения для поддержания положения на галоорбитах Земля-Луна». Достижения в космических исследованиях . 69 (1): 620–646. Бибкод : 2022AdSpR..69..620M . дои : 10.1016/j.asr.2021.10.028 . S2CID 239490016 .

[20] Чтобы увидеть это, нам просто нужно заметить, что $\operatorname {Tr} (\mathbf {V} _{2}^{*}\mathbf {M} ^{*}\mathbf {M} \mathbf {V} _{2})=\|\mathbf {M} \mathbf {V} _{2}\|^{2}$ и помни это $\|A\|=0\Leftrightarrow A=0$ .

[21] Райк, PPM де (1989). «Односторонний алгоритм Якоби для вычисления разложения по сингулярным значениям на векторном компьютере». СИАМ J. Sci. Стат. Вычислить . 10 : 359.

[22] Netlib.org

[23] Netlib.org

[24] thworks.co.kr/matlabcentral/fileexchange/12674-simple-svd

[25] Деммель, Джеймс (2000). «Разложения» . Шаблоны для решения алгебраических задач на собственные значения . Бай, Чжаоцзюнь; Деммель, Джеймс; Донгарра, Джек Дж.; Руэ, Аксель; ван дер Ворст, Хенк А. Общество промышленной и прикладной математики. дои : 10.1137/1.9780898719581 . ISBN 978-0-89871-471-5 .

[26] Чикко, Д; Массероли, М (2015). «Программный пакет для прогнозирования аннотаций генов и белков и поиска сходства» . Транзакции IEEE/ACM по вычислительной биологии и биоинформатике . 12 (4): 837–843. дои : 10.1109/TCBB.2014.2382127 . hdl : 11311/959408 . ПМИД 26357324 . S2CID 14714823 .

[27] Фан, Кентукки (1951). «Максимальные свойства и неравенства для собственных значений вполне непрерывных операторов» . Труды Национальной академии наук Соединенных Штатов Америки . 37 (11): 760–766. Бибкод : 1951PNAS...37..760F . дои : 10.1073/pnas.37.11.760 . ПМЦ 1063464 . ПМИД 16578416 .

[28] Ульманн, Джеффри (2018), Обобщенная обратная матрица, согласующаяся с диагональными преобразованиями (PDF) , SIAM Journal on Matrix Analysis, vol. 239, стр. 781–800, заархивировано из оригинала (PDF) 7 марта 2019 г.

[29] Эккарт, К .; Янг, Г. (1936). «Приближение одной матрицы другой меньшего ранга». Психометрика . 1 (3): 211–8. дои : 10.1007/BF02288367 . S2CID 10163399 .

[30] Хестенес, MR (1958). «Обращение матриц путем биортогонализации и связанные с этим результаты». Журнал Общества промышленной и прикладной математики . 6 (1): 51–90. дои : 10.1137/0106005 . JSTOR 2098862 . МР 0092215 .

[31] ( Голуб и Кахан 1965 )

[32] Голуб, GH ; Рейнш, К. (1970). «Разложение по сингулярным значениям и решения методом наименьших квадратов». Нумерическая математика . 14 (5): 403–420. дои : 10.1007/BF02163027 . МР 1553974 . S2CID 123532178 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

v т Это Численная линейная алгебра
Key concepts	Floating point Numerical stability
Problems	System of linear equations Matrix decompositions Matrix multiplication (algorithms) Matrix splitting Sparse problems
Hardware	CPU cache TLB Cache-oblivious algorithm SIMD Multiprocessing
Software	ATLAS MATLAB Basic Linear Algebra Subprograms (BLAS) LAPACK Specialized libraries General purpose software

v т Это Спектральная теория и ^*-алгебры
Basic concepts	Involution/-algebra Banach algebra B-algebra C-algebra Noncommutative topology Projection-valued measure Spectrum Spectrum of a C-algebra Spectral radius Operator space
Main results	Gelfand–Mazur theorem Gelfand–Naimark theorem Gelfand representation Polar decomposition Singular value decomposition Spectral theorem Spectral theory of normal C*-algebras
Special Elements/Operators	Isospectral Normal operator Hermitian/Self-adjoint operator Unitary operator Unit
Spectrum	Krein–Rutman theorem Normal eigenvalue Spectrum of a C*-algebra Spectral radius Spectral asymmetry Spectral gap
Decomposition	Decomposition of a spectrum Continuous Point Residual Approximate point Compression Direct integral Discrete Spectral abscissa
Spectral Theorem	Borel functional calculus Min-max theorem Positive operator-valued measure Projection-valued measure Riesz projector Rigged Hilbert space Spectral theorem Spectral theory of compact operators Spectral theory of normal C*-algebras
Special algebras	Amenable Banach algebra With an Approximate identity Banach function algebra Disk algebra Nuclear C*-algebra Uniform algebra Von Neumann algebra Tomita–Takesaki theory
Finite-Dimensional	Alon–Boppana bound Bauer–Fike theorem Numerical range Schur–Horn theorem
Generalizations	Dirac spectrum Essential spectrum Pseudospectrum Structure space (Shilov boundary)
Miscellaneous	Abstract index group Banach algebra cohomology Cohen–Hewitt factorization theorem Extensions of symmetric operators Fredholm theory Limiting absorption principle Schröder–Bernstein theorems for operator algebras Sherman–Takeda theorem Unbounded operator
Examples	Wiener algebra
Applications	Almost Mathieu operator Corona theorem Hearing the shape of a drum (Dirichlet eigenvalue) Heat kernel Kuznetsov trace formula Lax pair Proto-value function Ramanujan graph Rayleigh–Faber–Krahn inequality Spectral geometry Spectral method Spectral theory of ordinary differential equations Sturm–Liouville theory Superstrong approximation Transfer operator Transform theory Weyl law Wiener–Khinchin theorem

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