Алгоритм работы в толпе

Алгоритм «в толпе» — это численный метод решения проблемы шумоподавления при поиске базиса быстрого ; быстрее, чем любой другой алгоритм для больших, редких задач. ^[1] Этот алгоритм представляет собой метод активного набора , который итеративно минимизирует подзадачи шумоподавления глобального базисного поиска:

$\min _{x}{\frac {1}{2}}\|y-Ax\|_{2}^{2}+\lambda \|x\|_{1}.$

где $y$ наблюдаемый сигнал, $x$ это разреженный сигнал, который нужно восстановить, $Ax$ ожидаемый сигнал под $x$ , и $\lambda$ — параметр регуляризации, сочетающий в себе точность и простоту сигнала. Простота здесь измеряется разреженностью решения. $x$ , измерить через него $\ell _{1}$ -норм. Стратегии активного набора очень эффективны в этом контексте, поскольку ожидается, что лишь немногие коэффициенты будут ненулевыми. Таким образом, если их можно идентифицировать, решение проблемы, ограниченной этими коэффициентами, дает решение. Здесь объекты жадно выбираются на основе абсолютного значения их градиента при текущей оценке.

Другие активные методы шумоподавления преследования базиса включают BLITZ, ^[2] где выбор активного множества осуществляется с использованием разрыва двойственности задачи и Поиска признака признака, ^[3] где признаки включаются на основе оценки их знака.

Алгоритм

Он состоит из следующего:

Объявить $x$ быть 0, поэтому необъяснимый остаток $r=y$
Объявить активный набор $I$ быть пустым множеством, и $I^{c}$ быть его дополнением (неактивный набор)
Рассчитайте полезность $u_{j}=|\langle rA_{j}\rangle |$ для каждого компонента в $I^{c}$
Если включено $I^{c}$ , нет $u_{j}>\lambda$ , прекратить
В противном случае добавьте $L\approx 25$ компоненты для $I$ исходя из их полезности
Решите базовое подавление шума точно на $I$ и выбросить любой компонент $I$ значение которого достигает ровно 0. Эта задача плотная, поэтому методы квадратичного программирования очень хорошо подходят для этой подзадачи.
Обновлять $r=y-Ax$ - nb может быть вычислено в подзадаче как все элементы вне $I$ 0
Перейдите к шагу 3.

Поскольку каждый раз, когда алгоритм «в толпе» выполняет глобальный поиск, его сумма составляет $L$ компонентов активного набора, это может быть фактором $L$ быстрее, чем лучшие альтернативные алгоритмы, когда этот поиск требует больших вычислительных затрат. Теорема ^[1] гарантирует, что глобальный оптимум будет достигнут, несмотря на многократный характер алгоритма в толпе.

Примечания

^ Jump up to: ^а ^б См. «Алгоритм в толпе для быстрого подавления шума при поиске базиса» , IEEE Trans Sig Proc 59 (10), 1 октября 2011 г., стр. 4595–4605, [1] демонстрационный код MATLAB , доступен [2]
^ Джонсон Т., Гестрин К. Блиц: Принципиальный метаалгоритм масштабирования разреженной оптимизации . В материалах Международной конференции по машинному обучению (ICML) 2015 г. (стр. 1171-1179).( [3] )
^ Ли Х, Битва А, Райна Р, Нг AY. Эффективные алгоритмы разреженного кодирования . В журнале «Достижения в области нейронных систем обработки информации», 2007 г. (стр. 801–808). [4]

Эта прикладной математике, статья, посвященная незавершена . Вы можете помочь Википедии, расширив ее .

[in_crowd-1] Jump up to: ^а ^б См. «Алгоритм в толпе для быстрого подавления шума при поиске базиса» , IEEE Trans Sig Proc 59 (10), 1 октября 2011 г., стр. 4595–4605, [1] демонстрационный код MATLAB , доступен [2]

[2] Джонсон Т., Гестрин К. Блиц: Принципиальный метаалгоритм масштабирования разреженной оптимизации . В материалах Международной конференции по машинному обучению (ICML) 2015 г. (стр. 1171-1179).( [3] )

[3] Ли Х, Битва А, Райна Р, Нг AY. Эффективные алгоритмы разреженного кодирования . В журнале «Достижения в области нейронных систем обработки информации», 2007 г. (стр. 801–808). [4]

[1]

[2]

[3]