Prev: HP's award Winning Support Team Explains the ONe Year Warranty
Next: hpgcc and rpl-stack
From: John H Meyers on 4 May 2008 10:54
On Sat, 03 May 2008 20:06:01 -0500, Rodger Rosenbaum...
(who meanwhile wrote another, while I was still writing this :)

Hi -- isn't this banter fun?

I think it may actually soon converge
to some agreement or conclusion
(or fatigue on the part of the participants :)
and meanwhile may have left some useful bits in the archives,
or else just in the mind of one participant (me :)

>>> The only "possible" solutions are the ones whose residual norms
>>> are equal to the minimum possible.

>> There ya go -- a definition which I don't recall noticing earlier;

> This is what is meant in the AUR description of LSQ, second paragraph,
> when they say that with underdetermined systems
> "...an infinite number of solutions exist."

I had been confining my consideration to addressing what is written
in this thread, rather than bringing in things written elsewhere
by inference. For example, someone crediting the AUR
as the source for one adopted statement does not mean "endorsing"
other AUR statements, any more than Barack Obama
endorses what his old friend and minister says,
just because he attended his church, etc.

"Most" under-determined systems
actually have an infinite number of "exact" solutions,
so I have tended to assume that meaning for any such statement,
if no other meaning is made explicit.

At any rate, I have the AUR section on LSQ right in front of me,
and it's rather hard to claim that it ever really defines the word
"solution," even within its own "scope," but just uses it many times,
forgetting to define it in the first place,
in a manner not likely to be self-evident to anyone,
and thus likely to be taken as whatever is most familiar
to the individual reader, from past experience.

After considerable effort, it might be divined that the only meaning
which could make all the other statements defensible would be
"any X for which the residual attains its minimum possible norm,"
which makes the phrases "solution[s] that minimize[s] the residual
Euclidean norm" (occurring three times in this little AUR section)
a bit redundant (or perhaps those phrases were intended
as the definition, stuck under every rock in the middle of the garden,
but never declared to actually be a definition).

I can see where one might try to assign the meaning "any X at all"
to the word "solution," but then "if A has less than full row rank,
an infinite number of solutions exist" would seem rather silly and
meaningless, because an infinite number of "any X" _always_ exists,
so I think, to make any sense of the whole, we are compelled
to assign the very definition stated above,
which is what should be made explicit to begin with,
to avoid the "standard English meaning" of the word
being taken for granted,
leading to the mess we can otherwise get into.

Now back to Roger (repeating a few older lines here),
who evidently was trying to straighten out that same mess:

> First, some terminology.
> The AUR uses the word "solution" in places where
> it should add an adjective in front to be precise.
> I'll use the terms "exact solution", "approximate solution",
> "minimum norm solution" and "minimum residual solution".

> By "approximate solution",
> I mean a solution x that gives a non-zero residual.

> By "minimum residual solution", I mean a solution
> which gives a minimum residual norm.

Just like the AUR, however, you never defined "solution" at all
(or assumed that the AUR had defined it, which I think it never did),
apparently _replacing_ that undefined word
with a set of distinct, longer phrases, so that,
unless "solution" _already_ means something precise,
then it is a mathematically meaningless word in all of the above,
simply becoming part of the other phrases which are being defined,
rather than having a known meaning to begin with,
to which further qualifiers "approximate" etc. can then be applied.

In that light, what you have said
would seem to have to mean that an "approximate solution"
means "any X that gives a non-zero residual,"
which (particularly when the equations are inconsistent,
so that there is always a non-zero residual)
necessarily means "any X whatsoever,"
and that's why I considered it not worth attaching
a "special word" (approximate) which meant next to nothing,
save for "NOT a solution to the equation set,"
while incorporating at the same time the word "solution,"
which conjures up in most people's mind something that IS,
and thus the whole phrase is not what I'd offer
in the cause of explaining this topic to anyone new to it,
and just trying to make sense out of it.

On the other hand, if "solution" already does mean
precisely what I say we are forced to have it mean in the AUR,
given all its usage of the word,
then it already means "minimum residual solution,"
for which your "definition" above is then also redundant;
thus it wouldn't be expected that you did mean the same thing
as it finally seems necessary to conclude that the AUR did.

I offered "define 'approximate solution' as this,
and call it a draw" (isn't that just like what
Josh Waitzkin said, in "Searching for Bobby Fischer"?)

I think you should have agreed, rather than coming back with
the move "let's say within 10% of the correct value for starters,"
which is completely opposed to what you started to mean,
and seems guaranteed to derail discussion
(left side within 10% of right side? other way around?
what if both sides have opposite signs?), and at any rate,
sends the mind off in a direction unrelated to LSQ
(which does not seem assured to return an answer
within any pre-defined "approximateness" in this sense).


I believe I have finally comprehended
most of what the AUR was trying to say,
which you were trying to re-explain,
but since the never-defined word "solution"
was sitting in the middle of every sentence,
both in the AUR and in your exposition,
upon which other words were building themselves
an inverted pyramid of definitions,
the entire thing collapses into a total heap of confusion,
unless one gets the initial thing right,
and sticks to that same meaning, all the way through,
properly doing which even eliminates the need
for some of the extra verbiage which had been introduced.

What follows may not be exactly right,
but I think it's on the right track,
as to how it could be more clearly explained,
for everyone's benefit:

Some subset of all possible X produces a residual
whose [Euclidean] norm attains a minimum possible value.

In cases labeled "under-determined,"
there are infinitely many X in that set,
among which the one having minimum norm itself is LSQ's answer.

In cases labeled "over-determined,"
there is only one X in that set,
which obviously is LSQ's answer.

When the equations are consistent, the minimum norm is zero,
and LSQ's resulting X must satisfy all the equations.

When the equations are inconsistent, the minimum norm
is not zero, and there is no X satisfying all the equations
(the result of LSQ might even satify none of them,
much as a "least squares line" might actually pass through
none of the points which it is designed to "best represent")

"Under-determined" does not imply consistency of the equations,
and "over-determined" does not imply inconsistency
[the precise meanings in relation to "rank" should be defined]

Thus far, within the limited scope just above,
the word "solution" does not even need to be mentioned
("consistency of the equations" stands in for
"existence of solutions of the equations").

The very use of the word "solution," in fact,
invites confusion with the meaning expected from common usage,
such as "solving a set of equations," whereas LSQ "solves"
a more general goal, which can always be accomplished,
even when no X "solves" all the equations.

However, in the greater context of that general goal
which LSQ addresses, a "solution" can then mean
any X for which the [Euclidean] norm of the residual 'B-A*X'
attains its minimum possible value,
as I think we were compelled to conclude was already meant
"between the lines" in the AUR.

When the equation set has a solution (or many),
an "LSQ solution" is also a solution to the equation set;
otherwise, the phrase "minimum norm least squares solution..."
(the first phrase in the AUR)
isn't a "solution" to the equations themselves,
which the ongoing wording "... to any system of linear EQUATIONS
where A*X=B" (with emphasis on "=" !!!) completely muddles,
and should be replaced by something unmistakably declaring
that LSQ addresses a general minimization problem,
which only sometimes also solves the equations.

It struck me as counter-productive,
obscuring what could be made crystal clear in fewer words,
to throw more phrases needing further definition into the melee,
trying to make up for the AUR's original muddle,
like "approximate solution" (to what? to the original equations?
certainly not to the LSQ problem itself).

You could say (and did say) that an "approximate solution"
is any "solution" in LSQ sense
which isn't a "solution" to the equations themselves,
but the phrase "approximate solution" is not needed
to further define or explain anything else pertinent here,
and in my opinion only reinforces the original AUR muddle.

It reminded me of someone I know,
who addresses a honey jar that has become all sticky,
by putting it inside a plastic bag,
and then, when that bag itself becomes all sticky,
puts all of that inside yet another new plastic bag, etc.,
instead of just washing off the original jar to begin with :)

Extra qualifiers like "minimum residual solution"
are also not needed, because "solution" (in the generalized sense)
_already_ means that, unless "solution" means "any X whatsoever,"
to which I think you've already objected :)

Anyway, while we're working on a "minimization problem,"
why don't we also minimize the number of phrases we need
to express it, not wrapping slightly cloudy plastic bag wrappers
around it, but just cleaning up the original description,
to make it like a crystal clear original jar?

Finally (ending the scope of this part), although we (you) have
gone into several variations and details about the possible
characteristics of the set of "all [generalized] solutions,"
for various categories of inputs, the action of LSQ
can still be completely and rigorously defined in a single sentence
(which I think you admitted as "elegant" and "beautiful" :)
common to all of them, which can't be all that bad a thing
to also point out, can it?


Another way to describe LSQ follows (you've addressed it all,
but here I'm only trying to squeeze the same material
into a more condensed form, which simply by this
may be easier for people to comprehend all together,
like stepping back, taking a wider view,
and also "minimizing" the output of words, as far as possible :)

LSQ generalizes the idea of solving an equation set,
by seeking to minimize the Euclidean norm of 'A*X-B',
which is always possible,
rather than the goal to satisfy 'A*X=B',
which is not always possible.

A "solution" to the expression 'A*X-B',
in the sense of this wider goal,
is any X which minimizes the Euclidean norm of 'A*X-B'

If (and only if) that minimum is zero,
then X is also a solution to the equation set 'A*X=B'

In those cases where there are multiple solutions
to minimizing the Euclidean norm 'A*X-B'
(known as "under-determined" systems),
LSQ returns that solution (X)
having the smallest Euclidean norm itself,
which has other properties not here elaborated
(but turn to RR's examples to explore that).

[insert further precise definition/explanation
of under/over-determined, etc., if desired,
and contrast with "consistent"]

Does this harmonize the clashes
between one person's "solution" and another's?
Can it help other people's understanding?

All of your elaborations of the properties of these systems
certainly educate by example and deeper exploration,
while the level I sought to contribute was to isolate
what could be said in the most complete generality about LSQ,
applying to all cases.

No doubt there must be authors who have already done all of this
much better, even though their own output doesn't seem to have
penetrated into the AUR (or perhaps even here :)

Wolfram always seems to have something, don't they?
Not all on exactly the same issues, but related,
even further expanding the varied uses for the LSQ function:

http://mathworld.wolfram.com/LeastSquaresFitting.html
http://mathworld.wolfram.com/LeastSquaresFittingPolynomial.html
http://demonstrations.wolfram.com/LeastSquares/
http://documents.wolfram.com/v5/Built-inFunctions/AdvancedDocumentation/LinearAlgebra/4.3.html
(Golub and van Loan finally make their appearance :)

Searching far and wide, out into life:
http://en.wikipedia.org/wiki/Searching_for_Bobby_Fischer
http://www.imdb.com/title/tt0108065/


> Were you expecting that I would offer a proof?
> [that there is only one right answer for LSQ]

Heavens, no; if you had mentioned Fermat's Last Theorem
some years ago (before an accepted proof was published,
if Joe accepts it :) I might have mentioned
that it hadn't yet been proved,
but I would not have meant that statement
as saying that it wasn't so, nor as demanding a proof from you :)

Something very simple, yet never proved at all
(but the unscaled peak keeps attracting climbers):
http://www.petrospec-technologies.com/Herkommer/goldbach.htm
http://plus.maths.org/issue2/xfile/index.html [with calculator]
http://primes.utm.edu/glossary/page.php?sort=goldbachconjecture
http://mathworld.wolfram.com/GoldbachConjecture.html
http://en.wikipedia.org/wiki/Goldbach%27s_conjecture

> I got 95% of the way to a proof...

Wow, someday I might be able to claim having had a small part
in producing a masterpiece, just by inadvertently falling into
another creature's shell, just like a grain of sand into an oyster,
after which the oyster produces a big pearl, all on its own :)

Let me know when it comes to the point where we can shake hands again,
even if only after the bout is over :)

[r->] [OFF]
 | 
Pages: 1
Prev: HP's award Winning Support Team Explains the ONe Year Warranty
Next: hpgcc and rpl-stack