12. Алгоритмы реконструкции с квадратичной оптимизацией

В данной главе будут рассмотрены итерационные процедуры, предназначенные для минимизации квадратной функции общего вида и включающие в себя как частные случаи ряд различных оптимизационных критериев, описанных в гл. 4. Указанные процедуры отличаются по своей сущности от алгебраических алгоритмов реконструкций и в литературе носят название «алгоритмы реконструкции с одновременными итерациями» (SIRT).

12.1. МАТЕМАТИЧЕСКОЕ ВВЕДЕНИЕ

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

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

где

при условии

Отметим, что правая часть соотношения (12.3) идентична функции (6.39), условие минимальности которой совпадает с обобщенным критерием квадратичной оптимизации, если

и

Выражение (6.39) представляло собой обобщение соотношений Теперь мы рассмотрим величины в каждом из перечисленных выше уравнений. В соответствии с приводимой ниже табл. являются единичными матрицами соответствующих размеров, матрицами соответствующих размеров с нулевыми элементами, — вектором со всеми нулевыми, ненулевыми компонентами .

В гл. 6 детально не обсуждалась сущность фигурирующей в соотношении (6.38) величины теперь этот недостаток будет исправлен. Хотелось бы только отметить, что В — неотрицательно определенная матрица, откуда следует, что выражениях [за исключением (6.34), когда ] представляет собой положительно определенную матрицу. Вот почему предполагалось, что в формуле (12.3) представляет собой либо положительно определенную матрицу, либо матрицу с нулевыми элементами.

Теперь основная задача состоит в сведении проблемы квадратичной оптимизации к решению совместной системы уравнений [пример решения подобной задачи встречался в разд. 11.3, в котором минимизируемая нами функция действительно представляла собой частный случай функции (12.3) при Мы здесь исследуем два случая, когда матрица положительно определена и когда нулевая матрица.

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

Таблица 12.1 (см. скан)

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

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

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

Введем новую векторную переменную и с помощью следующего соотношения:

Тогда

и из выражений (12.3) — (12.5) следует, что

Вводя обозначения

и

замечаем, что при выполнении условия (12.8)

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

Рассмотрим далее случай, когда и предположим, что а при минимизация никогда не достигается. Вновь введем переменную , на этот раз определенную как

Тогда

и из условий (12.3) и (12.4) следует, что

Вводя обозначения

и используя определение (12.12) для функции замечаем, что если условие (12.15) выполняется, то справедливо также соотношение

Из него следует, что минимизирует функцию тогда и только тогда, когда где и минимизирует функцию Поэтому в данном случае проблему нахождения элементов множества К, согласно (12.2), можно свести к нахождению значений и, минимизирующих функцию в выражении (12.12).

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

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

Интересным следствием полученных результатов является тот факт, что если система уравнений (12.20) не имеет решений, то множество К пустое. Однако в рассматриваемых нами случаях существование решения (12.20) гарантируется. Если определена соотношением (12.10), то положительно определенная матрица и поэтому имеет обратную матрицу. Немногим более сложно показать (детали мы опускаем), что система уравнений (12.20) также имеет решение, если определяются соотношениями (12.17) и (12.18) соответственно.

Как уже отмечалось, матрица имеет обратную матрицу, если положительно определенная матрица; таким образом, при этом имеется единственное значение минимизирующее функцию следовательно, единственное значение которое минимизирует Данное значение образует единственный элемент множества К, и поэтому вторичный критерий оптимальности (12.1) становится излишним.

Предположим, что — решение с минимальной нормой системы уравнений (12.20) в случае, когда Тогда среди векторов, минимизирующих функцию вектор и обладает наименьшей нормой. Определив величину с помощью соотношения замечаем, что среди векторов минимизирующих функцию вектор обладает наименьшим значением [см. комментарии, относящиеся к соотношению (12.19)]. Таким образом, мы считаем, что вектор найден.

Подводя итоги, можно отметить, что проблема квадратичной оптимизации, описываемая соотношениями (12.1) — (12.3), сведена здесь к проблеме решения системы уравнений (12.20). Если положительно определенная матрица, то система (12.20) имеет единственное решение, а если то при этом потребуется решение с минимальной нормой. В следующем разделе будет обсуждаться класс алгоритмов решения системы уравнений (12.20).