Code covered by the BSD License  

Highlights from
Regularization Kaczmarz Tools Version 1.0 for Matlab

image thumbnail

Regularization Kaczmarz Tools Version 1.0 for Matlab

by

 

07 Oct 2013 (Updated )

Regularization Column version of Kaczmarz algorithmfor solving ill-posed systems

Convergence of the regularized form of the Column-Kaczmarz algorithm.

Convergence of the regularized form of the Column-Kaczmarz algorithm.

Demonstrates the change in the rate of convergence of the regularized form of the Column-Kaczmarz algorithm.

Contents

Author & Reference

Ivanov Andrey, Graduate student, ssauivanov@gmail.com.

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

  • [1] A. I. Zhdanov, The method of augmented regularized normal equations, Computational Math- ematics and Mathematical Physics, 52 (2012), pp. 194-197.
  • [3] T. Strohmer and R. Vershynin, A randomized Kaczmarz algorithm for linear systems with exponential convergence, J. Fourier Analysis and Applications, 15 (2009), pp. 262-278.
  • [4] G. P. Vasil'chenko and A. A. Svetlakov, A projection algorithm for solving systems of linear algebraic equations of high dimensionality, USSR Computational Mathematics and Mathematical Physics, 20 (1980), pp. 1-8.
  • [5] V. A. Morozov, Methods of solving incorrectly posed problems, Springer Verlag, New York, 1984.

See more for Regularization Tools dependency

addpath ('../regu/');

See more for AIRTools dependency

addpath ('../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); %or may be shaw(512);
[m,n] = size(A);

Add noize to f vector

noize_value = 0.015;
noize = randn(size(f));
noize = (noize/norm(noize)) * norm(f) * noize_value;
d = (norm(noize) / norm(f)) * 100;

fn = f + noize;

Some estimation perturbation

delta = norm(f-fn);

One of the heuristic methods to select regularization parameter

See more: V. A. Morozov, Methods of solving incorrectly posed problems, Springer Verlag, New York, 1984.

sigmaMax = max(svd(A));
alpha = ((sigmaMax^2)*delta/(norm(f)+delta));

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

N = [1:1:4000];

Execute the Kaczmarz-Column-Regularization (KCR) alg.

[x1 info1] = columnkaczmarz(A,fn,N,[],options);

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

Execute the Kaczmarz-Random-Column-Regularization (KRCR) alg.

[x2 info2] = randcolumnkaczmarz(A,fn,N,[],options);

error_x2 = zeros(1,size(x2,2));
for i = 1:1:length(error_x2)
    error_x2(i) = norm(x2(:,i)-x2(:,end),2);
end;

Plot the results

figure;
semilogy (1:1:length(error_x1), error_x1, 'r',...
          1:1:length(error_x2), error_x2, 'k');
legend('Error KCR','Error KRCR');

figure;
plot(1:1:length(x1(:,end)), x1(:,end), 'r', ...
     1:1:length(x2(:,end)), x2(:,end), 'k', ...
     1:1:length(u_true)   , u_true   , 'g');
legend('Solution with KCR','Solution with KRCR', 'Solution of the exact problem');

Contact us