Convergence of the Quasi-Optimal Kaczmarz algorithm.

Demonstrates the change in the rate of convergence of the Quasi-Optimal Kaczmarz algorithm (awaiting publication).


Author & Reference

Ivanov Andrey, Graduate student,

Dept. of Applied Mathematics, S. P. Korolyov Samara State Aerospace University (National Research University), Faculty of Computer Science, Samara, Russia.

See more for Regularization Tools dependency

addpath ('../libs/regu/');

See more for AIRTools dependency

addpath ('../libs/AIRtools/AIRtools/');

Generate test problem

Discretization of the "famous" Fredholm integral equation of the frst kind deviced by D. L. Phillips, see more in [6].

[A,f,u_true] = phillips(512);
[m,n] = size(A);

N = [1:1:6000];

Execute the Kaczmarz (KM) alg

[x0 info0] = kaczmarz(A,f,N);
error_x0 = zeros(1,size(x0,2));
for i = 1:1:length(error_x0)
    error_x0(i) = norm(x0(:,i)-u_true,2);

Execute the Randomized Kaczmarz (RKM) alg

[x2 info2] = randkaczmarz(A,f,N);
error_x2 = zeros(1,size(x0,2));
for i = 1:1:length(error_x0)
    error_x2(i) = norm(x2(:,i)-u_true,2);

options.stoprule.type = 'NR';
options.stoprule.epsilon = 10^-8;

Execute the QO-Kaczmarz (QO-KM) alg.

[x1 info1] = qoptimalkaczmarz(A,f,N,[],options);

error_x1 = zeros(1,size(x1,2));
for i = 1:1:length(error_x1)
    error_x1(i) = norm(x1(:,i)-u_true,2);

Plot the results

Compare solutions

plot(1:1:length(x0(:,end)), x0(:,end), 'r', ...
     1:1:length(x1(:,end)), x1(:,end), 'g', ...
     1:1:length(x2(:,end)), x2(:,end), 'b--', ...
     1:1:length(u_true)   , u_true   , 'c');
legend('KM', ...
       'QO-KM', ...
       'RKM', ...
       'Exact Solution');

Compare convergence rate

semilogy (1:1:length(error_x0), error_x0, 'r',...
          1:1:length(error_x1), error_x1, 'g', ...
          1:1:length(error_x2), error_x2, 'b');
legend('KM', ...
       'QO-KM', ...