Prev: i have question about simulink (error calculation block)
Next: how to get a m-by-n matrix from grayscale image?
From: Cheng Cosine on 14 Jun 2010 04:19
Hi:

I tried the following algorithm to see if I can get min norm LS soln
for


solving min f, f = 0.5*norm( A*x-b ), A is m-by-n and m < n. But the
algorithm


did not converge to the min norm LS soln. Does anyone know what's
wrong?


The algorithm used is:


x(k+1) = x(k)-pinv(A)*f(k)


The algorithm was tested using the following Matlab scripts.


Thanks,


A = [1, 2, 3, 4;
4, 5, 6, 7;
7, 8, 9, 10;
8, 4, 9, 1];
x_true = [9; 1; 6; 2];
b = A*x_true;


% Setup the under-determined system
N = 2;
A_und = A(1:N,:); b_und = b(1:N);
x_minLS = pinv(A_und)*b_und;
J_und = A_und;


x_guess = rand(size(x_minLS));


IterMaxNo = 500; IterDelta = 1.0E-7;


% compatible case
[x_und_gnpinv, n_iter] = ...
gnpinvL(x_guess, J_und, A_und, b_und, IterMaxNo, IterDelta);


function [y, n] = gnpinvL(x_old, J, A, b, IterMaxNo, IterDelta)


n = 0;


while ( n <= IterMaxNo )
f = A*x_old-b;
tmp = pinv(J)*f;
x_new = x_old-tmp;
n = n+1;


DiffNorm = norm(f);


if DiffNorm < IterDelta
y = x_new;
fprintf(' Converged! \n');
return
end % if converged


x_old = x_new;
end % while


y = x_new;
fprintf(' Iteration Exceeded! \n');


From: Torsten Hennig on 14 Jun 2010 00:50
> Hi:
>
> I tried the following algorithm to see if I can get
> t min norm LS soln
> for
>
>
> solving min f, f = 0.5*norm( A*x-b ), A is m-by-n and
> m < n. But the
> algorithm
>
>
> did not converge to the min norm LS soln. Does anyone
> know what's
> wrong?
>
>
> The algorithm used is:
>
>
> x(k+1) = x(k)-pinv(A)*f(k)
>
>
> The algorithm was tested using the following Matlab
> b scripts.
>
>
> Thanks,
>
>
> A = [1, 2, 3, 4;
> 4, 5, 6, 7;
> 7, 8, 9, 10;
> 8, 4, 9, 1];
> x_true = [9; 1; 6; 2];
> b = A*x_true;
>
>
> % Setup the under-determined system
> N = 2;
> A_und = A(1:N,:); b_und = b(1:N);
> x_minLS = pinv(A_und)*b_und;
> J_und = A_und;
>
>
> x_guess = rand(size(x_minLS));
>
>
> IterMaxNo = 500; IterDelta = 1.0E-7;
>
>
> % compatible case
> [x_und_gnpinv, n_iter] = ...
> gnpinvL(x_guess, J_und, A_und, b_und, IterMaxNo,
> xNo, IterDelta);
>
>
> function [y, n] = gnpinvL(x_old, J, A, b, IterMaxNo,
> IterDelta)
>
>
> n = 0;
>
>
> while ( n <= IterMaxNo )
> f = A*x_old-b;
> tmp = pinv(J)*f;
> x_new = x_old-tmp;
> n = n+1;
>
>
> DiffNorm = norm(f);
>
>
> if DiffNorm < IterDelta
> y = x_new;
> fprintf(' Converged! \n');
> return
> end % if converged
>
>
> x_old = x_new;
> end % while
>
>
> y = x_new;
> fprintf(' Iteration Exceeded! \n');
>
>

Why do you want to determine a least-squares solution
for an _underdetermined_ system ?
This approach is usually used for _overdetermined_
systems.
The affine solution of an underdetermined system is
given by
x_0 + kern(A)
where x_0 is a special solution of the system
A*x = b.

Best wishes
Torsten.
 | 
Pages: 1
Prev: i have question about simulink (error calculation block)
Next: how to get a m-by-n matrix from grayscale image?