The row-oriented form of the regularized Kaczmarz’s method

Abstract


This paper presents the new iterative method for solving the standard Tikhonov regularization problem. The basis of the method is the application the projection Kaczmarz algorithm to the augmented regularized normal system of equations. The use of the augmented regularized normal system of equations, instead the system of regularized normal equations, makes it possible to significantly reduce the spectral condition number of the original problem. The paper presents the row-oriented form of the regularized Kaczmarz algorithm. This form of the regularized Kaczmarz algorithm allows to solve problems in which the data are received sequentially (line by line). The proposed algorithm makes it possible to effectively calculate solutions of problems with sparse matrices of large and superlarge dimensions. The comparison’s results of the proposed row-oriented form of the algorithm with the column-oriented form of this algorithm are presented. By considering a certain classes of problems, the paper demonstrates that the proposed form of the regularized algorithm allows to reduce the number of iterations in comparison with the column-oriented form of the algorithm.

Full Text

Введение. Итерационные методы являются эффективным средством решения систем линейных алгебраических уравнений (СЛАУ), возникающих в различных прикладных задачах. При большой размерности и разреженности СЛАУ итерационные алгоритмы порой являются единственным доступным инструментом их решения [1]. В последние годы вновь возник интерес к проекционному алгоритму Качмажа [2]. Впервые данный алгоритм был успешно применён в компьютерной томографии для реконструкции изображений [3]. Алгоритм Качмажа имеет очень простую структуру, но из-за низкой скорости сходимости не нашел широкого применения в других прикладных областях. В работе [4] на основе процедуры рандомизации был предложен способ ускорения скорости сходимости алгоритма Качмажа. Данная статья позволила расширить область применения алгоритма Качмажа [5-10]. Для решения стандартной задачи регуляризации А. Н. Тихонова в статье [11] предложена столбцово-ориентированная форма регуляризованного алгоритма Качмажа и показана эффективность регуляризованного алгоритма при решении определенного класса прикладных задач. Однако итерационный алгоритм [11] не позволяет решать задачи, данные в которых поступают последовательно (построчно). Подобные задачи возникают, например, при обработке изображений. В предлагаемом сообщении рассматривается строчно-ориентированная форма регуляризованного алгоритма Качмажа. 1. Постановка задачи. Рассмотрим стандартную задачу регуляризации А. Н. Тихонова: minn Au - f 2 + α u , (1) u∈R Rm×n , Rm , где A ∈ f ∈ α > 0 - параметр регуляризации, · = · 2 - евклидова векторная норма. Как известно, все итерационные алгоритмы решения задачи (1) основаны на решении уравнений Эйлера (регуляризованных нормальных уравнений) A A + αEn u = A f. (2) Главный недостаток использования системы (2) для решения задачи (1) - спектральное число обусловленности задачи (2) равно квадрату спектрального числа обусловленности матрицы A в задаче (1). В работе [12] для решения задачи (1) предложена расширенная регуляризованная нормальная система уравнений: ωEm A A -ωEn y u = f 0 ⇔ Bw θ = q, (3) где Bw = b1 , . . . , bm+n ∈ R(m+n)×(m+n) , θ = y , u ∈ Rm+n , q = = (f , 0, . . . , 0) = (q1 , . . . , qm+n ) ∈ Rm+n ; qi = fi , i = 1, . . . , m; qi = 0, 547 Ж д а н о в А. И., С и д о р о в Ю. В. √ i = m + 1, . . . , m + n; ω = α; Em , En - единичные матрицы соответствующих порядков. Матрица Bw системы (3) при α > 0 невырождена и система (3) имеет единственное решение θ∗ = (y∗ , u∗ ) , где u∗ - решение задачи (2), а y∗ = = ω -1 (f - Au∗ ) [12]. Одним из преимуществ расширенной регуляризованной нормальной системы уравнений (3) является существенно меньшее спектральное число обусловленности матрицы Bw по сравнению со спектральным числом обусловленности матрицы A задачи (1) [12], т. е. κ2 (Bw ) = κ2 (A A + αEn ). Так как матрица Bw системы (3) при α > 0 является невырожденной квадратной матрицей, сама система (3) является совместной и, следовательно, как показано в работе [13], имеет единственное решение θ∗ , которое может быть получено применением итерационного метода Качмажа к расширенной системе (3). Алгоритм Качмажа для расширенной системы (3) можно записать в следующем виде, используя «микроитерации» [14]: θk+1 = θk + (qs - bs θk ) bs , bs 2 (4) где k = 0, 1, 2, . . . ; s = s(k) = (k mod (m + n)) + 1, т. е. {s (k)}∞ k=0 - периодическая последовательность вида 1, 2, . . . , m + n, . . . 1, 2, . . . , m + n, . . . . Так как система (3) совместная, то при любом начальном значении θ0 = = (y0 , u0 ) итерационная последовательность {θk }∞ k=0 , формируемая рекуррентным выражением (4), сходится к вектору θ∗ : lim θk - θ∗ = 0, k→∞ где θ∗ = (y∗ , u∗ ) , u∗ = (A A + αEn )-1 A f , y∗ = ω -1 (f - Au∗ ). Покажем, что за счет использования условий согласования, по аналогии со столбцово-ориентированной формой регуляризованного алгоритма Качмажа [11], для системы (3) можно получить сокращенный вариант строчноориентированной формы регуляризованного алгоритма. 2. Строчно-ориентированная форма регуляризованного алгоритма Качмажа. Запишем систему (3) в виде системы матричных уравнений: y + Au = f, (5) A y - ωu = 0. (6) Если в качестве условий согласования начальных значений u0 , y0 пользовать уравнение (5): исy0 = ω -1 (f - Au0 ) , то применив алгоритм Качмажа к уравнению (6), как показано в [11], получаем столбцово-ориентированную регуляризованную форму алгоритма Качмажа. 548 Строчно-ориентированная форма регуляризованного метода Качмажа Пусть начальные значения y0 , u0 будут удовлетворять условию согласования u0 = ω -1 A y0 , (7) которые получены на основании уравнения (6), и применим алгоритм Качмажа к уравнению (5). Ниже будет показано, что из условия согласования (7) следует выполнение условия uk = ω -1 A yk (8) для всех k 0. Тогда рекуррентные выражения строчно-ориентированной формы алгоритма можно записать в виде yk+1 = yk + ω k ej , uk+1 = uk + k aj ; k = fj - ωej yk - aj uk aj 2 + ω2 . (9) Здесь A = (a1 , . . . , am ) ∈ Rm×n , f = (f1 , . . . , fm ) ∈ Rm , Em = (e1 e2 . . . em ); k = 0, 1, 2, . . . ; j = j(k) = (k mod m) + 1; {j (k)}∞ k=0 - периодическая последовательность вида 1, 2, . . . , m, 1, 2, . . . m, . . . ; начальные условия u0 и y0 удовлетворяют (7). Таким образом, рекуррентные выражения (9) соответствуют алгоритму Качмажа (4), примененным к (5) при s = s (k) = 1, 2, . . . , m. Теорема 1. Пусть в (9) начальные значения θ0 = (y0 , u0 ) удовлетворяют условию согласования (7). Тогда θk → θ∗ при k → ∞, где θk = (yk , uk ) определяются из рекуррентных выражений (9), а θ∗ = (y∗ , u∗ ) . Д о к а з а т е л ь с т в о. Докажем по индукции, что из условия согласованности (7) начальных значений y0 , u0 следует выполнение условия согласованности (8) при любых k 0, где yk и uk вычисляются из рекуррентных выражений (9). При k = 0 на основании условий теоремы имеем u0 = ω -1 A y0 . При k = 1 из (9) получаем ω -1 A y1 = ω -1 A (y0 + ω 0 e1 ) = ω -1 A y0 + u0 0A e1 = u0 + 0 a1 = u1 . (10) a1 Таким образом, из (10) следует, что ω -1 A y1 = u1 . Пусть (8) выполняется для некоторого произвольного k = ν > 1. uν = ω -1 A yν . (11) Покажем тогда, что из справедливости (11) для k = ν следует справедливость (8) при k = ν + 1. Из рекуррентных выражений (9) получаем ω -1 A yν+1 = ω -1 A yν + ω ν ej(ν+1) = ω -1 A yν + νA = ej(ν+1) = uν + ν aj(ν+1) = uν+1 . (12) 549 Ж д а н о в А. И., С и д о р о в Ю. В. Из выражения (12) следует, что ω -1 A yν+1 = uν+1 , и как следствие этого - справедливость (8) для любых k ∈ N. Следовательно, если u0 и y0 удовлетворяют условию согласования (7), то алгоритм Качмажа (4) достаточно применить только для матричной системы уравнений (5), так как для выражения (4) из справедливости (8) следует, что θk+1 = θk для всех s = s(k) = m + 1, . . . , m + n. Докажем справедливость этого факта. Для всех s = s(k) = 1, . . . , m имеем алгоритм (4), а для всех s = s(k) = = m + 1, . . . , m + n получим θk+1 = θk - βk где βk = (qs ,-ω˜ es )θk , qs 2 +ω 2 qs -ω˜ es , а A = (q1 q2 . . . qn ), En = (˜ e1 e˜2 . . . e˜n ). Из условия (8) следует, что bs θk = qs , -ω˜ es θk = qs yk - ω˜ es uk = qs yk - e˜s A yk = 0. qs Таким образом для всех s = s(k) = m + 1, . . . , m + n βk = 0 и, следовательно, θk+1 = θk . Из теоремы 1 непосредственно следует, что при нулевых начальных условиях u0 = 0 и y0 = 0 алгоритм (9) будет сходиться, т. е. θk → θ∗ при k → ∞, так как эти начальные условия удовлетворяют условию согласования (7). 3. Тестовые исследования. Проведем сравнение столбцово-ориентированной [11] и строчно-ориентированной, полученной в данном сообщении, форм регуляризованного алгоритма Качмажа на двух тестовых задачах с матрицей A полного столбцового и не полного столбцового рангов. Тестовая задача 1. Рассмотрим матрицу A= 1 2 3 4 , rank(A) = 2 и правую часть f = (1, 2) . При заданном параметре регуляризации α = 0.1 вычислялось точное регуляризованное решение u∗ = (A A + αEn )-1 A f. В табл. 1 приведены общее число внутренних и внешних итераций, а также общее число k «микроитераций», необходимые для получения регуляризованного решения u∗ для столбцово-ориентированной и строчно-ориентированной форм регуляризованного алгоритма Качмажа с условием остановки uk - uk-1 < 10-8 . Из табл. 1 видно, что алгоритму Качмажа в строчно-ориентированной форме для нахождения решения тестовой задачи 1 с заданной точностью требуется в 1.7 раз меньше внешних итераций, чем алгоритму в столбцовоориентированной форме [11], при одинаковом числе внутренних итераций. Тестовая задача 2. Рассмотрим матрицу   1 2 3 A =  . . . . . . . . .  ∈ R15×3 , rank(A) = 2 43 44 45 550 Строчно-ориентированная форма регуляризованного метода Качмажа Таблица 1 Число итераций для тестовой задачи 1 [The number of iterations for the test problem 1] The algorithm form column-oriented [11] row-oriented The number of The number of The number k of internal iterations external iterations micro iterations 2 2 422 237 844 474 u∗ - uk 2.71 · 10-7 1.66 · 10-7 и правую часть f = (1, . . . , 15) ∈ R15 . При заданном параметре регуляризации α = 0.1 вычислялось точное ре-1 гуляризованное решение u∗ = A A + αEn A f с условием остановки итераций uk - uk-1 < 10-8 . Отметим, что для нахождения решения тестовой задачи 2 строчно-ориентированная форма алгоритма Качмажа требует в 5 раз больше внутренних итераций, чем столбцово-ориентированная форма алгоритма [11]. В табл. 2 приведены данные по числу итераций, необходимых для получения регуляризованного решения u∗ с заданной точностью по обеим формам регуляризованного алгоритма Качмажа. Таблица 2 Число итераций для тестовой задачи 2 [The number of iterations for the test problem 2] The algorithm form column-oriented [11] row-oriented The number of The number of The number k of internal iterations external iterations micro iterations 3 15 297 751 44 049 893 253 660 735 u∗ - uk 5.21 · 10-4 6.85 · 10-5 Из табл. 2 видно, что несмотря на то, что предложенная строчно-ориентированная форма алгоритма Качмажа требует большего числа внутренних итераций, она по сравнению со столбцово-ориентированной формой позволяет существенно снизить число внешних итераций, при этом уменьшается и общее число «микроитераций». При решении тестовой задачи 2 с заданной точностью эти «снижения» составляют 6.7 и 1.3 раз, соответственно. Заключение. В данном сообщении предлагается строчно-ориентированная форма регуляризованного алгоритма Качмажа, которая позволяет проводить последовательную (построчную) обработку данных, аналогично классическому алгоритму Качмажа. Преимуществом рассматриваемой формы регуляризованного алгоритма (9), в отличие от столбцово-ориентированной формы алгоритма, полученного в работе [11], является последовательный доступ к поступающим данным, что может быть эффективно использовано для решения прикладных задач, возникающих в компьютерной томографии и обработки изображений. Как показано в тестовых исследованиях, представленная строчно-ориентированная форма регуляризованного алгоритма (9) позволяет уменьшить число итераций для нахождения решений определенного класса задач по сравнению со столбцово-ориентированной формой алгоритма, полученного в [11]. Следует отметить, что для столбцово-ориентированной формы регуля551 Ж д а н о в А. И., С и д о р о в Ю. В. ризованного алгоритма Качмажа существует параллельная реализация для многоядерных (многопроцессорных) систем [15], а для получения параллельной версии строчно-ориентированной формы алгоритма можно использовать результаты работы [16]. Исследованию регуляризованных вариантов алгоритма Качмажа, основанных на расширенных системах (предложенных в работе [12]), также посвящена недавно опубликованная работа [17]. Конкурирующие интересы. Мы не имеем конкурирующих интересов. Авторский вклад и ответственность. Все авторы принимали участие в разработке концепции статьи и в написании рукописи. Авторы несут полную ответственность за предоставление окончательной рукописи в печать. Окончательная версия рукописи была одобрена всеми авторами. Финансирование. Исследование выполнялось без финансирования.

About the authors

Alexander I Zhdanov

Samara State Technical University

Email: zhdanovaleksan@yandex.ru
244, Molodogvardeyskaya st., Samara, 443100, Russian Federation
Dr. Phys. & Math. Sci., Professor; Head of Department; Dept. of Higher Mathematics & Applied Computer Science

Yuri V Sidorov

Samara State Technical University

Email: linuxboy2007@gmail.com
244, Molodogvardeyskaya st., Samara, 443100, Russian Federation
Senior Lecturer; Dept. of Higher Mathematics & Applied Computer Science

References

  1. Saad Y. Iterative Methods for Sparse Linear Systems. Philadelphia, PA, USA: Society for Industrial and Applied Mathematics, 2003. xviii+528 pp. doi: 10.1137/1.9780898718003.
  2. Kaczmarz S. Angenäherte Auflösung von Systemen linearer Gleichungen // Bull. Int. Acad. Polon. Sci. A, 1937. no. 35. pp. 355-357 ; Kaczmarz S. Approximate solution of systems of linear equations // Int. J. Control, 1993. vol. 57, no. 6. pp. 1269-1271. doi: 10.1080/00207179308934446.
  3. Gordon R., Bender R., Herman G. T. Algebraic Reconstruction Techniques (ART) for threedimensional electron microscopy and X-ray photography // J. Theor. Biol., 1970. vol. 29, no. 3. pp. 477-481. doi: 10.1016/0022-5193(70)90109-8.
  4. Strohmer T., Vershynin R. A Randomized Kaczmarz Algorithm with Exponential Convergence // J. Fourier Anal. Appl., 2009. vol. 15. pp. 262-278, arXiv: math/0702226 [math.NA]. doi: 10.1007/s00041-008-9030-4.
  5. Needell D. Randomized Kaczmarz solver for noisy linear systems // BIT Numer. Math., 2010. vol. 50, no. 2. pp. 395-403, arXiv: 0902.0958 [math.NA]. doi: 10.1007/s10543-010-0265-5.
  6. Needell D., Tropp J. A. Paved with good intentions: Analysis of randomized block Kaczmarz method // Linear Alg. Appl., 2014. vol. 441. pp. 199-221, arXiv: 1208.3805 [math.NA]. doi: 10.1016/j.laa.2012.12.022.
  7. Needell D., Zhao R., Zouzias A. Randomized block Kaczmarz method with projection for solving least squares // Linear Alg. Appl., 2015. vol. 484. pp. 322-343, arXiv: 1403.4192 [math.NA]. doi: 10.1016/j.laa.2015.06.027.
  8. Gower R., Richtarik P. Randomized Iterative Methods for Linear Systems // SIAM. J. Matrix Anal. Appl., 2015. vol. 36, no. 4. pp. 1660-1690, arXiv: 1506.03296 [math.NA]. doi: 10.1137/15M1025487.
  9. Wei K. Solving systems of phaseless equations via Kaczmarz methods: a proof of concept study // Inverse Problems, 2015. vol. 31, no. 12, 125008, arXiv: 1502.01822 [math.NA]. doi: 10.1088/0266-5611/31/12/125008.
  10. Shin Y., Xiu D. A Randomized Algorithm for Multivariate Function Approximation // SIAM J. Sci. Comput., 2017. vol. 39, no. 3. pp. A983-A1002. doi: 10.1137/16M1075193.
  11. Ivanov A., Zhdanov A. Kaczmarz algorithm for Tikhonov regularization problem // Appl. Math. E-Notes, 2013. vol. 13. pp. 270-276.
  12. Жданов А. И. Метод расширенных регуляризованных нормальных уравнений // Ж. вычисл. матем. и матем. физ., 2012. Т. 52, № 2. С. 205-208.
  13. Tanabe K. Projection Method for Solving a Singular System of Linear Equations and its Applications // Numer. Math., 1971. vol. 17, no. 3. pp. 203-214. doi: 10.1007/BF01436376.
  14. Ильин В. П. Об итерационном методе Качмажа и его обобщениях // Сиб. журн. индустр. матем., 2006. Т. 9, № 3. С. 39-49.
  15. Жданов А. И., Сидоров Ю. В. Параллельная реализация рандомизированного регуляризованного алгоритма Качмажа // Комп. оптика, 2015. Т. 39, № 4. С. 536-541. doi: 10.18287/0134-2452-2015-39-4-536-541.
  16. Liu Ji, Wright S. J., Sridhar S. An Asynchronous Parallel Randomized Kaczmarz Algorithm, 2014, arXiv: 1401.4780 [math.NA].
  17. Hefny A., Needell D., Ramdas A. Rows versus Columns: Randomized Kaczmarz or Gauss-Seidel for Ridge Regression // SIAM J. Sci. Comput., 2017. vol. 39, no. 5. pp. S528-S542, arXiv: 1507.05844 [math.NA]. doi: 10.1137/16M1077891.

Statistics

Views

Abstract - 17

PDF (Russian) - 19

Cited-By


PlumX

Dimensions

Refbacks

  • There are currently no refbacks.

Copyright (c) 2017 Samara State Technical University

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

This website uses cookies

You consent to our cookies if you continue to use our website.

About Cookies