Декомпозиция SVD и демонстрация сжатия изображения.

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

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

Определения и предположения

Вы должны помнить, что если A - это PSD, то все его собственные значения больше или равны нулю, и, как вы, наверное, догадались, если A - это PD, все его собственные значения больше нуля.

Еще один важный факт о матрицах PSD:

Обратите внимание, что этот факт также верен для A * Aᵀ (просто замените Aᵀ на A).

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

Обратите внимание, что если A имеет n строк и m столбцов, A * Aᵀ будет иметь n строк и n столбцов, что означает, что A * Aᵀ всегда является квадратной матрицей.

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

Если вышеизложенное было не так ясно, вот пример

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

Каждую вещественную матрицу A с m строками и n столбцами можно разложить на U * Sigma * Vᵀ
Когда U ортонормирован с m строками и столбцами;
V ^ T ортонормирован с n строками и столбцами;
А Sigma - это диагональная матрица с m строками и n столбцами.

Чтобы получить SVD-разложение матрицы, нам нужно будет выполнить 6 шагов.

  • Вычислить Aᵀ * A.
  • Найдите собственные значения и собственный вектор этой матрицы (если собственные векторы не ортонормированы, используйте процесс Грама Шмидта).
  • Соберите собственные векторы из предыдущего шага и вставьте их в ряды Vᵀ.
  • Извлеките квадратный корень из собственных значений и вставьте их в диагональ S (сигма).
  • Вычислите u = Av, нормализуйте их, а затем вставьте как U-столбцы.
  • В случае, если U не является квадратной матрицей, используйте процесс Грама-Шмидта для генерации большего количества ортонормированных векторов.

Я продолжу предыдущий пример, выполнив все вышеперечисленные шаги.
Мы выполнили шаг 1 и половину шага 2, вот собственные векторы Aᵀ * A.

Переходя к шагу 3, мы просто возьмем оба вектора, которые мы нашли выше, и вставим их в строки Vᵀ.

Далее, еще один легкий шаг впереди нас, но имейте в виду, что Sigma должна быть такого же размера, как A.

Еще одна важная вещь, о которой я раньше не говорил, - это то, что сингулярные значения должны располагаться по диагонали в порядке убывания, поэтому очень важно, чтобы в этом случае Sigma была такой, как я ее написал (нижняя версия, конечно).

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

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

Наконец, мы получили нашу SVD-декомпозицию

Как мы можем использовать SVD-декомпозицию для сжатия изображений

Чтобы ответить на этот ответ, мы сначала должны ответить на следующий вопрос.
Дана матрица A (ранга m), какова ближайшая матрица B (ранга r ‹m ) в A?

Давайте разберемся с этой проблемой, сначала разберемся, как мы измеряем расстояние между матрицами.

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

Мы определим расстояние между матрицами как Норму Фробениуса вычитания между ними.

Тогда мы можем перефразировать нашу проблему на

Для решения этой проблемы нам понадобится следующее наблюдение

Тогда мы можем сделать вывод, что решение нашей проблемы

Проще говоря, ближайшая матрица B к матрице A получается из SVD-разложения A. Предполагая, что мы хотим, чтобы B имел степень k, мы возьмем первые k сингулярных значений, первые k столбцов U и первые k строк Vᵀ и как можно ближе подойти к A со степенью k.

Наконец-то настал момент, и мы увидим, как это работает на реальном изображении.

Код, который я написал для этого алгоритма, находится прямо здесь, если вы хотите поэкспериментировать с ним самостоятельно.

Для сравнения, изображение, которое я сжал, находится вверху по шкале серого.