Path: news.mathworks.com!newsfeed-00.mathworks.com!solaris.cc.vt.edu!news.vt.edu!news.glorb.com!tr22g12.aset.psu.edu!news.mathforum.org!not-for-mail
From: Torsten Hennig <Torsten.Hennig@umsicht.fhg.de>
Newsgroups: comp.soft-sys.matlab
Subject: Re: ? why cannot get LS soln with mini norm
Date: Mon, 14 Jun 2010 04:50:22 EDT
Organization: The Math Forum
Lines: 102
Message-ID: <1349957944.329958.1276505452929.JavaMail.root@gallium.mathforum.org>
References: <317f961d-ce0a-43c4-bd56-b7c9c6fcc9b5@w12g2000yqj.googlegroups.com>
NNTP-Posting-Host: gallium.mathforum.org
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
X-Trace: support1.mathforum.org 1276505452 11472 144.118.94.39 (14 Jun 2010 08:50:52 GMT)
X-Complaints-To: news@news.mathforum.org
NNTP-Posting-Date: Mon, 14 Jun 2010 08:50:52 +0000 (UTC)
Xref: news.mathworks.com comp.soft-sys.matlab:644671

> 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.