4.3. МЕТОД ПРОЕКЦИЙ НА ВЫПУКЛЫЕ МНОЖЕСТВА

Метод проекций на выпуклые множества является математически строгим методом решения задачи восстановления изображений с ограничениями [147, 148].

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

Пусть принадлежит некоторому набору выпуклых множеств Например, пусть множество всех неотрицательных функций. Очевидно, что является выпуклым множеством — всякая комбинация неотрицательна. Обозначим через пересечение

Если f принадлежит выпуклым множествам то она принадлежит также и их пересечению

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

В функциональном анализе известно, что если любое выпуклое подмножество то существует единственный элемент такой, что если элемент то

Выражение (4.35) и определяет оператор проекций на выпуклое множество. Если где проецирующий оператор, то

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

Если рассматривать норму это определение эквивалентно введенному ранее оператору ограничений (4.21). Метод проекций на выпуклые множества является более общим методом построения операторов ограничений.

Основным вопросом реализации восстанавливающего алгоритма является построение оператора, позволяющего найти решение, принадлежащее . Если каждое из множеств замкнуто и выпукло, то их пересечение также замкнуто и выпукло [5]. Нахождение решения в этом случае означает нахождение оператора проекции на Структура однако, более сложна, чем структура каждого из где Поэтому прямое построение такого оператора может быть сложной задачей. С другой стороны, для каждого из С существует фиксированная

точка отображения где — оператор проекции на Если построить некоторый общий оператор

то фиксированная точка отображения окажется элементом множества

Из (4.36) следует, что фиксированная точка отображения может быть найдена итерационным путем:

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

Доказана следующая теорема [15]. Если пересечение не является пустым множеством, то для любого выбора констант таких, что последовательность сходится к точке причем сходимость сильная, если хотя бы одна из подпоследовательностей сходится сильно.

Метод проекций на выпуклые множества тесно связан с итерационными алгоритмами, рассмотренными в предыдущем параграфе. Действительно, если оператор проекций на выпуклое множество совпадает по форме с оператором ограничений вида то, учитывая нерасширяющий характер операторов проекций, итерационный алгоритм (4.37) эквивалентен алгоритму (4.26). В этом смысле метод проекций на выпуклые множества является математическим обобщением алгоритмов на основе нерасширяющих операторов. У метода проекций на выпуклые множества, однако, существует ряд значительных преимуществ.

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

если имеется некоторое произвольное множество функций, которому предположительно принадлежит решение то достаточно проверить, является ли оно выпуклым и замкнутым, а затем, пользуясь правилом (4.35), сконструировать оператор проекции на этом множестве. В качестве примера приведем вывод выражения для оператора проекции на множество функций с ограниченной энергией определяемых неравенством

Это множество выпукло, так как

Это множество также является замкнутым, так как из -следует Найдем элемент минимизирующий норму

Пусть где мнимая единица, тогда

Второй интеграл не зависит от А, поэтому задача состоит в минимизации интеграла

Если разбить на два множества то легко видеть, что интеграл (4.39) по множеству минимизируется при Следовательно, при Таким образом, необходимо минимизировать (4.39) при условиях и

где неотрицательная переменная, такая что

Решая задачу минимизации, легко убедиться, что

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

Приведем некоторые интересные множества функций и операторы проекций на них. Подробности доказательств выпуклости и выражения для проецирующих операторов можно найти в [142, 148]. Операторы ограничений (4.21), (4.23) — (4.25) оказываются реализациями оператора проекций на выпуклые множества для соответствующих ограничений. Кроме того, можно использовать множество функций, удовлетворяющих условиям

Оператор проекции на это множество равен

где

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

где минимальная из функций Легко показать, что ограничение вида также является выпуклым. Некоторые другие проецирующие операторы будут рассмотрены также в § 4.5.

Второе крупное преимущество метода проекций на выпуклые множества состоит в том, что в некоторых случаях в отсутствие шума можно теоретически решить вопрос о единственности решения (т. е. выделить случац, когда пересечение множеств ограничений С о представляет собой одну точку).

Доказана теорема [147], которая утверждает, что если известны два множества такие, что

где — пустое множество, ортогональное дополнение то задача восстановления из проекции имеет единственное решение.

Приведем пример использования (4.43). Пусть множество всех функций с ограниченной пространственной протяженностью и известна проекция на множество функций с финитным спектром:

Тогда элементами являются функции, спектр которых определен на всей оси а элементами являются функции, спектр которых равен нулю на интервале Очевидно, пересечение есть пустое множество и возможно единственное восстановление сигнала по его низкочастотному спектру и информации об ограниченной пространственной протяженности. Соответствующий итерационный алгоритм записывается следующим образом:

где оператор ограничения протяженности спектра, — оператор ограничения протяженности сигнала.

Смысл алгоритма (4.44), называемого также алгоритмом Гершберга — Папулиса [68, 136], очень глубок. По существу, этот алгоритм показывает, что в отсутствие шумов можно восстановить спектральные составляющие, «отрезанные» системой формирования, в частности, можно преодолеть дифракционный предел разрешения (см. гл. 5).

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