Уровень алгоритма

Алгоритм Качмажа

Материал из Алговики
Перейти к навигации Перейти к поиску


Алгоритм Качмажа (S. Kaczmarz)


Основные авторы описания: Е.С. Козлова, А.А. Иванов.

1 Общие сведения

1.1 Автор алгоритма

Стефан Качмаж (Stefan Kaczmarz) - польский математик, родился 1895 г. в городе Самбор (Sambor) Галиция (Galicia), Австро-Венгрия (Austria-Hungary), ныне Украина. Качмаж был профессором математики на факультете машиностроения университета Яна Казимира (Jan Kazimierz University) в городе Львов (Lwów) с 1919 по 1939 год, там же сотрудничал с Стефаном Банахом. Предложенный им итерационный метод послужил основой для многих современных технологий в обработке изображений, в том числе в задачах компьютерной томографии [1].

1.2 Краткая библиография

Применение метода С. Качмажа (S. Kaczmarz) [2] или т.н. метода алгебраической реконструкции наиболее известно в задачах реконструктивной компьютерной томографии высокого разрешения. Для интерпретации данных, полученных в результате неразрушающего сканирования некоторого объекта, с 60-70-х годов применяются различные аппаратные и программные реализации итерационного метода, разработанного польским математиком С. Качмажем (S. Kaczmarz) в 1937 году[3]; этот метод был использован Г. Хаусфилдом (G.N. Hounsfield) - конструктором первого томографа «ЭМИ-сканнер»[4] (нобелевская премия по физиологии и медицине в 1979 году).

Так же данный метод можно часто встретить под следующими названиями: Algebraic Reconstruction Technique (ART)[5][6][7], Projection onto Convex Sets (PCS)[8], Kaczmarz Algorithm [9] или метод ортогональных проекций.

Конструированию различных алгоритмов на основе итераций С. Качмажа посвящено существенное количество работ: согласно исследованию польского математика и библиографа А. Сигелски (A. Cegielski), на начало 2010 года статья С. Качмажа цитируется более чем в четырехстах реферируемых и значимых публикациях ученых из различных областей знаний. В Советской и Российской научных школах исследования итераций С. Качмажа представлены в литературе такими известными учеными как: В.Н. Ильин, Г.П. Васильченко, А.А. Светлаков и другие, например, в работах[10][11]. Общие идеи о проекционных методах так же представлены в классической работе Л. Г. Гурина, Б. Т. Поляка, Э. В. Райка[12], где впервые предлагается и обосновывается идентичный алгоритм для решения систем линейных алгебраических неравенств и уравнений.

В 2008 году американскими математиками Т. Штромером (T. Strohmer) и Р. Вершининым (R. Vershynin) в [13] была предложена рандомизированная модификация итерационного метода, в которой последовательность приближений к решению для совместных и переопределенных с.л.а.у. сходится с экспоненциальной скоростью.

Множество модификаций идеи метода ортогональных проекций нашли свое практическое применение в различных областях знаний, связанных с обработкой и интерпретацией больших объемов данных: при реконструкции синограмм в медицине, биологии, геологии; при решении задач диагностики плазмы, кристаллографии[14], дефектоскопии и микроскопии, параллельных вычислений и распределенного анализа[15] и др.

1.3 Геометрическая интерпретация

Метод алгебраической реконструкции достаточно просто формулируется с использованием его геометрической интерпретации. Рассмотрим совместную с.л.а.у. с двумя неизвестными

[math]A=\begin{pmatrix}3 & 2\\
2 & 3
\end{pmatrix},\text{ }f=\begin{pmatrix}1\\
2
\end{pmatrix}[/math]

и несовместную переопределенную, полученную добавлением к этой системе дополнительного уравнения [math]-u_{1}+u_{2}=1.5[/math]. Каждое уравнение из с.л.а.у. можно интерпретировать как гиперплоскость в пространстве координат, а решение совместной с.л.а.у. - как точку пересечения всех этих гиперплоскостей. При использовании метода алгебраической реконструкции для решения с.л.а.у. поиск приближенного решения осуществляется в направлениях, перпендикулярных к гиперплоскостям, каждая из которых описывается отдельным уравнением решаемой системы (см. Рис.1).

Рисунок 1. К геометрической интерпретации метода алгебраической реконструкции: слева --- случай совместной с.л.а.у., справа --- несовместной с.л.а.у.

Интерактивная диаграмма для совместного случая подготовлена авторами статьи здесь (Notes about S. Kaczmarz algorithm - consistent case), а для несовместного случая здесь (Notes about S. Kaczmarz algorithm - inconsistent case). Данные диаграммы позволяют регулировать параметры с.л.а.у. и начальное приближение, что позволяет наглядно демонстрировать сходимость итерационной последовательности.

Описанные результаты наводят на очевидную идею - проекционная последовательность влияет на скорость сходимости метода ортогональных проекций. Обратите внимание на Рис.2.

Рисунок 2. Выбор последовательности проектирования в алгоритме С. Качмажа: К выбору последовательности ортогональных проекций: слева - последовательность проектирования начинается от первого к последнему уравнению и в обратном порядке - от последнего к предпоследнему (symART[16][17][18]), а справа - последовательность строится циклическим способом (от последнего к первому уравнению и т.д.)

Как показано на Рис. 2 - итерационная последовательность, в случае Рис. 2 (справа) сходится вообще за конечное число итераций.

1.4 Математическая запись алгоритма

Запишем совместную (в общем случае - переопределенную) с.л.а.у.

[math]Au=f,\, A\in R^{m\times n},\, u\in R^{n},\, f\in R^{m},[/math]

тогда итерации согласно алгоритму определяются последовательностью

[math]u^{k+1}=u^{k}+\lambda_{k}\frac{f_{j\left(k\right)}-\left(a_{j\left(k\right)},u^{k}\right)}{\Vert a_{j\left(k\right)}\Vert^{2}}a_{j\left(k\right)},[/math]

где

[math]A=\left(a_{1},\, a_{2},\,\ldots\,,\, a_{m}\right)^{T}\in R^{m\times n},\, u\in R^{n},\, f=\left(f_{1},\, f_{2},\,\ldots\,,\, f_{m}\right)\in R^{m},[/math]

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

[math]j\left(k\right)=\left(k\ \bmod\ m\right)+1,\, k=\overline{0,\infty},[/math]

где [math]k[/math] - номер итерации, [math]u^{0}[/math] - начальное приближение, а [math]\lambda_{k}[/math] - параметр релаксации (Рис. 2 построен для случая, когда [math]\lambda_{k}=1,\,\forall k[/math]).

2 Рандомизированная версия алгоритма и скорость сходимости

3 Программная реализация

4 Параллельные реализации

5 Классификация проекционных последовательностей

Рисунок 3. Классификация правил для задания проекционной последовательности в алгоритме C. Качмажа

Под проекционной последовательностью понимается порядок обхода уравнений системы в процессе итераций алгоритма Качмажа. А рассматриваемая последовательность задается с использованием правила [math]j\left(k\right)[/math], где [math]k\in N_{0}[/math] которое позволяет вычислить номер используемого уравнения на итерации с номером [math]k[/math]. Правило [math]j\left(k\right)[/math]рассматривать как сюръективное отображение множества [math]N_{0}[/math] на множество [math]\left\{ 1,2,\ldots,m\right\}[/math], где [math]m[/math] - количество уравнений в с.л.а.у. [math]Au=f,\ A\in R^{m\times n},\ u\in R^{n},\ f\in R^{m}[/math].

Отображения такого вида могут быть как детерминированными, так и случайными, рандомизированными. В последнем случае [math]j\left(k\right)[/math] является дискретной случайной величиной с заданным законом распределения. Например, к детерминированным отображениям необходимо отнести:

  • правило циклического обхода [math]j\left(k\right)=\left(k\bmod m\right)+1,\, k=\overline{0,\infty}[/math];
  • метод четной перестановки - эвристический метод для задач компьютерной томограции из [19];
  • симметричное правило (symmetric ART), в котором последовательность проектирования на гиперплоскости идет в начале в прямом порядке от первого уравнения к последнему, а затем в обратном порядке - от последнего - к первому.

Существенно важной является классификация рассматриваемых правил по их зависимости от данных. Например, результат из [20], где [math]j\left(k\right)[/math] является дискретной случайной величиной с заданным законом распределения [math]P\left(j\left(k\right)=i\right)=\frac{\left\Vert a_{i}\right\Vert _{2}^{2}}{\left\Vert A\right\Vert _{F}^{2}}[/math], где [math]\left\Vert \cdot\right\Vert _{F}[/math] - матричная норма Фробениуса и [math]\left\Vert a_{i}\right\Ver[/math] - евклидова норма строки матрицы с.л.а.у. с номером [math]i=\overline{1,m}[/math]. Этот результат качественно отличается от всех известных рандомизированных способов наличием зависимости от матрицы с.л.а.у - от исходных данных задачи.

5.1 Алгоритм с четной перестановкой

6 Алгоритм Качмажа как метод максимального уменьшения ошибки на каждой итерации

7 References

  1. Natterer, Frank (2001), "V.3 Kaczmarz's method", The Mathematics of Computerized Tomography, Classics in Applied Mathematics 32, SIAM, p. 128, ISBN 9780898714937.
  2. 1
  3. Kaczmarz, S. Angenäherte Auflösung von Systemen linearer Gleichungen [Текст] / S. Kaczmarz // Bulletin International de l'Académie Polonaise des Sciences et des Lettres / Classe des Sciences Mathématiques et Naturelles. Série A, Sciences Mathématiques. — 1937. — Vol. 35. — С. 355-357.
  4. Hounsfield, G. N. A Discussion on Recent Developments in Medical Endoscopy and Related Fields [Текст] / G. N. Hounsfield // Proceedings of the Royal Society of London. Series B, Biological Sciences. — 1977. — Vol. 195, N. 1119. — С. 281-289.
  5. Gordon, R. Algebraic reconstruction techniques (ART) for three-dimensional electron microscopy and x-ray photography [Текст] / R. Gordon, R. Bender, G. T. Herman // Journal of theoretical biology. — 1970. — Vol. 29, Issue 3. — С. 471–481.
  6. Micke, A. The Mathematics of Computerized Tomography [Текст] / A. Micke, F. Natterer // ZAMM - Zeitschrift für Angewandte Mathematik und Mechanik (Journal of Applied Mathematics and Mechanics). — 1987. — Vol. 67, Issue 11. — С. 580. —ISBN 3-519-02103-X and 0-471-90959-9.
  7. Herman, G. T. Fundamentals of computerized tomography: Image reconstruction from projection [Текст] : 2nd ed. / G. T. Herman. — Springer, 2009. — 300 с.
  8. Sezan, K. M. Applications of convex projection theory to image recovery in tomography and related areas [Текст] / K. M. Sezan, H. Stark // Image Recovery: Theory and Application / H. Stark, editor. — Academic Press, 1987. — С. 415-462.
  9. Cegielski, A. Bibliography on the Kaczmarz method [Электронный ресурс] : Faculty of Mathematics, Computer Science and Econometrics University of Zielona Gora ; Poland, March, 28th, 2010 / Режим доступа: http://www.uz.zgora.pl/~acegiels/Publikacje-Kaczmarz.pdf
  10. Ильин, В. П. Об итерационном методе Качмажа и его обобщениях [Текст] / В. П. Ильин // Сибирский журнал индустриальной математики. — 2006. — Т. 9, вып. 3. — С. 39–49.
  11. Г. П. Васильченко, А. А. Светлаков, “Проекционный алгоритм решения систем линейных алгебраических уравнений большой размерности”, Ж. вычисл. матем. и матем. физ., 20:1 (1980), 3–10.
  12. Л. Г. Гурин, Б. Т. Поляк, Э. В. Райк, “Методы проекций для отыскания общей точки выпуклых множеств”, Ж. вычисл. матем. и матем. физ., 7:6 (1967), 1211–1228
  13. Strohmer, T. A Randomized Kaczmarz Algorithm with Exponential Convergence [Текст] / T. Strohmer, R. Vershynin // Journal of Fourier Analysis and Applications. — 2009. — Vol. 15, Issue 2. — С. 262-278.
  14. Marks, L. D. A feasible set approach to the crystallographic phase problem [Текст] / L. D. Marks, W. Sinkler, E. Landree // Acta Crystallographica Section A. — 1987. — Vol. 55, Issue 4. — С. 601-612.
  15. JElble, J. M. GPU computing with Kaczmarz’s and other iterative algorithms for linear systems [Текст] / J. M. Elble, N. V. Sahinidis, P. Vouzis // Parallel Computing. — 2010. — Vol. 36, Issues 5-6. — С. 215–231.
  16. Bjorck, A. Accelerated projection methods for computing pseudoinverse solutions of systems of linear equations [Текст] / A. Bjorck, T. Elfving // BIT Numerical Mathematics. — 1979. — Vol. 19, Issue 2. — С.145-163.
  17. Nikazad, T. Algebraic Reconstruction Methods [Текст] : PhD. Thesis, Linköping University / T. Nikazad. — Linköping, 2008.
  18. Kamath, G. Component-Average Based Distributed Seismic Tomography in Sensor Networks [Текст] / G. Kamath, L. Shi, W.-Z. Song // IEEE International Conference on Distributed Computing in Sensor Systems. — 2013. — С. 88-95.
  19. Guan H. A projection access order for speedy convergence of ART (algebraic reconstruction technique): a multilevel scheme for computed tomography [Текст] / Guan H., R. Gordon // Physics in Medicine and Biology. — 1994. — Vol. 39, N. 11. — С. 2005-2022.
  20. Strohmer, T. A Randomized Kaczmarz Algorithm with Exponential Convergence [Текст] / T. Strohmer, R. Vershynin // Journal of Fourier Analysis and Applications. — 2009. — Vol. 15, Issue 2. — С. 262-278.