WikiDer > Алгоритм в толпе - Википедия

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

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

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

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

Алгоритм

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

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

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

Примечания

Этот Прикладная математика-связанная статья является заглушка. Вы можете помочь Википедии расширяя это. v т е