Русская Википедия:Итерация Ландвебера
Итерация Ландвебера или Алгоритм Ландвебера — это алгоритм решения некорректно поставленных линейных обратных задач. Алгоритм был расширен на решение нелинейных задач с ограничениями. Метод впервые представлен в 1950-х годах Шаблон:Не переведено 5Шаблон:Sfn и в настоящее время этот метод понимается как частный случай многих других более общих методовШаблон:Sfn.
Базовый алгоритм
Оригинальный алгоритм ЛандвебераШаблон:Sfn пытается найти сигнал x из (зашумлённых) измерений y. Линейная версия предполагает, что <math>y = Ax </math> для линейного оператора A. Если задача поставлена в конечномерном пространстве, A является просто матрицей.
Если оператор A не вырожден, то явным решением будет <math> x = A^{-1} y</math>. Однако в случае, когда оператор A плохо обусловлен, явное решение является плохим выбором, поскольку оно чувствительно к любому шуму в значениях y. Если A сингулярен, это явное решение даже вообще не существует. Алгоритм Ландвебера является попыткой регуляризовать задачу и является одной из альтернатив регуляризации Тихонова. Мы можем рассматривать алгоритм Ландвебера как метод нахождения
- <math> \min_x \|Ax-y\|_2^2/2 </math>
с помощью итеративного метода. Этот алгоритм получается из обновления точки по формуле
- <math> x_{k+1} = x_{k} - \omega A^*(Ax_k - y). </math>
где коэффициент релаксации <math>\omega</math> удовлетворяет условию <math> 0 < \omega < 2/\sigma_1^2</math>. Здесь <math>\sigma_1</math> — наибольшее сингулярное значение оператора <math>A</math>. Если мы запишем <math> f(x) = \|Ax-y\|_2^2 /2</math>, то обновление можно записать в терминах градиента
- <math> x_{k+1} = x_k - \omega \nabla f(x_k), </math>
а следовательно, алгоритм является частным случаем градиентного спуска.
Для плохо обусловленных задач итеративный метод нужно остановить на подходящей итерации ввиду его полусходимости. Это означает, что итерации достигают регуляризованного решения во время некоторой итерации, но решение становится нестабильным на следующих итерациях. Величина, обратная номеру итерации <math> 1/k </math>, действует как параметр регуляризации. Подходящий параметр найден, если невязка <math> \|Ax_k-y\|_2^2 </math> достигает уровня шума.
Использование итерации Ландвебера в качестве алгоритма регуляризации обсуждается в литературеШаблон:SfnШаблон:Sfn.
Нелинейное расширение
В общем случае точки, полученные по формуле <math> x_{k+1} = x_{k} - \tau \nabla f(x_k) </math> образуют последовательность <math>f(x_k)</math>, которая сходится к минимальному значению функции f, если f выпукла, а шаг <math>\tau</math> выбирается так, что <math> 0 < \tau < 2/( \|\nabla f\|^2 ) </math>, где <math> \|\cdot \| </math> является спектральной нормой.
Поскольку это является частным случаем градиентного спуска, в настоящее время нет особого смысла анализировать метод в чистом виде как нелинейные итерации Ландвебера, но такой анализ был исторически осуществлён несколькими сообществами не заботясь об унификации подхода.
Нелинейная задача Ландвебер изучалась во многих статьях во многих сообществах. См., например статью Ханке, Нойбауэра и ШерцераШаблон:Sfn.
Обобщение на задачи с ограничениями
Если f является выпуклой функцией, а C — выпуклым множеством, то задача
- <math> \min_{x \in C} f(x) </math>
может быть решена нелинейными итерациями Ландвебера с ограничениями, которые задаются формулой:
- <math> x_{k+1} = \mathcal{P}_C( x_{k} - \tau \nabla f(x_k) )</math>
где <math>\mathcal{P}</math> является проекцией в множество C. Сходимость гарантируется при <math> 0 < \tau < 2/( \|A\|^2 ) </math>Шаблон:Sfn. Это опять является частным случаем проективного градиентного спуска (который, в свою очередь, является частным случаем алгоритма прямого-обратного хода как обсуждается в статье Комбета и ПескеШаблон:Sfn).
Приложения
Поскольку метод появился ещё в 1950-х годах, он признан или переоткрыт многими научными сообществами, особенно теми, которые изучают некорректно поставленные задачи. В компьютерной томографии он называется методикой одновременной итерационной реконструкции (SIRT, Шаблон:Lang-en). Метод используется также в компьютерном зренииШаблон:Sfn и для восстановления сигналаШаблон:Sfn. Используется метод и при цифровой обработка изображений, поскольку многие задачи обработки изображений, такие как обратная свёртка, плохо обусловлены. Варианты метода используются также в задачах Шаблон:Не переведено 5 и compressed sensingШаблон:Sfn.
Примечания
Литература
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Статья
