Я читал о разложении сингулярных значений (SVD). Почти во всех учебниках упоминается, что она разбивает матрицу на три матрицы с заданной спецификацией.
Но какова интуиция, лежащая в основе разделения матрицы в такой форме? PCA и другие алгоритмы уменьшения размерности интуитивно понятны в том смысле, что алгоритм обладает хорошим свойством визуализации, но с SVD это не так.
matrix
linear-algebra
svd
intuition
ШАШАНК ГУПТА
источник
источник
Ответы:
Запишите SVD матрицы (вещественное, n × p ) как X = U D V T, где U - n × p , D - диагональ p × p, а V T - p × p . В терминах столбцов матриц U и V мы можем записать X = ∑ p i = 1 d i u i v T iX n×p
Теперь представьте, что содержит значения черно-белого изображения в оттенках серого, каждая запись в матрице представляет один пиксель. Например, следующая картина бабуина:X
Затем прочитайте это изображение в R и получите матричную часть полученной структуры, возможно, используя библиотеку
pixmap
.Если вы хотите получить пошаговое руководство по воспроизведению результатов, вы можете найти код здесь .
Рассчитаем СВД:
в результате чего получаются следующие два изображения:
Слева мы можем легко увидеть вертикальные / горизонтальные полосы на изображении ранга 1.
Что довольно интересно: мы видим части исходного изображения, которые трудно представить как суперпозицию вертикальных / горизонтальных линий, в основном волосы диагонального носа и некоторую текстуру, а также глаза!
источник
Пусть (поэтому количественно определяет взрывную силу в направлении ). Предположим, что единичные векторы определены так, что Уравнения (2) могут быть кратко выражены с использованием матричной записи в виде где - матрица , й столбец которой равен , - матрица чья столбец иσi=∥Avi∥2 σi A vi ui Avi=σiuifor i=1,…,n.(2) AV=UΣ,(3) V n×n i vi U m×n i ui Σ это диагональная матрица, й диагональный элемент которой равен . Матрица ортогональна, поэтому мы можем умножить обе части (3) на чтобы получить
Может показаться, что теперь мы вывели SVD из с почти нулевым усилием. Ни один из шагов до сих пор не был сложным. Однако важная часть картины отсутствует - мы еще не знаем, что ортогонально.n×n i σi V VT A=UΣVT. A U
Вот ключевой факт, отсутствующий фрагмент: оказывается, что ортогонален : Я утверждаю, что если это не так, то не будет оптимальным для задачи (1). Действительно, если бы (4) не было выполнено, то можно было бы улучшить , немного его возмутив в направлении .Av1 Av2 ⟨Av1,Av2⟩=0.(4) v1 v1 v2
Предположим (для противоречия), что (4) не выполняется. Если слегка возмущается в ортогональном направлении , норма не изменяется (или, по крайней мере, изменение нормы незначительно). Когда я иду по поверхности земли, мое расстояние от центра Земли не меняется. Однако, когда возмущается в направлении , вектор возмущается в неортогональном направлении , и поэтому изменение нормы является пренебрежимо малым . Нормаv1 v2 v1 v1 v1 v2 Av1 Av2 Av1 Av1 может быть увеличено на незначительную сумму. Это означает, что не является оптимальным для задачи (1), что противоречит. Мне нравится этот аргумент, потому что: 1) интуиция очень ясна; 2) интуиция может быть преобразована непосредственно в строгое доказательство.v1
Аналогичный аргумент показывает, что является ортогональным как к и к , и так далее. Векторы попарно ортогональны. Это означает, что единичные векторы могут быть выбраны попарно ортогональными, что означает, что матрица выше является ортогональной матрицей. Это завершает наше открытие СВД.Av3 Av1 Av2 Av1,…,Avn u1,…,un U
Чтобы преобразовать приведенный выше интуитивный аргумент в строгое доказательство, мы должны учитывать тот факт, что если возмущен в направлении , возмущенный вектор действительно не является единичным вектором. (Его норма .) Чтобы получить строгое доказательство, определите Вектор действительно является единичным вектором. Но, как вы можете легко показать, если (4) не выполняется, то для достаточно малых значений имеем (при условии, что знакv1 v2 v~1=v1+ϵv2 1+ϵ2−−−−−√ v¯1(ϵ)=1−ϵ2−−−−−√v1+ϵv2. v¯1(ϵ) ϵ f(ϵ)=∥Av¯1(ϵ)∥22>∥Av1∥22 ϵ выбран правильно). Чтобы показать это, просто проверьте, что . Это означает, что не является оптимальным для задачи (1), что противоречит.f′(0)≠0 v1
(Кстати, я рекомендую прочитать объяснение Qiaochu Юаня из СВДА здесь . В частности, обратите внимание на «Key лемме # 1», которая является то , что мы обсуждали выше. Как Qiaochu говорит, ключевая лемму # 1 является «техническим сердцем разложения по сингулярным числам ".)
источник
Чувак, потрать час своего дня и посмотри эту лекцию: https://www.youtube.com/watch?v=EokL7E6o1AE
Этот парень очень прямолинеен, важно не пропускать ничего из этого, потому что в конце концов все сводится вместе. Даже если вначале это может показаться немного медленным, он пытается определить критическую точку, что он и делает!
Я подведу итог для вас, вместо того, чтобы просто дать вам три матрицы, которые все делают (потому что это сбивало меня с толку, когда я читал другие описания). Откуда взялись эти матрицы и почему мы так настроили их? Лекция прибивает это! Каждая матрица (когда-либо существовавшая в истории вечности) может быть построена из базовой матрицы с одинаковыми размерами, затем повернуть ее и растянуть (это основная теорема линейной алгебры). Каждая из этих трех матриц, которые бросают люди, представляет собой исходную матрицу (U), матрицу масштабирования (сигма) и матрицу вращения (V).
Матрица масштабирования показывает, какие векторы вращения являются доминирующими, они называются сингулярными значениями. Разложение является решающим для U, сигма и V.
источник