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

или Итерация Ландвебера алгоритм Ландвебера — это алгоритм решения некорректных линейных обратных задач , который был расширен для решения нелинейных задач, включающих ограничения. Метод был впервые предложен в 1950-х годах Луи Ландвебером . и теперь его можно рассматривать как частный случай многих других, более общих методов.

Основной алгоритм

Оригинальный алгоритм Ландвебера пытается восстановить сигнал x из (зашумленных) измерений y . Линейная версия предполагает, что $y=Ax$ для линейного оператора A . Когда задача имеет конечные размеры , A — это просто матрица.

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

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

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

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

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

$x_{k+1}=x_{k}-\omega \nabla f(x_{k})$

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

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

Использование итерации Ландвебера в качестве алгоритма регуляризации обсуждалось в литературе.

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

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

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

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

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

Если f — выпуклая функция и C — выпуклое множество , то задача

$\min _{x\in C}f(x)$

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

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

где ${\mathcal {P}}$ является проекцией на множество C . Сходимость гарантируется, если $0<\tau <2/(\|A\|^{2})$. Это снова частный случай прогнозируемого градиентного спуска (который является частным случаем алгоритма вперед-назад ), как обсуждалось в разделе .

Приложения

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