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

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

Начнем с того, что вспомним, что матрицу $M$ размером $m\times n$ также можно рассматривать как линейное преобразование $f\colon\mathbb R^n\to\mathbb R^m$, установив $f(\vec x) :=M\vec x$. Линейные преобразования довольно просты, так как они могут делать только три вещи:

  • Они могут вращать векторы
  • Они могут переворачивать векторы
  • Они могут растягивать/сжимать векторы.

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

Это диагональ, если он растягивается/сжимается только в направлениях осей:

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

Первое разложение, которое мы рассмотрим, собственное разложение, делает это путем выделения набора специальных векторов, которые не поворачиваются и растягиваются/сокращаются на одинаковую величину. во всех направлениях: наше преобразование только потенциально переворачивает и «равномерно» растягивает/сжимает эти специальные. Конечно, это связано со своей загадочной терминологией: эти специальные векторы называются собственными векторами, а величина, на которую они равномерно растягиваются/сжимаются, называется собственными значениями.

Затем декомпозиция сначала поворачивает и потенциально переворачивает заданный вектор, затем растягивает/сжимает его в направлениях осей, поворачивает и потенциально переворачивает его обратно:

Однако есть проблема: это не всегда работает. Во-первых, мы должны предположить, что $M$ является квадратной матрицей, а это означает, что $m=n$, потому что мы делаем то же самое вращение (в обратном порядке) после растяжения/сжатия, и поэтому мы имеем оставаться в одном и том же пространстве.

Быть квадратной матрицей недостаточно, так как мы также требуем, чтобы $M$ была симметричной и положительно полуопределенной (технически достаточно более слабого условия, но мы проигнорирую это здесь, так как SVD позаботится и об этом). Больше жаргона! Давайте посмотрим на них по одному.

Преобразование называется симметричным, если его двукратное применение отменяет все повороты и перевороты; т.е. после второго преобразования остается только растяжение/сжатие:

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

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

Вот точная формулировка собственного разложения:

Теорема (собственное разложение). Пусть $M$ — квадратная матрица, одновременно симметричная и положительно полуопределенная. Тогда существуют ортогональная матрица $Q$ и диагональная матрица $\Lambda$ такие, что $M=Q\Lambda Q^{-1}$.

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

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

Таким образом, разложение говорит о том, что любое преобразование можно разделить на (1) вращение + потенциальное переворачивание, (2) растяжение/сжатие в направлениях осей и (3) другое (потенциально другое) вращение + потенциальное переворачивание.

Вы можете найти крутую интерактивную анимацию разложения здесь. Вот точная формулировка разложения.

Теорема (разложение по сингулярным значениям). Любая вещественнозначная $m\times n$ матрица $M$ может быть записана в виде $M=U\Sigma V^T$, где $U$ и $V$ — ортогональные матрицы размерностей $m\times m$ и $ n\times n$ матрица соответственно, а $\Sigma$ — диагональная матрица $m\times n$. Далее, если мы допустим, что $\sigma_i$ является $i$-м диагональным элементом $\Sigma$, то

где $p:=\min(m,n)$ и $\sigma_i=0$ для всех $i›p$.

Вот и все! С доказательством этой теоремы можно ознакомиться здесь. Следует отметить одну замечательную вещь: когда наше преобразование является одновременно симметричным и полуположительно определенным, тогда SVD и собственное разложение эквивалентны!

Настройтесь в следующий раз, чтобы узнать о некоторых применениях этой декомпозиции в науке о данных!

Первоначально опубликовано на https://saattrupdan.github.io.