к -СВД

В прикладной математике k - SVD — это алгоритм обучения словаря для создания словаря для разреженных представлений с помощью подхода разложения по сингулярным значениям . k -SVD — это обобщение k метода кластеризации -means , и он работает путем итеративного чередования между разреженным кодированием входных данных на основе текущего словаря и обновлением атомов в словаре для лучшего соответствия данным. Он структурно связан с алгоритмом ожидания-максимизации (EM) . k -SVD широко используется в таких приложениях, как обработка изображений, обработка звука, биология и анализ документов.

k алгоритм

k -SVD является своего рода обобщением k -средних следующим образом. Кластеризацию k -средних можно также рассматривать как метод разреженного представления . То есть поиск наилучшей кодовой книги для представления образцов данных. $\{y_{i}\}_{i=1}^{M}$ по ближайшему соседу , решив

$\quad \min \limits _{D,X}\{\|Y-DX\|_{F}^{2}\}\qquad {\text{subject to }}\forall i,x_{i}=e_{k}{\text{ for some }}k.$

что почти эквивалентно

$\quad \min \limits _{D,X}\{\|Y-DX\|_{F}^{2}\}\qquad {\text{subject to }}\quad \forall i,\|x_{i}\|_{0}=1$

что является k-средством, допускающим «веса».

Буква F обозначает норму Фробениуса . Разреженный термин представления $x_{i}=e_{k}$ заставляет алгоритм k -means использовать только один атом (столбец) в словаре $D$. Чтобы ослабить это ограничение, цель алгоритма k -SVD состоит в том, чтобы представить сигнал как линейную комбинацию атомов в $D$.

Алгоритм k -SVD следует последовательности построения алгоритма k -means. Однако, в отличие от k -средних, для достижения линейной комбинации атомов в $D$, член разреженности ограничения ослабляется так, что количество ненулевых записей каждого столбца $x_{i}$ может быть больше 1, но меньше числа $T_{0}$.

Таким образом, целевая функция становится

$\quad \min \limits _{D,X}\{\|Y-DX\|_{F}^{2}\}\qquad {\text{subject to }}\quad \forall i\;,\|x_{i}\|_{0}\leq T_{0}.$

или в другой объективной форме

$\quad \min \limits _{D,X}\sum _{i}\|x_{i}\|_{0}\qquad {\text{subject to }}\quad \forall i\;,\|Y-DX\|_{F}^{2}\leq \epsilon .$

В алгоритме k -SVD $D$ сначала фиксированная и лучшая матрица коэффициентов $X$ найден. Как найти действительно оптимальный $X$ сложно, мы используем метод поиска аппроксимации. Для расчета коэффициентов можно использовать любой алгоритм, такой как OMP, поиск ортогонального сопоставления , если он может предоставить решение с фиксированным и заранее определенным количеством ненулевых записей. $T_{0}$.

После задачи разреженного кодирования следующей задачей является поиск лучшего словаря. $D$. Однако найти весь словарь за раз невозможно, поэтому процесс заключается в обновлении только одного столбца словаря. $D$ каждый раз, исправляя $X$. Обновление $k$-й столбец делается путем переписывания срока штрафа как

$\|Y-DX\|_{F}^{2}=\left\|Y-\sum _{j=1}^{K}d_{j}x_{j}^{\text{T}}\right\|_{F}^{2}=\left\|\left(Y-\sum _{j\neq k}d_{j}x_{j}^{\text{T}}\right)-d_{k}x_{k}^{\text{T}}\right\|_{F}^{2}=\|E_{k}-d_{k}x_{k}^{\text{T}}\|_{F}^{2}$

где $x_{k}^{\text{T}}$ обозначает k ю строку X. -

Разложив умножение $DX$ в сумму $K$ матрицы ранга 1, мы можем предположить, что другие $K-1$ условия предполагаются фиксированными, а $k$-th остается неизвестным. После этого шага мы можем решить задачу минимизации, аппроксимировав $E_{k}$ термин с $rank-1$ матрица с использованием разложения по сингулярным значениям , затем обновление $d_{k}$ с этим. Однако новое решение для вектора $x_{k}^{\text{T}}$ не гарантированно будет разреженным.

Чтобы решить эту проблему, определите $\omega _{k}$ как

$\omega _{k}=\{i\mid 1\leq i\leq N,x_{k}^{\text{T}}(i)\neq 0\},$

что указывает на примеры $\{y_{i}\}_{i=1}^{N}$ которые используют атом $d_{k}$ (также записи $x_{i}$ это не ноль). Затем определите $\Omega _{k}$ как матрица размера $N\times |\omega _{k}|$, с теми, что на $(i,\omega _{k}(i)){\text{th}}$ записи и нули в противном случае. При умножении ${\tilde {x}}_{k}^{\text{T}}=x_{k}^{\text{T}}\Omega _{k}$, это сжимает вектор-строку $x_{k}^{\text{T}}$ путем отбрасывания нулевых записей. Аналогично, умножение ${\tilde {Y}}_{k}=Y\Omega _{k}$ представляет собой подмножество текущих примеров с использованием $d_{k}$ атом. Тот же эффект можно увидеть на ${\tilde {E}}_{k}=E_{k}\Omega _{k}$.

Таким образом, проблема минимизации, упомянутая ранее, становится

$\|E_{k}\Omega _{k}-d_{k}x_{k}^{\text{T}}\Omega _{k}\|_{F}^{2}=\|{\tilde {E}}_{k}-d_{k}{\tilde {x}}_{k}^{\text{T}}\|_{F}^{2}$

и это можно сделать напрямую с помощью SVD. СВД разлагается ${\tilde {E}}_{k}$ в $U\Delta V^{\text{T}}$. Решение для $d_{k}$ - первый столбец U, вектор коэффициентов ${\tilde {x}}_{k}^{\text{T}}$ в качестве первого столбца $V\times \Delta (1,1)$. После обновления всего словаря процесс переходит к итеративному решению X, а затем итерационному решению D.

Ограничения

Выбор подходящего «словаря» для набора данных является невыпуклой проблемой, и k -SVD работает путем итеративного обновления, которое не гарантирует нахождение глобального оптимума. Однако это характерно для других алгоритмов этой цели, и k -SVD работает на практике довольно хорошо.

См. также

• Разреженное приближение
• Разложение по сингулярным значениям
• Матрица норма
• k - означает кластеризацию
• Низкоранговое приближение