Разговор о SVD-разложении матриц

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

В этой статье мы говорим о SVD-разложении матриц.

некоторые знания матрицы

Во-первых, давайте рассмотрим некоторые базовые знания о матрицах.

Транспонирование и сопряженное транспонирование

Транспонирование матрицы — простейший вид матричного преобразования. Проще говоря, если $m\times n$ матрица $\mathbf M$ Транспонирование записывается как $\mathbf M^{\mathsf T}$ ;но $\mathbf M^{\mathsf T}$ Является $n\times m$ матрица и $\mathbf M_{i,j} = \mathbf M^{\mathsf T}_{j,i}$ .

Поэтому транспонирование матрицы равносильно переворачиванию матрицы по главной диагонали, при этом нетрудно получить $\mathbf M = \bigl(\mathbf M^{\mathsf T}\bigr)^{\mathsf T}$ .

Сопряженное транспонирование матрицы, вероятно, является предпоследним простейшим матричным преобразованием. Сопряженное транспонирование нужно только наложить сопряженное комплексного числа на основе транспонирования. Следовательно, если $\mathbf M^{\mathsf H}$ матрица заметок $\mathbf M$ Сопряженное транспонирование , то мы имеем $\mathbf M_{i,j} = \overline{\bigl(\mathbf M^{\mathsf H}\bigr)_{j,i}}$ .

Унитарная матрица

Унитарная матрица — это особый вид квадратной матрицы, удовлетворяющий условию

U UH =U H U= In .

U U H =U H U =I n .

Нетрудно заметить, что унитарная матрица на самом деле является обобщенной ортогональной матрицей; когда все элементы унитарной матрицы являются действительными числами, унитарная матрица на самом деле является ортогональной матрицей. С другой стороны, поскольку унитарная матрица $\mathbf U$ удовлетворить $\mathbf U^{-1} = \mathbf U^{\mathsf H}$ , на самом деле это необходимое и достаточное условие унитарности матрицы.

нормальная матрица

Как и унитарная матрица, нормальная матрица также является специальной квадратной матрицей, которая требуется для удовлетворения коммутативного закона с ее сопряженной транспонированной матрицей в смысле матричного умножения. То есть, если матрица $\mathbf M$ Если выполняются следующие условия, она называется нормальной матрицей:

M MH =M H M.

M M H =M H M .

Очевидно, что унитарная матрица комплексных коэффициентов и ортогональная матрица действительных коэффициентов являются нормальными матрицами. Очевидно, нормальные матрицы — это не только унитарные матрицы или ортогональные матрицы. Например, матрица $\mathbf M = \begin{pmatrix}1 & 1 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1\end{pmatrix}$ — нормальная матрица, но явно не унитарная и не ортогональная матрица, поскольку

M MH =( 2 11 1 21 1 12 ) =M H M.

Спектральная теорема и спектральное разложение

Диагонализация матриц - важное предложение линейной алгебры. Спектральная теорема дает результат диагонализации квадратных матриц: если матрица $\mathbf M$ — нормальная матрица, то существует унитарная матрица $\mathbf U$ , а диагональная матрица $\mathbf \Lambda$ , так что

M =UΛ UH .

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

разложение СВД

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

Что говорит разложение SVD: предположим $\mathbf M$ Является $m\times n$ матрица, все элементы которой принадлежат числовому полю $\mathbb K$ (поле реального числа $\mathbb R$ или сложное поле $\mathbb C$ ). Ну, есть $m\times m$ унитарная матрица $\mathbf U$ и $n\times n$ унитарная матрица $\mathbf V$ сделать

M =UΣ VH ,

в $\mathbf\Sigma$ да $m\times n$ неотрицательная действительная диагональная матрица , и $\mathbf\Sigma$ элементы по диагонали $\mathbf\Sigma_{i, i}$ да $\mathbf M$ единственное значение . В общем, мы предпочитаем располагать эти сингулярные значения в порядке убывания, чтобы $\mathbf\Sigma$ На $\mathbf M$ Только уверен.

С другой стороны, поскольку $\mathbf U$ и $\mathbf V$ все матрицы унитарные, поэтому $\mathbf U$ и $\mathbf V$ Векторы-столбцы , соответственно, растянуты в $\mathbb K^{m}$ и $\mathbb K^{n}$ набор стандартных ортонормированных базисов. мы будем $\mathbf U$ Вектор-столбец $\vec u_i,\; 1 \leqslant i\leqslant m$ ;будет $\mathbf V$ Вектор-столбец $\vec v_j,\; 1\leqslant j\leqslant n$ ; в то же время, $\mathbf\Sigma$ по диагоналиэлементы обозначены $\sigma_k,\; 1\leqslant k\leqslant\min(m,n)$ . Тогда разложение SVD может фактически преобразовать матрицу $\mathbf M$ написать итоговую форму

M = мин (m,n) ∑ я знак равно 1 σi→ ты я→ v Т я .

Метод расчета СВД

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

SVD и собственные значения

Теперь предположим, что матрица $\mathbf M_{m\times n}$ Разложение SVD

M =UΣ VH ;

Тогда у нас есть

M MH =UΣV H VΣ H UH =U (ΣΣ H )U H M H M =V ΣH U H UΣ VH =V (Σ H Σ) VH

То есть, $\mathbf U$ Вектор-столбец (левый сингулярный вектор) , равен $\mathbf M\mathbf M^{\mathsf H}$ собственные векторы ; в то же время, $\mathbf V$ Вектор-столбец (правый сингулярный вектор) , равен $\mathbf M^{\mathsf H}\mathbf M$ собственные векторы , с другой стороны, $\mathbf M$ Сингулярные значения ( $\mathbf\Sigma$ ненулевые диагональные элементы ), то $\mathbf M\mathbf M^{\mathsf H}$ или $\mathbf M^{\mathsf H}\mathbf M$ Квадратный корень из ненулевых собственных значений .

Как рассчитать СВД

Вооружившись этими знаниями, мы можем вручную вычислить SVD-разложение любой матрицы; в частности, алгоритм выглядит следующим образом:

рассчитать $\mathbf M\mathbf M^{\mathsf H}$ и $\mathbf M^{\mathsf H}\mathbf M$ ;
Рассчитать отдельно $\mathbf M\mathbf M^{\mathsf H}$ и $\mathbf M^{\mathsf H}\mathbf M$ собственные векторы и их собственные значения;
$\mathbf M\mathbf M^{\mathsf H}$ Собственные векторы $\mathbf U$ ;и $\mathbf M^{\mathsf H}\mathbf M$ Собственные векторы $\mathbf V$ ;
правильно $\mathbf M\mathbf M^{\mathsf H}$ и $\mathbf M^{\mathsf H}\mathbf M$ Квадратный корень из ненулевого собственного значения , соответствующего положению вышеупомянутого собственного вектора, заполните $\mathbf\Sigma$ диагональный элемент .

Ознакомьтесь с фактическим расчетом

Теперь попробуем вычислить сингулярное разложение . Рассчитать разложение по сингулярным числам, нужно рассчитать $\mathbf M$ Лево-правое произведение его сопряженного транспонирования; здесь мы в основном используем $\mathbf M\mathbf M^{\mathsf H}$ Например.

Во-первых, нам нужно рассчитать $\mathbf M\mathbf M^{\mathsf H}$ ,

W =MM H =[ 2 4 1 3 0 0 0 0 ] [ 2 10 0 4 30 0 ] =[ 20 140 0 14 100 0 0 00 0 0 00 0 ] .

Теперь мы просим $\mathbf W$ собственные значения и собственные векторы . По определению $\mathbf W\vec x = \lambda \vec x$ ;следовательно $(\mathbf W - \lambda\mathbf I)\vec x = \vec 0$ . Это означает, что

[ 20 −λ14 00 14 10−λ 00 0 0− λ 0 0 00 −λ ] → Икс =→ 0 .

Согласно теории линейных уравнений, если $\vec x$ Если уравнение имеет ненулевое решение, определитель матрицы коэффициентов должен быть равен 0, т. е.

|20 −λ14 00 14 10−λ 00 0 0− λ 0 0 00 −λ |=|20 −λ14 14 10−λ ||− λ 0 0 −λ |=0 ,

Это $\bigl((20 - \lambda)(10 - \lambda) - 196\bigr)\lambda^2 = 0$ ;Решения должны $\lambda_{1} = \lambda_{2} = 0$ , $\lambda_{3} = 15 + \sqrt{221} \approx 29.866$ , $\lambda_{4} = 15 - \sqrt{221} \approx 0.134$ . Подставьте собственные значения в исходное уравнение, и соответствующие собственные векторы могут быть решены; эти собственные векторы используются в качестве векторов-столбцов для формирования матрицы

U =[ − 0,82 − 0,58 00 − 0,58 0,8200 0 01 0 0 00 1 ] .

То же можно понять (заметим, что $\mathbf M\mathbf M^{\mathsf T}$ и $\mathbf M^{\mathsf T}\mathbf M$ собственные значения одинаковы)

V знак равно [ - 0,40 - 0,91 - 0,91 0,40 ] .

а также $\mathbf\Sigma$ Диагональные элементы на задаются выражением $\mathbf W$ состоит из арифметических квадратных корней собственных значений , таким образом, существует

Σ =[ 5.46 0 0 0.37 0 0 0 0 ] .

Итак, мы получаем матрицу $\mathbf M$ Разложение SVD (численно аппроксимировано):

[ 2 4 1 3 0 0 0 0 ] ≈ [ - 0,82 - 0,58 00 - 0,58 0,82 00 0 01 0 0 00 1 ] [ 5,46 0 0 0,37 0 0 0 0 ] [ - 0,40 - 0,91 - 0,91 0,40 ]

Интуитивная интерпретация геометрии

Сначала рассмотрим пример. Предположение $\mathbf M$ Является $m\times n$ матрица и $\mathbf x$ это линейное пространство $\mathbb K^n$ вектор в , то

у =М⋅х

это линейное пространство $\mathbb K^m$ вектор в . Таким образом, матрица $\mathbb A$ соответствует от $\mathbb K^n$ прибыть $\mathbb K^m$ преобразование $T: \mathbb K^n \to \mathbb K^m$ , точнее оба $\mathbf x\mapsto \mathbf M\cdot\mathbf x$ .

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

Преобразование вращения и преобразование отражения (зеркало)

Вращение в линейном пространстве фактически меняет направление вектора, но не меняет длину и хиральность вектора. Теперь предположим, что матрица $\mathbf M_{n\times n}$ это линейное пространство $\mathbf R^{n}$ Матрица, соответствующая преобразованию поворота в , посмотрим, как она должна выглядеть.

Во-первых, мы рассматриваем векторный скалярный продукт $\vec a\cdot\vec b = \lvert\vec a\rvert\lvert\vec b\rvert\cos\langle\vec a,\vec b\rangle$ . Потому что поворот не меняет длину вектора, а угол между двумя векторами остается неизменным после такого же поворота. Следовательно, если $\mathbf M$ Соответственно преобразованию вращения, должно быть

→ а ⋅→ б = М → а ⋅ М → б ,

это

→ а ⋅→ б Т = М → а ⋅ ( М → б )Т ,

Это означает, что $\mathbf M\mathbf M^{\mathsf T} = \mathbf I_{n}$ ,это $\mathbf M$ является ортогональной матрицей.

Поэтому для двумерного случая $\mathbf M$ могу написать $\begin{bmatrix}\cos\varphi & -\sin\varphi \\ \sin\varphi & \cos\varphi\end{bmatrix}$ или $\begin{bmatrix}\cos\varphi & \sin\varphi \\ \sin\varphi & -\cos\varphi\end{bmatrix}$ . Бывший определительПоследний определитель. теперь, когда $\mathbf M$ является ортогональной матрицей, то значение ее определителя должно быть $\pm 1$ . Проблема в том, что определительиКакая из них ротация? Или оба вращаются?

Оглядываясь назад, мы должны обратить внимание на две вещи. Во-первых, в определении вращения мы предполагаем, что вращение сохраняет «хиральность»; во-вторых, в процессе вывода о том, что матрица вращения является ортогональной матрицей, мы не использовали свойство «хиральности-инвариантности», поскольку $\cos\langle\vec a,\vec b\rangle = \cos\langle\vec b,\vec a\rangle$ .

На самом деле, если $\mathbf M$ Определитель, то матрица соответствует ошибочному вращению — сначала повернуть $\varphi$ Затем нажмите прямую линию $r = k\varphi$ зеркало. учитывать $\varphi - \alpha = 2\varphi - (\varphi + \alpha)$ , это вращение дефекта по существу представляет собой прямую линию $r = k(\varphi / 2)$ зеркало.

Поэтому мы говорим, что матрица вращения является определителемявляется положительно определенной матрицей вида

[ cos φ− sin φ sin φ cos φ ] ,

Указывает на вращение в положительном направлении (обычно против часовой стрелки) $\varphi$ . за $\mathbb R^{2}$ Стандартный ортогональный базис на $\begin{bmatrix}1 \\ 0\end{bmatrix}$ , $\begin{bmatrix}0 \\ 1\end{bmatrix}$ , они превращаются в $\begin{bmatrix}\cos\varphi \\ \sin\varphi\end{bmatrix}$ и $\begin{bmatrix}-\sin\varphi \\ \cos\varphi\end{bmatrix}$ .

Определительявляется положительно определенной матрицей вида

[ cos φsin φ sin φ− cosφ ] ,

Указывает прямую линию $r = k(\varphi / 2)$ зеркало.

масштабное преобразование

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

Геометрическая интерпретация разложения SVD

Теперь оглядываясь назад на разложение СВД

M =UΣ VH ,

Обсуждаем в реальном диапазоне, мы по сути конвертируем сложное преобразование $M:\mathbb R^{m}\to\mathbb R^{n}$ Декомпозируется на три преобразования: поворот/отражение $U:\mathbb R^{m}\to\mathbb R^{m}$ , увеличить $\Sigma:\mathbb R^{m}\to\mathbb R^{n}$ , повернуть/отразить $V:\mathbb R^{n}\to\mathbb R^{n}$ .

Без ограничения общности полагаем m = n а такжеивсе матрицы вращения, то этот процесс можно выразить как

Легко найти, $\mathbf V^{\mathsf H}$ Сначала поверните (возможно, вырожденную) единичную сферу (вращая ортонормированный базис), затем пройдите $\mathbf \Sigma$ Масштабируйте и растяните единичный круг в эллипс (гиперэллипсоид в гиперпространстве), а затем передайте $\mathbf U$ поместить гиперэллипсоид в $\mathbb K^{m}$ вращаться в пространстве. А длина каждой полуоси этого суперэллипсоида есть матрица $\mathbf M$ Сингулярные значения , то есть матрица $\mathbf \Sigma$ Элементы по диагонали.

Приложения разложения SVD

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

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

Следовательно, декомпозиция SVD работает как минимум двумя способами:

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

Применение этих двух аспектов на самом деле двояко: ведь после сортировки по важности, с одной стороны, мы можем знать, какая информация (сингулярные значения) важна, а с другой стороны, я могу естественным образом отбросить неважные части. Здесь мы берем сжатие информации с потерями в качестве примера.

В реальной жизни и на работе большое количество информации может быть представлено в матричной форме. Например: изображение (см.PIL Concise Tutorial — Манипуляции с пикселями и фильтры изображений) информация, огромные матрицы признаков в задачах машинного обучения и т. д. Здесь мы следуем предыдущей траектории и визуально отображаем применение декомпозиции SVD при сжатии графики в виде информации об изображении.

Сначала давайте рассмотрим кота, которого мы видели, он выглядит так:

После разложения SVD сингулярные значения трех каналов RGB соответственно имеют вид (код):

[  8.29754663e+04   1.43568761e+04   8.28098602e+03   7.94075752e+03
   6.87204550e+03   4.64118946e+03   3.07326587e+03   2.64043230e+03
   2.34251575e+03   2.08293043e+03   1.81457650e+03   1.73772694e+03
   1.55535238e+03   1.44987605e+03   1.28556279e+03   1.18657598e+03
   1.15156737e+03   1.10588319e+03   1.04069060e+03   9.63555279e+02
   ...
   2.07308001e+00   2.03810704e+00   2.01670137e+00   1.89766075e+00
   1.78169821e+00]
[  7.52035286e+04   1.45096769e+04   1.02416708e+04   7.99187399e+03
   5.55763091e+03   4.82795595e+03   3.22590281e+03   2.81678573e+03
   2.47269533e+03   2.05484885e+03   1.87922653e+03   1.67558281e+03
   1.55022246e+03   1.48494502e+03   1.30714569e+03   1.19338672e+03
   1.17078655e+03   1.07687752e+03   1.04558020e+03   9.93807772e+02
   ...
   2.08166328e+00   2.03020090e+00   1.95633445e+00   1.88738236e+00
   1.80539295e+00]
[  7.15164941e+04   1.60372342e+04   1.20401757e+04   8.69602152e+03
   5.69604800e+03   3.76913288e+03   3.48390702e+03   3.17683272e+03
   2.73730517e+03   2.32005514e+03   2.08571764e+03   1.76733763e+03
   1.55393096e+03   1.47436741e+03   1.39202168e+03   1.21607022e+03
   1.17991116e+03   1.16377337e+03   1.01255317e+03   9.97811473e+02
   ...
   2.17604369e+00   2.13041080e+00   1.99837012e+00   1.88718778e+00
   1.80040166e+00]

Когда мы усекаем от большого к меньшему, отбрасываем меньшие сингулярные значения и реконструируем изображение, мы получаем «сжатое» изображение.

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

Когда берутся только 5 сингулярных значений, реконструированное изображение выглядит следующим образом. В этот момент изображение кота едва можно было разглядеть.

Замечено, что около 20-го сингулярного значения величина сингулярного значения меняется на порядок (от+03падать до+02). Поэтому при взятии 20 сингулярных значений реконструированное изображение выглядит следующим образом, образ кота в это время уже очень четкий.

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

Точно так же мы можем также наблюдать доступ100/200/300/ 400При наличии сингулярных значений результат получается путем восстановления изображения.

Ваша поддержка - самая большая мотивация для меня, чтобы написать

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