[OT] "Real world" linear algebra

(er... dsprelated.com appears to have blanked the subject line on me on
that last post.  Sorry about that.)

Rune Allnor wrote:
> On 29 Aug, 16:53, Gordon Sande <g.sa...@worldnet.att.net> wrote:
> 
>>On 2009-08-29 09:09:26 -0300, Rune Allnor <all...@tele.ntnu.no> said:
> 
> 
>>You have gotten confused by not paying close atention to
>>the subtle distinction. The "least" is applied to the residuals
>>and the "minimum" to the solution.
> 
> 
> I can't remember ever to have encountered a underdetermined
> system in a useful application.  Once the system is
> underdetermined, you are basically down to guesswork.
> Constrained guesswork, but guesswork nonetheless.

In the practical control systems, they often need more outputs then you 
have inputs.

VLV

On 29 Aug, 18:38, "Michael Plante" <michael.pla...@gmail.com> wrote:

> Also, for conditioning reasons, in the use of SVD, you are supposed to
> doctor singular values that are very close to zero, with "close" being some
> fraction (specific to the application) of the largest singular value. &#4294967295;I do
> not know what MATLAB chooses for the threshold in its internal routines.
> In light of the act of forcing a nearly-singular matrix to be *actually*
> singular, it should become clear where the "underdetermined" aspect can
> come from.

I'm not sure that's correct. If you have an MxN matrix of
basis vectors, the underdetermined system occurs when N > M
and you get at most M nonzero signular values, but need N
model coefficients. You are in a mess no matter what. Any
additional vanishing singular values only mean that you
are in an even larger mess.

> But it is totally conceivable that the folks (you?) designing your
> experiments had enough intuition to choose experiments that uniquely
> determine your coefficients, in which case you've been able to avoid this.

Well... in my experience the problem is that people
'design' experiments that are expected to produce
qualitative, not quantitative, answers.

Apart from that, the SVD is nifty for 'cleaning' noise
in overdetermined LMS problems. If the data x = s + n
has autocovariance matrix Rxx on the form

Rxx = Rss + sigma^2*I,

where Rss is the signal of interest and rank(Rss) < N,
you can use the SVD to remove the basis for the noise-only
subspace. It can cause significant improvments in the
data analysis.

Rune

>On 29 Aug, 18:38, "Michael Plante" <michael.pla...@gmail.com> wrote:
>
>> Also, for conditioning reasons, in the use of SVD, you are supposed to
>> doctor singular values that are very close to zero, with "close" being
so=
>me
>> fraction (specific to the application) of the largest singular value.
=A0=
>I do
>> not know what MATLAB chooses for the threshold in its internal
routines.
>> In light of the act of forcing a nearly-singular matrix to be
*actually*
>> singular, it should become clear where the "underdetermined" aspect
can
>> come from.
>
>I'm not sure that's correct. If you have an MxN matrix of
>basis vectors, the underdetermined system occurs when N > M
>and you get at most M nonzero signular values, but need N
>model coefficients. You are in a mess no matter what. Any
>additional vanishing singular values only mean that you
>are in an even larger mess.

Fair enough.  You will also have an underdetermined case there, without
any help from modification of singular values, as you pointed out.  I was
not limiting myself to that case, though.  I also agree that you're in a
mess regardless.  But it seems that there is still some information to help
diagnose the problem, and that, on average, in finite precision, you can
get some improvement in residuals by zeroing those components, even if the
solution is less meaningful that what we'd like.

For clarity, take the "determined" case of NxN, assume it's not
technically singular, but has a very large condition number, and assume
that only one of the singular values is really small (i.e., the others have
a slight spread).  In exact precision, it would hurt accuracy a little to
zero that one value.  But with a computer, it can be argued that the small
singular value is on the order of expected roundoff, or even smaller than
that.  The SVD algorithm is really telling you no other real information
about that singular value other than that it's very small.  It is
associated with a vector in an "almost" nullspace.  Of course, there isn't
really a nullspace exactly, since it was assumed to be nonsingular, but
there's a very similar coefficient matrix nearby that has that vector as
the basis for its nullspace.

The trouble is that when you find the solution, the portion of the
solution vector associated with those small components mostly consists of
stuff that cancels when you multiply back against the original matrix. 
Cancellation is frequently bad news, and can give a fairly large
residuals...at the mercy of roundoff.  But all is not lost.  Since that
portion of the solution vector associated with this "almost-nullspace
direction" has very little impact on the exact problem (recall it would
mostly cancel, at higher precision), the most robust way to tackle it
numerically is to zero that singular value, essentially planning ahead to
avoid catastrophic cancellation at the expense of what would, in exact
precision, be a slight loss in accuracy.  You pick the threshold small
enough that your residuals are improved more often than not.  This, of
course, means that occasionally they will be slightly worse off, due to
good luck you would have otherwise had with rounding, but not by much.  

Michael Plante wrote:
>> On 29 Aug, 16:53, Gordon Sande <g.sa...@worldnet.att.net> wrote:
>>> On 2009-08-29 09:09:26 -0300, Rune Allnor <all...@tele.ntnu.no> said:
>>> You have gotten confused by not paying close atention to
>>> the subtle distinction. The "least" is applied to the residuals
>>> and the "minimum" to the solution.
>> Once the system is
>> underdetermined, you are basically down to guesswork.
>> Constrained guesswork, but guesswork nonetheless.
> 
> True, although the covariance output of a good routine will tell you which
> parameters are in error so you can improve the model and/or take better
> data.  I get the impression that the OP is trying to do something with the
> residuals besides just minimizing them and forgetting.  Richard:  am I
> mistaken?
> 

As phrased, I don't know. To many technical terms are floating 
around this thread that I'm not familiar with.
I *DID* say my motivation was self education ;/

I'll only be considering cases with at least 4 satellites in view.

Therefore, >=4 equations with 4 unknowns.
The parameters of the equations have noise, offsets, and 
precision errors.

I've downloaded lecture notes and lab assignments from a course 
covering geodetic measurements. It assumes more math than I have. 
So I'm trying to find out just how much I don't know.

Thanks.

>> I get the impression that the OP is trying to do something with the
>> residuals besides just minimizing them and forgetting.  Richard:  am I
>> mistaken?
>> 
>
>As phrased, I don't know. To many technical terms are floating 
>around this thread that I'm not familiar with.
>I *DID* say my motivation was self education ;/
>
>I'll only be considering cases with at least 4 satellites in view.
>
>Therefore, >=4 equations with 4 unknowns.
>The parameters of the equations have noise, offsets, and 
>precision errors.

I can see how the terminology might not be helpful.  I was looking at 

>Current project is investigation of GPS "errors".  Quotes cause 
>one man's error is another's *DATA*

when I wrote that.  When you solve for your unknowns, if you plug them
back in and see if you can get your measurement back, the amount by which
you are off is your residual.  Ideally it's 0, but an overdetermined system
will typically eliminate some information from the measurements to give a
"best fit", so it won't match all the measurements precisely, and you call
that amount it's off by a nonzero residual.  Least squares minimizes that
residual, which is what you want, I think.  

A lot of times, people just take their solution for the unknowns and run
with it, assuming that the residuals are just "noise" (as they are with a
good model).  I know a *little* about GPS, and it has some interesting
effects that can perhaps be modeled, since some of them vary slowly over
time, so I was wondering if you were going to take those residuals and do
something additional with them, or if your modeling would strictly be in
terms of adding unknowns to be solved for.


>I've downloaded lecture notes and lab assignments from a course 
>covering geodetic measurements. It assumes more math than I have. 

Out of curiosity, what sort of math?

On 30 Aug, 03:20, "Michael Plante" <michael.pla...@gmail.com> wrote:


> A lot of times, people just take their solution for the unknowns and run
> with it, assuming that the residuals are just "noise" (as they are with a
> good model).

This is the Damocles sword of model-based data processing:
With a good model you can get a very good represnetation
of the data. Without a *good* model you can be worse off
than ever.

> >I've downloaded lecture notes and lab assignments from a course
> >covering geodetic measurements. It assumes more math than I have.
>
> Out of curiosity, what sort of math?

Presumably trigonometry. The problem is that cartographers
try and represent the Earth, which deviates slightly
from a perfect sphere, in terms of trig functions that
work on the sphere. The computations on the sphere are
awkward at the best of times; with the expansions and
modifications for the ellipsoid case (and not to metion
the imperfect elliposid cases) the algebra becomes
nightmare'ish.

Rune

On Aug 29, 7:44&#4294967295;am, Richard Owlett <rowl...@pcnetinc.com> wrote:
> Karl Molnar wrote:
> > What is on the right side of the eqn. Ax + b ~= 0?
>
> I wasn't trying to be formally correct, just trying to contrast
> "real" with "ideal" (ie Ax+b = 0)
>
>
>
> > Some references:
>
> > 0) search for Moore-Penrose pseudoinverse (it's even in Wikipedia);
>
> First Google hit I got after reading Rune's response.
>
>
>
> > 1) search for least squares problem, minimum norm solution;
>
> I should have thought of searching for "least squares". I don't
> recognize "minimum norm solution" at all - will have to look it up.
>
>
>
> > 2) Pick up a copy of Matrix Computations by G. Golub and C. Van Loan;
>
> Not available &#4294967295;from local library system. In fact using "matrix"
> in a keyword search yielded only one math related hit -
> Cliftnotes for Algebra II ;/
>
>
>
> > 3) If you have MATLAB, type 'doc mldivide' for a good treatment of how
> > they solve these problems.
>
> I only have Scilab, will go searching its help files.
>
> Thanks to all who responded.
>
>
>
>
>
> > Richard Owlett wrote:
> >> I haven't had a linear algebra course in over 40 years.
> >> AND, all our problem sets had exact solutions.
>
> >> That is Ax+b = 0 (A a matrix, x&b vectors)
> >> But I have Ax+b ~= 0 (fortunately &#4294967295;# of equations > # unknowns)
>
> >> I have not *YET* Googled. Don't know appropriate keywords. Suggestions
> >> please. TIA
>
> >> [As there are some that claim I don't give enough info.
> >> &#4294967295; Current project is investigation of GPS "errors".
> >> &#4294967295; Quotes cause one man's error is another's *DATA*
> >> &#4294967295; As I'm cheap with limited observation time
> >> &#4294967295; &#4294967295; I'll use RINEX formatted CORS data ;]
>
> >> Besides which I'm trying to educate myself.- Hide quoted text -
>
> - Show quoted text -

Hello Richard,

Here is a .pdf of a MathCad sheet I wrote awile back that solves your
GPS equations. It uses Least Squares inside of an iterative process.

http://www.claysturner.com/dsp/gps%20eqn%20solve.pdf

IHTH,

Clay