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

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

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

В линейной алгебре , то сингулярное разложение ( SVD ) представляет собой разложение из реальной или комплексной матрицы , обобщающая eigendecomposition квадратной нормальной матрицы к любой матрице через расширение полярного разложения .${\ Displaystyle м \ раз п}$

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

Диагональные элементы из известны как сингулярных значений из М . Количество ненулевых сингулярных значений равно ранга из М . Столбцы U и столбцы V называются левые сингулярными векторы и правый сингулярные векторы из М , соответственно.${\ Displaystyle \ sigma _ {я} = \ Sigma _ {ii}}$${\ Displaystyle \ mathbf {\ Sigma}}$

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

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

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

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

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

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

В частном случае, когда M представляет собой вещественную квадратную матрицу размера m × m , матрицы U и V ^{⁎ также} могут быть выбраны как вещественные матрицы размера m × m . В этом случае «унитарный» то же самое, что « ортогональный ». Затем, интерпретируя обе унитарные матрицы, а также диагональную матрицу, обозначенную здесь как A , как линейное преобразование x → Ax пространства R ^m , матрицы U и V ^⁎ представляют вращения или отражение пространства, а представляет собой масштабирование каждой координаты x _i на коэффициент σ _i . Таким образом , разрывы разложения СВД вниз любого обратимого линейного преобразования R ^м в составе трех геометрических преобразований : поворот или отражение ( V ^⁎ ), с последующим координатно-на-координату масштабирования ( ), за которым следует другой поворот или отражение ( U ).${\ Displaystyle \ mathbf {\ Sigma}}$${\ Displaystyle \ mathbf {\ Sigma}}$

В частности, если M имеет положительный определитель, то U и V ^⁎ могут быть выбраны как отражения или оба вращения. Если определитель отрицательный, ровно один из них должен быть отражением. Если определитель равен нулю, каждый может быть независимо выбран как принадлежащий к любому типу.

Если матрица М является реальным , но не квадратным, а именно м × н с т ≠ п , ее можно интерпретировать как линейное преобразование из R ^п к R ^м . Тогда U и V ^⁎ могут быть выбраны как вращения R ^m и R ⁿ соответственно; и , помимо масштабирования первых координат, также расширяет вектор нулями, то есть удаляет конечные координаты, чтобы превратить R ⁿ в R ^m .${\ Displaystyle \ mathbf {\ Sigma}}$${\ Displaystyle \ мин \ {м, п \}}$

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

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

Столбцы U и V являются ортонормированными основаниями [ править ]

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

Геометрическое значение [ править ]

Поскольку U и V является унитарными, мы знаем , что столбцы U ₁ , ..., U _м из U получения ортогонального базиса из K ^м и столбцов V ₁ , ..., V _п из V выход ортогонального базиса K ⁿ (относительно стандартных скалярных произведений на этих пространствах).

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

${\ displaystyle {\ begin {cases} T: K ^ {n} \ to K ^ {m} \\ x \ mapsto \ mathbf {M} x \ end {cases}}}$

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

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

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

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

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

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

Рассмотрим матрицу 4 × 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}}}$

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

${\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]{\boldsymbol {\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}}}$

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

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

${\displaystyle \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 [ править ]

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

${\displaystyle \mathbf {M} {\vec {v}}=\sigma {\vec {u}}\,{\text{ and }}\mathbf {M} ^{*}{\vec {u}}=\sigma {\vec {v}}.}$

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

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

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

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

• М × п матрица М имеет не более р различных особых значений.
• Всегда можно найти унитарный базис U для K ^м с подмножеством базисных векторов , охватывающих левые-сингулярных векторов каждой особой величины М .
• Это всегда можно найти унитарный базис V для K ^п с подмножеством базисных векторов , охватывающих правого сингулярных векторов каждой особой величины М .

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

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

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

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

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

Для SVD M , как описано выше, выполняются следующие два соотношения:

${\displaystyle {\begin{aligned}\mathbf {M} ^{*}\mathbf {M} &=\mathbf {V} {\boldsymbol {\Sigma }}^{*}\mathbf {U} ^{*}\,\mathbf {U} {\boldsymbol {\Sigma }}\mathbf {V} ^{*}=\mathbf {V} ({\boldsymbol {\Sigma }}^{*}{\boldsymbol {\Sigma }})\mathbf {V} ^{*}\\\mathbf {M} \mathbf {M} ^{*}&=\mathbf {U} {\boldsymbol {\Sigma }}\mathbf {V} ^{*}\,\mathbf {V} {\boldsymbol {\Sigma }}^{*}\mathbf {U} ^{*}=\mathbf {U} ({\boldsymbol {\Sigma }}{\boldsymbol {\Sigma }}^{*})\mathbf {U} ^{*}\end{aligned}}}$

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

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

В частном случае, когда M является нормальной матрицей , которая по определению должна быть квадратной, спектральная теорема говорит, что ее можно унитарно диагонализовать с использованием базиса собственных векторов , так что можно записать M = UDU ^⁎ для унитарной матрицы U и диагональная матрица D . Когда M также является положительно полуопределенным , разложение M = UDU ^⁎ также является разложением по сингулярным значениям. В противном случае его можно преобразовать в SVD, сдвинув фазу каждого σ _iлибо его соответствующему V _i, либо U _i . Естественное соединение SVD к ненормальным матрицам через полярное разложение теорему: М  =  SR , где S  =  U U ^⁎ является неотрицательно и нормальным, а R  =  УФ ^⁎ унитарна.${\displaystyle \mathbf {\Sigma } }$

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

Заявления СВД [ править ]

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

Разложение по сингулярным числам может использоваться для вычисления псевдообратной матрицы. (Различные авторы используют разные обозначения для псевдообратной матрицы ; здесь мы используем ^† .) Действительно, псевдообратная матрица M с разложением по сингулярным значениям M = U Σ V ^⁎ имеет вид

M ^† = V Σ ^† U ^⁎

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

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

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

Минимизация общего наименьших квадратов [ править ]

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

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

Другое применение СВД является то , что она дает явное представление диапазона и нулевое пространство матричного М . Правые-сингулярные векторы , соответствующие исчезающий сингулярных значения M охватывают нулевое пространство М и левые-сингулярные векторы , соответствующие сингулярных значения , отличный от нуля в M охватывают диапазон M . Например, в приведенном выше примере нулевое пространство , натянутое на последних двух рядов V ^⁎ и диапазон натянуто на первых трех столбцах U .

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

Аппроксимация матрицы низкого ранга [ править ]

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

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

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

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

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

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

Здесь U _i и V _i - это i-й столбец соответствующих матриц SVD, σ _i - упорядоченные сингулярные значения, и каждое A _i является сепарабельным. SVD можно использовать для нахождения разделения фильтра обработки изображения на отдельные горизонтальные и вертикальные фильтры. Обратите внимание, что количество ненулевых σ _i в точности равно рангу матрицы.

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

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

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

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

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

Аналогичная проблема, с интересными приложениями в анализе формы , является ортогональной проблемой Procrustes , которая заключается в нахождении ортогональной матрица O , которая наиболее близко отображает A в B . Конкретно,

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

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

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

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

Алгоритм Kabsch (называется проблема Вахба в других областях) использует 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]

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

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

Собственное значение λ матрицы M характеризуется алгебраическим соотношением M u = λu . Когда M является эрмитовым , также доступна вариационная характеристика. Пусть M - вещественная симметричная матрица размера n × n . Определять

${\displaystyle {\begin{cases}f:\mathbb {R} ^{n}\to \mathbb {R} \\f(x)=x^{\textsf {T}}\mathbf {M} x\end{cases}}}$

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

${\displaystyle \nabla x^{\textsf {T}}\mathbf {M} x-\lambda \cdot \nabla x^{\textsf {T}}x=0}$

для некоторого действительного числа λ . Символ набла, ∇ , - это оператор дель (дифференцирование по x ). Используя симметрию M, получаем

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

Поэтому М у = Х , так что у является единица длиной собственного вектора M . Для каждой единицу длины собственного вектора V из М его собственное значение равно е ( V ), так что λ является наибольшим собственным значением M . Тот же самый расчет, выполняемый для ортогонального дополнения к u, дает следующее наибольшее собственное значение и так далее. Сложный эрмитов случай аналогичен; там f ( x ) = x * M x является действительной функцией 2 n вещественных переменных.

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

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

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

Пусть - комплексная матрица размера m × n . Поскольку она положительно полуопределенная и эрмитова, по спектральной теореме существует унитарная матрица размера n × n такая, что${\displaystyle \mathbf {M} }$${\displaystyle \mathbf {M} ^{*}\mathbf {M} }$${\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} .}$

Причем из второго уравнения следует . ^[18] Наконец, унитарность выражается в терминах и в следующие условия:${\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 \{\mathbf {M} {\boldsymbol {v}}_{i}\}_{i=1}^{\ell }}$${\displaystyle \{\lambda ^{-1/2}\mathbf {M} {\boldsymbol {v}}_{i}\}_{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 \{\lambda ^{-1/2}\mathbf {M} {\boldsymbol {v}}_{i}\}_{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}}}$

Для V ₁ у нас уже есть V _2, чтобы сделать его унитарным. Теперь определим

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

где дополнительные нулевые строки добавляются или удаляются, чтобы количество нулевых строк равнялось количеству столбцов U ₂ , и, следовательно, общие размеры равны . потом${\displaystyle {\boldsymbol {\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} {\boldsymbol {\Sigma }}\mathbf {V} ^{*}.}$

Обратите внимание , что аргумент может начинаться с диагонализацией ММ ^⁎ , а не M ^⁎ M (это показывает , что непосредственно ММ ^⁎ и M ^⁎ M имеют одинаковые ненулевые собственные значения).

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

Сингулярные значения также могут быть охарактеризованы как максимумы u ^T Mv , рассматриваемые как функция от u и v , на определенных подпространствах. Особые векторы - это значения u и v, при которых достигаются эти максимумы.

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

Рассмотрим функцию σ, ограниченную на S ^{m −1} × S ^{n −1} . Поскольку и S ^{m −1,} и S ^{n −1} являются компактными множествами, их произведение также компактно. Кроме того, поскольку σ непрерывно, оно достигает наибольшего значения по крайней мере для одной пары векторов u ∈ S ^{m −1} и v ∈ S ^{n −1} . Это наибольшее значение обозначается σ _1, а соответствующие векторы обозначаются u₁ и v ₁ . Поскольку σ ₁ является наибольшим значением σ ( u , v ), оно должно быть неотрицательным. Если бы он был отрицательным, изменение знака u ₁ или v ₁ сделало бы его положительным и, следовательно, большим.

Заявление. u ₁ , v ₁ - левый и правый сингулярные векторы M с соответствующим сингулярным значением σ ₁ .

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

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

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

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

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

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

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

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

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

Больше сингулярных векторов и сингулярных значений можно найти, максимизируя σ ( u , v ) по нормализованным u , v, которые ортогональны u ₁ и v ₁ соответственно.

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

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

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

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

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

SVD матрицы M обычно вычисляется с помощью двухэтапной процедуры. На первом этапе матрица сводится к двухдиагональной матрице . Это требует O ( mn ² ) операций с плавающей запятой (flop), предполагая, что m ≥ n . Второй шаг - вычислить SVD двухдиагональной матрицы. Этот шаг можно выполнить только итерационным методом (как и в случае алгоритмов собственных значений ). Однако на практике достаточно вычислить SVD с определенной точностью, как машинный эпсилон . Если эта точность считается постоянной, то второй шаг занимает O ( n ) итераций, каждая из которых стоит O (п ) шлепки. Таким образом, первый шаг дороже, а общая стоимость составляет O ( млн ² ) флопов ( Trefethen & Bau III 1997 , Lecture 31).

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

Второй шаг может быть выполнен с помощью варианта QR-алгоритма для вычисления собственных значений, который впервые был описан Голубом и Каханом (1965) . LAPACK подпрограммы DBDSQR ^[19] реализует этот итерационный метод, с некоторыми изменениями , чтобы покрыть случай , когда особые значения очень малы ( Demmel & Каган 1990 ). Вместе с первым шагом с использованием отражений Хаусхолдера и, при необходимости, QR-разложения, это формирует процедуру DGESVD ^[20] для вычисления разложения по сингулярным значениям. harvtxt error: multiple targets (2×): CITEREFGolubKahan1965 (help)

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

Существует альтернативный способ, в котором явно не используется разложение по собственным значениям. ^[21] Обычно проблема сингулярных чисел матрицы M преобразуется в эквивалентную симметричную задачу на собственные значения, такую ​​как MM ^⁎ , M ^⁎ M или

${\displaystyle {\begin{pmatrix}\mathbf {O} &\mathbf {M} \\\mathbf {M} ^{*}&\mathbf {O} \end{pmatrix}}.}$

Подходы, использующие разложение на собственные значения, основаны на алгоритме QR , который хорошо разработан, чтобы быть стабильным и быстрым. Обратите внимание, что сингулярные значения являются действительными, а правые и левые сингулярные векторы не требуются для формирования преобразований подобия. Можно итеративно переключаться между QR-разложением и LQ-разложением, чтобы найти действительные диагональные эрмитовы матрицы . QR - разложение дает M ⇒ Q R и разложение LQ из R дает R ⇒ L P ^⁎ . Таким образом, на каждой итерации M⇒ Q L P ^⁎ , обновить M ⇐ L и повторить ортогонализации. В конце концов, эта итерация между QR-разложением и LQ-разложением дает левую и правую унитарные сингулярные матрицы. Этот подход нельзя легко ускорить, поскольку алгоритм QR может иметь спектральные сдвиги или дефляцию. Это связано с тем, что метод сдвига нелегко определить без использования преобразований подобия. Однако этот итеративный подход очень просто реализовать, поэтому он является хорошим выбором, когда скорость не имеет значения. Этот метод также дает представление о том, как чисто ортогональные / унитарные преобразования могут получить SVD.

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

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

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

${\displaystyle {\begin{aligned}\sigma _{\pm }&={\sqrt {|z_{0}|^{2}+|z_{1}|^{2}+|z_{2}|^{2}+|z_{3}|^{2}\pm {\sqrt {(|z_{0}|^{2}+|z_{1}|^{2}+|z_{2}|^{2}+|z_{3}|^{2})^{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, включая полное унитарное разложение нулевого пространства матрицы. Вместо этого часто бывает достаточно (а также быстрее и экономичнее для хранения) вычислить сокращенную версию SVD. Для матрицы M размера m × n ранга r можно выделить следующее :

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

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

Вычисляются только n векторов-столбцов U, соответствующих векторам-строкам V * . Остальные векторы-столбцы U не вычисляются. Это значительно быстрее и экономичнее , чем полный СВД , если п  «  м . Таким образом, матрица U _{' n} имеет размер m × n , Σ _n - диагональ n × n , а V - n × n .

Первый этап при расчете тонкой SVD обычно будет QR - разложение на М , который может сделать для значительно быстрее расчета , если  п  «  м .

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

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

Вычисляются только r векторов-столбцов U и r векторов-строк V *, соответствующих ненулевым сингулярным значениям Σ _r . Остальные векторы U и V * не вычисляются. Это быстрее и экономичнее, чем тонкий СВД, если r  ≪  n . Таким образом, матрица U _r имеет размер m × r , Σ _r - диагональ r × r , а V _r * - размер r × n .

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

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

Вычисляются только t векторов-столбцов U и t векторов-строк V *, соответствующих t наибольшим сингулярным значениям Σ _t . Остальная часть матрицы отбрасывается. Это может быть гораздо быстрее и экономичнее , чем компактный СВД , если т « г . Таким образом, матрица U _t имеет размер m × t , Σ _t - диагональ t × t , а V _t * - это t × n .

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

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

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

Сумма K наибольших сингулярных значений М является матрица нормы , то Ky вентилятор к -норму М . ^[22]

Первым из норм Ky вентилятора, штат Кентукки вентилятор 1-нормы, является таким же , как оператор норма из М в качестве линейного оператора относительно евклидовых норм К ^м и К ^п . Другими словами, 1-норма Ки Фана - это операторная норма, индуцированная стандартным ℓ ² евклидовым скалярным произведением. По этой причине его еще называют операторной 2-нормой. Нетрудно проверить связь между 1-нормой Ky Fan и сингулярными значениями. В общем случае это верно для ограниченного оператора M в (возможно, бесконечномерных) гильбертовых пространствах

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

Но в матричном случае ( M * M ) ^½ - нормальная матрица , поэтому || М * М || ^½ является наибольшей собственным значением ( M * M ) ^½ , т.е. наибольшего сингулярного значения М .

Последняя из норм Ки Фана, сумма всех сингулярных значений, является следовой нормой (также известной как «ядерная норма»), определяемой соотношением || М || = Tr [( M * M ) ^½ ] (собственные значения M * M - это квадраты сингулярных значений).

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

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

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

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

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

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

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

где σ _я являюсь особым значением М . Это называется норма Фробениуса , Шаттен 2-норма или норма Гильберта-Шмидт из М . Непосредственный расчет показывает, что норма Фробениуса M = ( m _ij ) совпадает с:

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

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

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

Режим- к представлению [ править ]

${\displaystyle M=USV^{\textsf {T}}}$могут быть представлены с использованием Режим- K умножение матрицы , применяя затем на результат; то есть . ^[23]${\displaystyle S}$${\displaystyle \times _{1}U}$${\displaystyle \times _{2}V}$${\displaystyle M=S\times _{1}U\times _{2}V}$

Тензор СВД [ править ]

Существуют два типа тензорных разложений, которые обобщают SVD на многоходовые массивы. Один из них разбивает тензор на сумму тензоров ранга 1, что называется разложением тензорного ранга . Второй тип разложения вычисляет ортонормированные подпространства, связанные с различными факторами, появляющимися в тензорном произведении векторных пространств, в которых живет тензор. Это разложение упоминается в литературе как SVD высшего порядка (HOSVD) или Tucker3 / TuckerM . Кроме того, полилинейный анализ главных компонент в обучении полилинейных подпространств включает в себя те же математические операции, что и разложение Таккера, которое используется в другом контексте уменьшения размерности..

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

Особые значения матрицы А однозначно определены и инвариантны относительно левой и / или правой унитарных преобразований A . Другими словами, сингулярные значения БЛА , для унитарного U и V , равны сингулярных значений А . Это важное свойство для приложений, в которых необходимо сохранять евклидовы расстояния и инвариантность относительно вращений.

Масштабно-инвариантными СВД, или СИ-СВД, ^[24] аналогично обычному SVD за исключением того, что его уникально определяется сингулярные значения инвариантны относительно диагональных преобразований A . Другими словами, особые значения DAE , для невырожденной диагональной матрицы D и Е , равны сингулярных значений А . Это важное свойство для приложений, для которых требуется инвариантность к выбору единиц измерения переменных (например, метрических единиц по сравнению с британскими).

SVD функций высшего порядка (HOSVD) - численная реконструкция - преобразование модели TP [ править ]

Преобразование модели TP численно восстанавливает HOSVD функций. Для получения дополнительной информации посетите:

• Каноническая форма функций TP и моделей qLPV на основе HOSVD
• Трансформация модели тензорного продукта
• Преобразование модели ТП в теории управления

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

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

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

где есть умножение на F на L ² ( X , μ ).${\displaystyle T_{f}}$

Это можно показать, имитируя линейный алгебраический аргумент для матричного случая выше. VT _f V * - это единственный положительный квадратный корень из M * M , заданный функциональным исчислением Бореля для самосопряженных операторов . Причина, по которой U не обязательно должен быть унитарным, заключается в том, что, в отличие от конечномерного случая, для данной изометрии U ₁ с нетривиальным ядром может не быть найден подходящий U ₂ такой, что

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

- унитарный оператор.

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

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

и обратите внимание, что UV * все еще является частичной изометрией, в то время как VT _f V * положительно.

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

Понятие сингулярных значений и левых / правых сингулярных векторов может быть расширено до компактного оператора в гильбертовом пространстве, поскольку они имеют дискретный спектр. Если T компактно, каждое ненулевое λ в его спектре является собственным значением. Кроме того, компактный самосопряженный оператор можно диагонализовать по собственным векторам. Если M компактно, то M ^⁎ M ^тоже . Применяя результат диагонализации, унитарный образ его положительного квадратного корня T _f  имеет набор ортонормированных собственных векторов { e _i }, соответствующих строго положительным собственным значениям { σ _i }. Для любогоψ ∈ 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},}$

где ряд сходится в топологии нормы на H . Обратите внимание, как это похоже на выражение из конечномерного случая. σ _я называются сингулярные значения M . { U е _я } (соотв. { V е _I }) можно считать левым сингулярным (соответственно правой) сингулярные векторы М .

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

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

История [ править ]

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

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

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

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

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

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

• Банерджи, Судипто; Рой, Аниндья (2014), Линейная алгебра и матричный анализ для статистики , Тексты в статистической науке (1-е изд.), Чепмен и Холл / CRC, ISBN 978-1420095388
• Trefethen, Lloyd N .; Бау 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 (2007). «§14.4 Разложение по сингулярным числам» . Научная библиотека GNU. Справочное руководство .
• Халлдор, Бьорнссон и Венегас, Сильвия А. (1997). «Пособие по EOF и SVD анализу климатических данных» . Университет Макгилла, Отчет CCGCR № 97-1, Монреаль, Квебек, 52 стр.
• Хансен, PC (1987). «Усеченный СВД как метод регуляризации». БИТ . 27 (4): 534–553. DOI : 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-е изд.). Wellesley-Cambridge Press. ISBN 978-0-9614088-5-5.
• Стюарт, GW (1993). «К ранней истории разложения сингулярных значений» . SIAM Обзор . 35 (4): 551–566. CiteSeerX  10.1.1.23.1831 . DOI : 10.1137 / 1035134 . hdl : 1903/566 . JSTOR  2132388 .
• Wall, Michael E .; Рехтштайнер, Андреас; Роча, Луис М. (2003). «Сингулярная декомпозиция и анализ главных компонент» . В DP Berrar; В. Дубицкий; М. Гранцов (ред.). Практический подход к анализу данных микрочипов . Norwell, MA: Kluwer. С. 91–109.
• Нажмите, WH; Теукольский С.А.; Феттерлинг, штат Вашингтон; Фланнери, Б.П. (2007), «Раздел 2.6» , Численные рецепты: Искусство научных вычислений (3-е изд.), Нью-Йорк: Cambridge University Press, ISBN 978-0-521-88068-8

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

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