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

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

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

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

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

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

где фактор релаксации удовлетворяет . Здесь самый большой исключительное значение из . Если мы напишем , то обновление можно записать в терминах градиент

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

За некорректно проблем, итерационный метод должен быть остановлен при подходящем индексе итерации, потому что он полусходится. Это означает, что итерации приближаются к регуляризованному решению в течение первых итераций, но становятся нестабильными в последующих итерациях. Величина, обратная индексу итерации действует как параметр регуляризации. Подходящий параметр найден, когда несовпадение приближается к уровню шума.

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

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

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

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

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

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

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

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

куда это проекция на съемочную площадку C. Сходимость гарантирована, когда .[6] Это снова частный случай прогнозируемый градиентный спуск (что является частным случаем вперед-назад алгоритм ), как описано в.[2]

Приложения

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

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

  1. ^ а б Ландвебер Л. (1951): Итерационная формула для интегральных уравнений Фредгольма первого рода // Америк. J. Math. 73, 615–624
  2. ^ а б П. Л. Комбетс, Ж.-К. Песке, "Методы проксимального расщепления в обработке сигналов", в: Алгоритмы с фиксированной точкой для обратных задач в науке и технике (Х. Х. Баушке, Р. С. Бурачик, П. Л. Комбеттс, В. Эльзер, Д. Р. Люк, Х. Волкович, редакторы), стр. 185–212. Спрингер, Нью-Йорк, 2011. ArXiv
  3. ^ Луи, А. (1989): Inverse und schlecht gestellte Probleme. Штутгарт, Тойбнер
  4. ^ Вайникко Г.М., Веретенников А.Ю. (1986): Итерационные процедуры в некорректно поставленных задачах. Москва, Наука
  5. ^ Анализ сходимости итерации Ландвебера для нелинейных некорректных задач Мартин Ханке, Андреас Нойбауэр и Отмар Шерцер. NUMERISCHE MATHEMATIK Том 72, Номер 1 (1995), 21-37, Дои:10.1007 / s002110050158
  6. ^ Эйке, Б .: Итерационные методы для некорректно поставленных задач с выпуклыми ограничениями в гильбертовом пространстве. Нумер. Функц. Анальный. Оптим. 13. С. 413–429 (1992).
  7. ^ Johansson, B., Elfving, T., Kozlovc, V., Censor, Y., Forssen, P.E., Granlund, G .; «Применение метода Ландвебера с наклонной проекцией к модели обучения с учителем», Math. Comput. Моделирование, том 43, стр 892–909 (2006)
  8. ^ Trussell, H.J., Civanlar, M.R .: итерация и проекция Ландвебера на выпуклые множества. IEEE Trans. Акуст., Речь, сигнальный процесс. 33, 1632–1634 (1985)
  9. ^ Анастасиос Кириллидис и Волкан Севхер (2011). «Рецепты жестких пороговых методов». Рецепты для жестких пороговых методов. С. 353–356. Дои:10.1109 / CAMSAP.2011.6136024. ISBN  978-1-4577-2105-2.