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

Итерация Ландвебера или Алгоритм Ландвебера — это алгоритм решения некорректно поставленных линейных обратных задач. Алгоритм был расширен на решение нелинейных задач с ограничениями. Метод впервые представлен в 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, англ. simultaneous iterative reconstruction technique). Метод используется также в компьютерном зрении и для восстановления сигнала. Используется метод и при цифровой обработка изображений, поскольку многие задачи обработки изображений, такие как обратная свёртка, плохо обусловлены. Варианты метода используются также в задачах разреженной аппроксимации и compressed sensing.

Литература

• Landweber L. An iteration formula for Fredholm integral equations of the first kind // Amer. J. Math.. — 1951. — Т. 73. — С. 615–624.
• Louis A.K. Inverse und schlecht gestellte Probleme. — Stuttgart: Teubner, 1989.
• Вайникко Г.М., Веретенников А.Ю. Итерационные процедуры в некорректных задачах. — Москва: «Наука», 1986.
• Martin Hanke, Andreas Neubauer, Otmar Scherzer. A convergence analysis of the Landweber iteration for nonlinear ill-posed problems // NUMERISCHE MATHEMATIK. — 1995. — Т. 72, № 1. — doi:10.1007/s002110050158.
• Eicke B. Iteration methods for convexly constrained ill-posed problems in Hilbert space. // Numer. Funct. Anal. Optim.. — 1992. — Вып. 13.
• Johansson B., Elfving T., Kozlovc V., Censor Y., Forssen P.E., Granlund G. The application of an oblique-projected Landweber method to a model of supervised learning // Math. Comput. Modelling. — 2006. — Т. 43.
• Trussell H.J., Civanlar M.R. The Landweber iteration and projection onto convex sets // IEEE Trans. Acoust., Speech, Signal Process.. — 1985. — Вып. 33. — С. 1632–1634.
• Anastasios Kyrillidis, Volkan Cevher. Recipes on hard thresholding methods // Recipes for hard thresholding methods. — 2011. — С. 353–356. — ISBN 978-1-4577-2105-2. — doi:10.1109/CAMSAP.2011.6136024.
• P. L. Combettes, J.-C. Pesquet. Proximal splitting methods in signal processing / H. H. Bauschke, R. S. Burachik, P. L. Combettes, V. Elser, D. R. Luke, H. Wolkowicz, Eds.. — New York: Springer, 2011. — С. 185–212. Архивировано 12 апреля 2024 года.