К-СВД - K-SVD

В Прикладная математика, К-СВД это изучение словаря алгоритм создания словаря для разреженные представления, через разложение по сингулярным числам подход. К-СВД - это обобщение k-означает кластеризацию метод, и он работает путем итеративного чередования между разреженным кодированием входных данных на основе текущего словаря и обновлением атомов в словаре для лучшего соответствия данным.^[1][2] K-SVD широко используется в таких приложениях, как обработка изображений, обработка звука, биология и анализ документов.

Описание проблемы

Эта секция содержит перефразировать из несвободного источника, защищенного авторским правом, http://intranet.daiict.ac.in/~ajit_r/IT530/KSVD_IEEETSP.pdf (Отчет детектора дублирования). Соответствующее обсуждение можно найти на страница обсуждения. Идеи в этой статье следует выражать оригинально. (Май 2014 г.) (Узнайте, как и когда удалить этот шаблон сообщения)

Цель изучения словаря - изучить переполненную матрицу словаря. ${ Displaystyle D in mathbb {R} ^ {п раз K}}$ который содержит ${ displaystyle K}$ сигнальные атомы (в этих обозначениях столбцы ${ displaystyle D}$). Вектор сигнала ${ Displaystyle у в mathbb {R} ^ {п}}$ могут быть представлены, редко, как линейная комбинация этих атомов; представлять ${ displaystyle y}$, вектор представления ${ displaystyle x}$ должен удовлетворять точному условию ${ displaystyle y = Dx}$, или приблизительное условие ${ Displaystyle у приблизительно Dx}$, уточняется, требуя, чтобы ${ Displaystyle | Y-Dx | _ {p} leq epsilon}$ за небольшую сумму ε и немного L_п норма. Вектор ${ Displaystyle х in mathbb {R} ^ {K}}$ содержит коэффициенты представления сигнала ${ displaystyle y}$. Обычно норма ${ displaystyle p}$ выбран как L₁, L₂, или же L_∞.

Если ${ Displaystyle п <К}$ и D - матрица полного ранга, для задачи представления доступно бесконечное число решений. Следовательно, на решение должны быть наложены ограничения. Кроме того, для обеспечения разреженности предпочтительным является решение с наименьшим количеством ненулевых коэффициентов. Таким образом, представление разреженности является решением либо

${ displaystyle (P_ {0}) quad min limits _ {x} | x | _ {0} qquad { text {при условии}} y = Dx}$

или же

${ displaystyle (P_ {0, epsilon}) quad min limits _ {x} | x | _ {0} qquad { text {при условии}} | y-Dx | _ { 2} leq epsilon}$

где ${ Displaystyle | х | _ {0}}$ считает ненулевые элементы вектора ${ displaystyle x}$. (Видеть нулевая "норма".)

К-СВД алгоритм

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

${ displaystyle quad min limits _ {D, X} { | Y-DX | _ {F} ^ {2} } qquad { text {при условии}} forall i, x_ { i} = e_ {k} { text {для некоторых}} k.}$

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

${ Displaystyle quad min limits _ {D, X} { | Y-DX | _ {F} ^ {2} } qquad { text {при условии}} quad forall i, | x_ {i} | _ {0} = 1}$.

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

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

Итак, целевая функция принимает вид

${ displaystyle quad min limits _ {D, X} { | Y-DX | _ {F} ^ {2} } qquad { text {при условии}} quad forall i ;, | x_ {i} | _ {0} leq T_ {0}.}$

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

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

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

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

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

куда ${ displaystyle x_ {T} ^ {k}}$ обозначает k-й ряд Икс.

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

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

${ Displaystyle omega _ {k} = {я середина 1 Leq я Leq N, x_ {T} ^ {k} (я) neq 0 },}$

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

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

${ Displaystyle | E_ {k} Omega _ {k} -d_ {k} x_ {T} ^ {k} Omega _ {k} | _ {F} ^ {2} = | E_ {k } ^ {R} -d_ {k} x_ {R} ^ {k} | _ {F} ^ {2}}$

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

Ограничения

Выбор подходящего «словаря» для набора данных - невыпуклая проблема, и K-SVD работает путем итеративного обновления, которое не гарантирует нахождение глобального оптимума.^[2] Однако это обычное дело для других алгоритмов для этой цели, и K-SVD на практике работает довольно хорошо.^{[2][нужен лучший источник ]}

Смотрите также

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

Рекомендации