Какая норма ошибки восстановления минимизируется матрицей аппроксимации низкого ранга, полученной с помощью PCA?

Ответ одним словом: оба.

Начнем с определения норм. Для матрицы оператор -норма определяется как $X$ $2$ и норма Фробениуса как

‖ X ‖_{2} = s u p \frac{‖ X v ‖_{2}}{‖ v ‖_{2}} = m a x (s_{i})

$\|X\|_2 = \mathrm{sup}\frac{\|Xv\|_2}{\|v\|_2} = \mathrm{max}(s_i)$

где

- сингулярные значения

, т.е. диагональные элементы

в разложении по сингулярным числам

| | Икс {| |}_{F} знак равно \sqrt{\underset{я J}{Σ} {Икс}_{я J}^{2}} знак равно T р ({Икс}^{⊤} Икс) знак равно \sqrt{Σ s_{я}^{2}},

$\|X\|_F = \sqrt {\sum_{ij} X_{ij}^2} = \mathrm{tr}(X^\top X) = \sqrt{\sum s_i^2},$

s_{i}

$s_i$

X

$X$

S

$S$

X = U S V^{⊤}

$X = USV^\top$

PCA задается тем же разложением сингулярных значений, когда данные центрированы. являются главными компонентами, являются главными осями, то есть собственными векторами ковариационной матрицы, и восстановление только с главными компонентами, соответствующими наибольшим сингулярным значениям, определяется как . $US$ $V$ $X$ $k$ $k$ $X_k = U_k S_k V_k^\top$

Теорема Эккарта-Юнга говорит, что - это матрица, минимизирующая норму ошибки восстановления среди всех матриц ранга . Это верно как для нормы Фробениуса, так и для операторной нормы . Как отметил @cardinal в комментариях, он был впервые доказан Шмидтом (из известности Грам-Шмидта) в 1907 году для случая Фробениуса. Позднее он был вновь открыт Экартом и Янгом в 1936 году и теперь в основном связан с их именами. Мирский обобщил теорему в 1958 г. на все нормы, инвариантные относительно унитарных преобразований, и это включает 2-норму оператора. $X_k$ $\|X-A\|$ $A$ $k$ $2$

Эту теорему иногда называют теоремой Эккарта-Юнга-Мирского. Стюарт (1993) называет это теоремой приближения Шмидта. Я даже видел, как это называется теорема Шмидта-Эккарта-Юнга-Мирского.

Эккарт и Янг, 1936, Аппроксимация одной матрицы другой ранга
Мирский, 1958, Симметрические калибровочные функции и унитарно-инвариантные нормы
Стюарт, 1993, О ранней истории разложения сингулярных значений

Доказательство для оператора норма $2$

Пусть имеет полный ранг . Поскольку имеет ранг , его нулевое пространство имеет измерений. Пространство, охватываемое правыми сингулярными векторами соответствующими наибольшим сингулярным значениям, имеет размерность. Таким образом, эти два пространства должны пересекаться. Пусть - единичный вектор от пересечения. Тогда мы получим: $X$ $n$ $A$ $k$ $n-k$ $k+1$ $X$ $k+1$ $w$ требовалось доказать.

| | Икс - A {| |}_{2}^{2} \geq | | (Икс - A) вес {| |}_{2}^{2} знак равно | | Икс вес {| |}_{2}^{2} знак равно Σ_{я знак равно 1}^{К + 1} s_{я}^{2} (v_{я}^{⊤} вес)^{2} \geq s_{К + 1}^{2} знак равно | | Икс - {Икс}_{К} {| |}_{2}^{2},

$\|X-A\|^2_2 \ge \|(X-A)w\|^2_2 = \|Xw\|^2_2 = \sum_{i=1}^{k+1}s_i^2(v_i^\top w)^2 \ge s_{k+1}^2 = \|X-X_k\|_2^2,$

Доказательство для нормы Фробениуса

Мы хотим , чтобы найти матрицу ранг минимизирующим . Мы можем , где имеет ортонормированных столбцов. Минимизация при фиксированном является регрессионной проблемой с раствором . Подключив его, мы видим, что теперь нам нужно минимизировать $A$ $k$ $\|X-A\|^2_F$ $A=BW^\top$ $W$ $k$ $\|X-BW^\top\|^2$ $W$ $B=XW$ где представляет ковариационная матрица , то есть . Это означаетчто ошибка восстановления сведенаминимуму, взявкачестве столбцов некоторые ортонормированным векторам максимизации общей дисперсии проекции.

‖ X - X W W^{⊤} ‖^{2} = ‖ X ‖^{2} - ‖ X W W^{⊤} ‖^{2} = c o n s t - t r (W W^{⊤} X^{⊤} X W W^{⊤}) = c o n s t - c o n s t \cdot t r (W^{⊤} Σ W),

$\|X-XWW^\top\|^2=\|X\|^2-\|XWW^\top\|^2=\mathrm{const}-\mathrm{tr}(WW^\top X^\top XWW^\top)\\=\mathrm{const}-\mathrm{const}\cdot\mathrm{tr}(W^\top\Sigma W),$

Σ

$\Sigma$

X

$X$

Σ = X^{⊤} X / (n - 1)

$\Sigma=X^\top X/(n-1)$

W

$W$

k

$k$

$k$ $X=USV^\top$ $\Sigma=VS^2V^\top/(n-1)=V\Lambda V^\top$ $R=V^\top W$

t r (W^{⊤} Σ W) = t r (R^{⊤} Λ R) = \sum_{i} λ_{i} \sum_{j} R_{i j}^{2} \leq \sum_{i = 1}^{k} λ_{k},

$\mathrm{tr}(W^\top\Sigma W)=\mathrm{tr}(R^\top\Lambda R)=\sum_i \lambda_i \sum_j R_{ij}^2 \le \sum_{i=1}^k \lambda_k,$

W = V_{k}

$W=V_k$

Смотрите следующие три связанных темы:

Более ранняя попытка доказательства нормы Фробениуса

Это доказательство я нашел где-то в Интернете, но оно неверно (содержит пробел), как объясняет @cardinal в комментариях.

| | Икс - A {| |}_{F} знак равно | | U S В^{⊤} - A | | знак равно | | S - U^{⊤} A В | | знак равно | | S - В | |,

$\|X-A\|_F=\|USV^\top - A\| = \|S - U^\top A V\| = \|S-B\|,$

B = U^{⊤} A V

$B=U^\top A V$

| | Икс - A {| |}_{F} знак равно \underset{я J}{Σ} (S_{я J} - В_{я J})^{2} знак равно \underset{я}{Σ} (s_{я} - В_{я я})^{2} + \underset{я \neq J}{Σ} В_{я J}^{2},

$\|X-A\|_F = \sum_{ij}(S_{ij}-B_{ij})^2 = \sum_i (s_i-B_{ii})^2 + \sum_{i\ne j}B_{ij}^2.$

B

$B$

k

$k$

k

$k$

s_{i}

$s_i$

B_{o p t i m a l} = S_{k}

$B_\mathrm{optimal}=S_k$

A_{o p t i m a l} = U_{k} S_{k} V_{k}^{⊤}

$A_\mathrm{optimal} = U_k S_k V_k^\top$

амеба говорит восстановить монику
источник

Доказательство в случае нормы Фробениуса не является правильным (или, по крайней мере, полным), так как приведенный здесь аргумент не исключает возможности того, что матрица того же ранга могла бы исключить некоторые другие диагональные члены, в то же время имея «малое» отклонение. диагоналей. Чтобы более четко увидеть разрыв, отметьте, что удержание диагоналей постоянным и «обнуление» недиагоналей часто может повысить ранг рассматриваемой матрицы!

кардинал

Отметим также, что СВД было известно Бельтрами (по крайней мере, в довольно общем, хотя и частном случае) и Джордану еще в 1874 году.

Кардинал

B

$B$

S

$S$ вместо того

k

$k$ наибольшие из них и имеет несколько ненулевых недиагональных членов, а затем обе суммы,

\sum_{i} (s_{i} - B_{i i})^{2}

$\sum_{i}(s_i-B_{ii})^2$ а также

\sum_{i \neq j} B_{i j}^{2}

$\sum_{i\ne j}B_{ij}^2$ , собираемся увеличить. Так что это только увеличит ошибку реконструкции. Нет? Тем не менее, я попытался найти другое доказательство для нормы Фробениуса в литературе, и прочитал, что это должно как-то легко следовать из случая нормы оператора. Но до сих пор я не понимаю, как это должно следовать ...

амеба говорит восстановить монику

Я делать , как GW Stewart (1993), О ранней истории сингулярного разложения, SIAM Review , Vol. 35, нет 4, 551-566 и, учитывая ваш предыдущий проявленный интерес к историческим вопросам, я думаю, что вы тоже. К сожалению, я думаю, что Стюарт непреднамеренно чрезмерно пренебрегает элегантностью доказательства Шмидта 1907 года. В нем скрыта регрессионная интерпретация, которую Стюарт упускает из виду и которая действительно довольно симпатична. Есть еще одно доказательство, которое следует первоначальному подходу диагонализации, который вы используете, но который требует дополнительной работы, чтобы заполнить этот пробел. (продолжение) .

кардинал

@cardinal: Да, вы правы, теперь я тоже вижу разрыв. Большое спасибо за статью Стюарта, это было очень интересное чтение. Я вижу, что Стюарт представляет доказательства Шмидта и Вейля, но оба они выглядят более сложными, чем то, что я хотел бы скопировать здесь (и до сих пор у меня не было времени тщательно их изучить). Я удивлен: я ожидал, что это будет очень простой результат, но, похоже, он менее тривиален, чем я думал. В частности, я бы не ожидал, что случай Фробениуса намного сложнее, чем оператор норма. Я буду редактировать пост сейчас. С Новым Годом!

говорит амеба: восстанови Монику

Какая норма ошибки восстановления минимизируется матрицей аппроксимации низкого ранга, полученной с помощью PCA?

Ответы:

Ответ одним словом: оба.

Доказательство для оператора норма222

Доказательство для нормы Фробениуса

Более ранняя попытка доказательства нормы Фробениуса

Доказательство для оператора норма $2$