В моем последнем посте я обсуждал собственное разложение. Однако это применимо только к квадратным матрицам. Более общий метод, разложение по сингулярным числам (SVD), называемый фундаментальной теоремой линейной алгебры, существует для всех матриц.
В этом посте я сначала представлю теорию и конструкцию SVD, а затем покажу вам, как мы можем использовать SVD для аппроксимации матриц, что позволяет сжимать изображения. Помните, что изображения — это всего лишь матрицы со значениями, представляющими цвет пикселя.
Ценности:
называются сингулярными значениями, и таких значений r (r — ранг матрицы A). Обычно они сортируются в порядке убывания. Кроме того, сингулярная матрица Σ уникальна и имеет тот же размер, что и матрица A.
Векторы-столбцы матрицы U называются сингулярными слева, а векторы-столбцы матрицы V называются сингулярными справа. векторы.
Какова интуиция разложения СВД?
Пусть A — матрица преобразования линейного отображения, отображающая векторное пространство R{mxm} в векторное пространство R{nxn}. SVD разбивает это линейное отображение на три части.
- Матрица V — это матрица преобразования в R{n}, которая выполняет изменение базиса из собственного базиса A^{T}Aкоторую мы увидим позже, на стандартную основу. Поскольку V является ортонормированным, это означает:
Итак, сначала V^{T} выполняет изменение базиса со стандартного базиса на собственный базис A^{T}A.
2. Матрица Σ масштабирует новые координаты по сингулярным значениям и отображает собственный базис A^{ T}A в собственный базис AA^{T}.
3. U – это матрица преобразования, которая отображает собственный базис в стандартный базис R{m}.
В SVD происходит смена базиса как в векторном пространстве R{mxm}, так и в векторном пространстве R{nxn}, однако в собственном разложении у нас была только одна смена базиса в том же векторном пространстве.
Строительство СВД
Во-первых, давайте вспомним, что означает, что матрица является симметричной положительно-полуопределенной (СПД). Это симметричная матрица, которая удовлетворяет
для всех x.
Если у нас есть матрица A, мы можем сделать матрицу SPD следующим образом:
потому что:
то же самое означает:
Мы знаем, что можем вычислить собственное разложение на положительно полуопределенной матрице с ортонормированным базисом собственных векторов. Следовательно, мы можем получить:
где P является ортонормированным базисом собственных векторов и диагональной матрицы, содержащей положительные собственные значения.
Предположим, что СВД существует:
Сравнивая уравнение las с собственным разложением, можно увидеть, что P представляет собой матрицу сингулярных справа векторов V A и что собственные значения представляют собой квадраты сингулярных значений.
Итак, мы определили, какими должны быть матрица P и матрица Σ, но нам нужно построить U.
Обратите внимание на матрицу V:
Кроме того, изображения векторных столбцов V, которые являются ортогональными, также должны быть ортогональными в соответствии с матрицей преобразования A.
Опять же, предположим, что SVD существует, посмотрите на:
Спектральная теорема говорит нам, что мы можем диагонализовать матрицу с ортонормированными собственными векторами следующим образом:
Ортонормированные собственные векторы AA⊤ являются левосингулярными векторами U и образуют ортонормированный базисный набор.
Итак, AV образует ортонормированный базис AA⊤ A , но также и U. Однако мы знаем:
таким образом, чтобы получить U, нужно нормализовать AV:
для всех значений j, что приводит нас к:
Это SVD-разложение A.
Матричная аппроксимация
При разложении СВД получаем:
которую мы также можем записать в виде суммы:
Поскольку мы знаем, что сингулярные числа расположены в порядке убывания, первые элементы будут вносить больший вклад в результат. Имеет смысл попытаться отказаться от более поздних частей, чтобы иметь меньшую размерность и, таким образом, иметь более быстрые алгоритмы.
Вот как мы выполняем аппроксимацию ранга k. Мы берем только количество первых векторов-столбцов U и такое же количество первых строк V и вычисляем результат.
Вот пример. Используемая картинка:
Размер изображения 1240х1280.
Используя numpy в python, я вычислил SVD-разложение изображения и попытался аппроксимировать изображение с 10, 20, 30, 40 и 50 первыми столбцами. Вот результаты, которые я получил с кодом, который можно найти здесь:
Последнее изображение является отличным представителем исходного изображения. И это включает только около 7% чисел. (50*(1240+1+1280)/(1240*1280)). Это потрясающе :)
Заключение
SVD позволяет нам идентифицировать неоднородность данных, когда мы хотим выполнить сжатие данных путем аппроксимации. Этот метод применим к неквадратным матрицам и таблицам данных, что делает его применение очень широким.
Также следует помнить, что линейная алгебра — очень мощный инструмент!
