WikiDer > Итерация Ландвебера

В Итерация Ландвебера или же Алгоритм Ландвебера это алгоритм решения некорректно линейный обратные задачи, и он был расширен для решения нелинейных задач, связанных с ограничениями. Впервые метод был предложен в 1950-х гг. Луи Ландвебер,^[1] и теперь его можно рассматривать как частный случай многих других более общих методов.^[2]

Базовый алгоритм

Оригинальный алгоритм Ландвебера ^[1] пытается восстановить сигнал Икс от (зашумленных) измерений у. Линейная версия предполагает, что ${ displaystyle y = Ax}$ для линейный оператор А. Когда проблема в конечном размеры, А это просто матрица.

Когда А является неособый, то явным решением будет ${ displaystyle x = A ^ {- 1} y}$. Однако если А является плохо воспитанный, явное решение - плохой выбор, поскольку оно чувствительно к любому шуму в данных. у. Если А является единственное число, этого явного решения даже не существует. Алгоритм Ландвебера - это попытка упорядочить проблема, и является одной из альтернатив Тихоновская регуляризация. Мы можем рассматривать алгоритм Ландвебера как решение:

${ displaystyle min _ {x} | Ax-y | _ {2} ^ {2} / 2}$

с использованием итеративного метода. Алгоритм дается обновлением

${ displaystyle x_ {k + 1} = x_ {k} - omega A ^ {*} (Ax_ {k} -y).}$

где фактор релаксации ${ displaystyle omega}$ удовлетворяет ${ Displaystyle 0 < omega <2 / sigma _ {1} ^ {2}}$. Здесь ${ displaystyle sigma _ {1}}$ самый большой исключительное значение из ${ displaystyle A}$. Если мы напишем ${ Displaystyle е (х) = | Ax-y | _ {2} ^ {2} / 2}$, то обновление можно записать в терминах градиент

${ Displaystyle х_ {к + 1} = х_ {к} - омега набла ф (х_ {к})}$

и, следовательно, алгоритм является частным случаем градиентный спуск.

За некорректно проблем, итерационный метод должен быть остановлен при подходящем индексе итерации, потому что он полусходится. Это означает, что итерации приближаются к регуляризованному решению в течение первых итераций, но становятся нестабильными в последующих итерациях. Величина, обратная индексу итерации ${ displaystyle 1 / k}$ действует как параметр регуляризации. Подходящий параметр найден, когда несовпадение ${ displaystyle | Ax_ {k} -y | _ {2} ^ {2}}$ приближается к уровню шума.

Использование итерации Ландвебера как регуляризация Алгоритм обсуждался в литературе.^[3][4]

Нелинейное расширение

Как правило, обновления генерируются ${ displaystyle x_ {k + 1} = x_ {k} - tau nabla f (x_ {k})}$сгенерирует последовательность ${ displaystyle f (x_ {k})}$ который сходится к минимизатору ж в любое время ж является выпуклыйи размер шага ${ Displaystyle тау}$ выбирается так, что ${ Displaystyle 0 < тау <2 / ( | набла ф | ^ {2})}$ куда ${ displaystyle | cdot |}$ это спектральная норма.

Поскольку это особый тип градиентного спуска, в настоящее время нет особой пользы от анализа его как нелинейного метода Ландвебера, но такой анализ исторически выполнялся многими сообществами, не знающими об объединяющих рамках.

Нелинейная проблема Ландвебера изучалась во многих статьях во многих сообществах; см., например,.^[5]

Расширение на ограниченные задачи

Если ж это выпуклая функция и C это выпуклый набор, тогда проблема

${ Displaystyle мин _ {х в C} е (х)}$

может быть решена с помощью ограниченной нелинейной итерации Ландвебера, задаваемой следующим образом:

${ displaystyle x_ {k + 1} = { mathcal {P}} _ {C} (x_ {k} - tau nabla f (x_ {k}))}$

куда ${ displaystyle { mathcal {P}}}$ это проекция на съемочную площадку C. Сходимость гарантирована, когда ${ Displaystyle 0 < тау <2 / ( | A | ^ {2})}$.^[6] Это снова частный случай прогнозируемый градиентный спуск (что является частным случаем вперед-назад алгоритм), как описано в.^[2]

Приложения

Поскольку этот метод существует с 1950-х годов, он был принят и заново открыт многими научными сообществами, особенно теми, кто изучает некорректно поставленные проблемы. В Рентгеновская компьютерная томография это называется SIRT - метод одновременной итеративной реконструкции. Он также использовался в компьютерное зрение сообщество^[7] и сообщество восстановления сигналов.^[8] Он также используется в обработка изображений, поскольку многие проблемы с изображением, такие как деконволюция, некорректно поставлены. Варианты этого метода использовались также в задачах разреженной аппроксимации и сжатое зондирование настройки.^[9]

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