Сокращённое сингулярное разложение

Эта статья плохо повышает индекс цитируемости
авторов других статей этой вики.

Вы можете помочь, добавив навигационные ссылки.

Содержание

1 О чем речь?
2 Оптимальность с точки зрения нормы Фробениуса
3 Выбор K
4 Ссылки

О чем речь?[]

Пусть дана матрица $A\in \mathbb {R} ^{N\times D},rgA=R$ . Пусть есть сингулярное разложение $A=U\Sigma V^{T}$ , где $U\in {\mathcal {O}}_{N\times R},U=\left[u_{1},u_{2},...u_{R}\right]$ , $\Sigma =diag\left(\sigma _{1},\sigma _{2}...\sigma _{R}\right)$ , $V\in {\mathcal {O}}_{D\times R},V=\left[v_{1},v_{2},...v_{R}\right]$ , где ${\mathcal {O}}$ — множество ортогональных матриц соответствующей размерности (т. е. $U^{T}U=V^{T}V=I\in \mathbb {R} ^{R\times R}$ ), $\sigma _{1}\geq \sigma _{2}\geq ...\geq \sigma _{R}>0$ (ОБРАЩАЮ ВНИМАНИЕ: в отличие от лекций Китова неравенство с нулем СТРОГОЕ, потому что так правильнее, пруф), $V^{T}$ — транспонирование матрицы $V$ . Более подробно можно прочитать тут.

Пусть мы хотим построить низкоранговое приближение ранга $K\leq R$ для матрицы, то есть ${\hat {A}}_{K}:rg{\hat {A}}_{K}\leq K$ . Усечённое сингулярное разложение — такое, в котором отбросили часть меньших сингулярных чисел (и отбросили столбцы в $U,V$ ). Итак, усечённое сингулярное разложение порядка $K$ : ${\hat {A}}_{K}=U_{K}\Sigma _{K}V_{K}^{T}$ , где $U_{K}=\left[u_{1},u_{2},...u_{K}\right],\Sigma _{K}=diag\left(\sigma _{1},\sigma _{2}...\sigma _{K}\right),V=\left[v_{1},v_{2},...v_{K}\right]$ .

Оптимальность с точки зрения нормы Фробениуса[]

Норма Фробениуса для матрицы $A\in \mathbb {R} ^{N\times D}$ : $||A||_{F}={\sqrt {\sum _{i=1}^{N}\sum _{j=1}^{D}a_{i,j}^{2}}}$ .

Используем определения, введенные выше. Утверждается, что ${\hat {A}}_{K}$ будет оптимальным в смысле нормы Фробениуса приближением исходной матрицы ранга $K\leq R$ , то есть

${\begin{aligned}rg{\hat {A}}_{K}=K\\{\hat {A}}_{K}={\underset {B\in \mathbb {R} ^{N\times D}rgB\leq K}{argmin}}||B-A||_{F}\\\end{aligned}}$

Докажем это. К сожалению, так вышло, что все, что я перенабирал, кануло в лету, сил у меня больше нет, и читатель отсылается сюда, страница 13, за разъяснениями (ОБРАТИТЕ ВНИМАНИЕ: в пункте 2.2 доказательства у Китова опечатка: неравенство противоположное (не $\leq$ , а $\geq$ )). Основная идея такова: с рангом все более-менее ясно: ${\begin{aligned}rgU_{K}=K,rgV_{K}=rgV_{K}^{T}=K,rg\Sigma _{K}=K\Rightarrow rgU_{K}\Sigma _{K}=rg\Sigma _{K}V_{K}^{T}\\=K\Rightarrow rgU_{K}\Sigma _{K}V_{K}^{T}=K\end{aligned}}$

(следует из того, что ранг произведения не превосходит ранга каждого из сомножителей, а также неравенства Фробениуса: $rgABC\geq rgAB+rgBC-rgB$ ), мдауш; вторая часть базируется на связи SVD-разложения и PCA.

Выбор K[]

Пусть, как и прежде, матрица $A=U\Sigma V^{T}$ , где $\Sigma =diag\left(\sigma _{1},\sigma _{2}...\sigma _{R}\right)$ . Ее усечённое сингулярное разложение порядка $K$ представим в виде ${\hat {A}}_{K}=U\Sigma _{K}V^{T}$ , где $\Sigma _{K}=diag\left(\sigma _{1},\sigma _{2}...\sigma _{K},0...0\right)$ . Тогда ошибка аппроксимации записывается следующим образом: $E_{K}=A-{\hat {A}}_{K}=U{\tilde {\Sigma }}V^{T}$ , где ${\tilde {\Sigma }}=diag\left(0...0,\sigma _{K+1}...\sigma _{R}\right)$ . Используя теорему о том, что $||A||_{F}^{2}=\sum _{i=1}^{R}\sigma _{i}^{2}$ (познакомиться с ней и ее доказательством поближе можно тут на страницах 16-18), легко получаем критерий выбора оптимального $K$ : выбирать $K$ нужно таким образом, чтобы относительная ошибка аппроксимации была меньше некоторого порога $t$ , т.е. $K={\underset {K}{argmin}}\{{\frac {||E_{K}||_{F}^{2}}{||A||_{F}^{2}}}={\frac {\sum _{i=K+1}^{R}\sigma _{i}^{2}}{\sum _{i=1}^{R}\sigma _{i}^{2}}}<t\}$ .