A NOVEL INTERPRETATION OF LEAST SQUARES SOLUTION

VOL. 15 NO. (1992) 41-46

A NOVEL INTERPRETATION OF LEAST ^SQUARES SOLUTION

JACK-KANG CHAN

Norden

Systems 75 Maxess

Road Melville,

New

York

11747

(Received March 5, 1991 and in revised form August 21, 1991)

Abstract.

We

show that the well-known least

squares (LS)

solution ofan overdeterminedsystemof linear equationsisa convex combination of all the non-trivial solutionsweighed bythe

squares

ofthe corre- spondingdenominator determinants of the

Cramer’s

rule. This

Least Squares

Decomposition

(LSD) gives

an alternate statistical interpretation of least

squares,

as well as another geometric meaning.

Furthermore,

when thesingular^valuesofthe matrix of the overdeterminedsystemare notsmall,the

LSD may

be abletoprovideflexible solutions.

As

anillustration,we

apply

the

LSD

tointerpretthe LS-solution in theproblemof source localization.

Key

Words and Phrases: leastsquares decomposition, least

squares

solution,overdeterminedsystem, source localization.

1980

MathematicsSubjectClassification:

15A09, 15A15, 65F20,

56F40 1.

INTRODUCHON.

Given an overdeterminedsystemof linearequations

Ax

-b

(1)

where

A [aij]

is anmxn matrix with m n andrank

(A)

n, andb

[bj]

^{is anm-column}vector,and x

[x]

^istheunknown n-column vector.

For

simplicity,we consider

only

real numbers. Thereareat most

det[A ix...i.;

b:

j]

j 1, ...,n

x[ix...i,] (2)

det[A" ix...in]

^{1< < < m}

where

det[A: ix...in],

^assumed

non-zero,

is thenxnminorformed from

A by

takingtherows

ix,..., i,,

and

det[A:ix...in;

^b:

j]

^isthepreviousdeterminant with itsjthcolumn

replaced by

thecorresponding

bi,

fromthe vectorb.

Theleast

squares (LS)

solution is

[3]:

Xts (a ’A )-Xa

^’b

(3)

where

(A’A)-XA’

^isthegeneralizedinverseof

A. Using

ournotations, the LS-solutioncan be rewritten as

solutionsby takingthe sum over thoselarge singularvaluesonly.

LEAST SQUARES DECOMPOSITION.

THEOREM.

det[A ’A A

’b:

j] det[A i...i.]’ det[A i...i.;

^b:

j]

det[A’A , ^{t[A i...i.]l}

⁰

For

j- 1 ,n,

(4) (5)

det[A: ix...i.]l

^2"xi[h..]

E ⁽⁶⁾

Xj[LS]

.’,

""" ^{E det[A" kx...k.]l}

PROOF. We

haveassumed that

A’A

isnon-singular

(since ^rank(A)- n). Note

that

Eq. (5)

^isa specialcaseof

Eq. (4),

and

Eq. (6)

^isthe

consequences

of

Eqs. (2), (3), (4)

^and

(5).

^{Thecase whenm n}

isobvious,because in thiscase,there is

only

one term in the summations. Thecase when n 2 canbe verifiedeasilybydirect evaluation. The

proof

for the

general

case isnotationally

lengthy. In

orderto illustratethe

spirit,

^wewill

prove Eq. (4)

^{for m 4and n 3in the}

following. Note

that if

A

is

complex,

wesimply

replace

all thetransposes

by

theconjugate transposes.

SupposeA [ai]4s

^{and b}

[bi]4,,r

^Then

and

lla

lailai2 auas"

aea, a aea

^u

Ab

LetDz; .det[A: 123]’ .det[A:

123;b:

1].

Therefore, a21 a31

la

^a23

1,2,3

. ab ^ab

1,2,3

1,3

^aila

1.3 a

1,3

^aai2

bl

^a12 a13

b2

a22

b

a32 a3

1.2,3ala

1,2,3aa

det[A

’A;A’b:

1]-

a42

1

^{aila2 a41a4.3}

ab, a.2a

^a4.2a4.

l ^a,b, l

^{atjai2 a43}

abi ,

aaiz a43

l ^ailb

^a41

,

ailat

1,2,3

1 ^ai2bi

^{a42 1,2,3}

²

^ai2a3

t ^ai3bi

^a4.3

^{1,3 aa2}

1,2,3 1,2,3

l.zs’aaaz 1.3 ^a2

For

the thirddeterminant,multiply Column 2 bya4. and add it toColumn 3.

For

the fourth determinant, multiply Column 1

by

a4.2 and add it toColumn2,thenmultiply Column 1

by

a4.3 and add it toColumn 3.

We

thenhave,

D12 det[A ’A ;A

^’b"

I]-

ab

a3a2

, a,b, asa a

Similarly,

weobtain

DI24,DI:;4

^and

Dz. ^{Adding up}

^alltheseexpressions,we note that the sumofthe second determinantsinthe aboveexpression

gives-det[A ’A;A ’b: 1],

andsimilarlyfor the third andthe fourthdeterminants.

Therefore,

D12 +D12 +DI3 +Dz-4.det[A’A;A’b" 1]-det[A’A;A’b: 1]

det[A ’A A

’b

1] det[A ’A A

’b

1]

de

[A ’A A

b

1]

whichistherequired

LSD (Eq. (4)).

Ifallthe singularvalues of

A

arenotsmall,we cannotreducethe summation in the

SVD. However,

the

Least Square

Decomposition

(LSD) (Eq. (6))

^{suggeststhat we}

may

stillgeta better answer

by

summing those NT-solutions whose

Cramer

denominator determinants are

large

inmagnitude.

We

willverifythe

LSD

formulasand theabove idea via an

example

in thenextSection.

In

fact,the

LSD

has the same form as awell-known result in statistics: If

1 ,,

are unbiased estimators oft9with variances

respectively,then the linear unbiased minimum variance estimatorof 19iswell known to be

[2]:

-

^j-1

^{2 (7)}

Eq. (7)

^isalso the result ofminimizing

where

E E (e,- e)/ ()

bythemethodofleast

squares [2]. Thus,

if weinterpretthe

squares

ofthe

Cramer

denominator determinants asthe

o ^"-’s,

the N-T-solutions are the estimatesofthe

"true"

solutions,then

Eq. (6)

^and

^Eq. (7)

are identical.

Therefore,the

LSD

has a secondmeaningof"least

squares" (Eq. (8))!

Eq. (6)

givesasimple geometric interpretation, namely,the LS-solution is the

"center

of

mass"

among the NT-solutions. TheLS-solution istherefore lyingnear those NT-solutions whose denominator deter- minants arelargeinmagnitude

(or,

small

variances).

3. AN EXAMPLE.

Consider

As

shown in Table 1,there are 4 NT-solutions

(see

^{Columns 1to4}inTable

l(a)).

The LS-solution is computedfrom

(A ’A )x (A ’b),

asshown inColumn 5.

We

have,from Table

l(a),

(44)2(208/44)

+

(1)2(57/1)

+

(-5)2(-55/- 5)

+

(23)2(161/23)

¹³¹⁸⁷

(44) (114/44)

+

(1)2 (-34/1)

+

(-5) (-60/- 5)

+

(23) (138/23)

8456

(44) (-96/44)

+

(1)2 (-44/1)

+

(-5) (-10/- 5)

+

(23) (-92/23)

^-6334

and

(44)2+(1) +(-5)2+(23)

^2491.

Hence

all the

LSD

formulas have been verified. Furthermore,the ratioof themagnitude squared

(or,

just the

magnitude)

of the determinants indecendingorderprovidesinformationabout thesignificantnumber oftermsin the

LSD

sum.

In

ourcase,wehave

(44) (23) (-5) (1)

^{1 0.27324} 0.01291 0.00052

Thus,wemaydefinea"conditionnumber"asthe ratio of thelargestdeterminantsquaredtothesmallest.

The singular values can be computed

[1]:

s_t-7.501111, s_2-

2.926371, s3-2.273693. ^Note

^that

sls2s3 2491.

None

of thesesingularvalues aresmall,because the rankof the matrix is3.

In

thiscase, the

SVD

givesnofurtherimprovement,butthe

LSD

is still flexibleas illustrated in Table

l(b),

where the

LSD

issumming upthe N-T-solutions withlargedenominator determinants indecendingorder ofmagnitude.

Thus,we

may

firstfindthe

SVD

of thesystemtosee howmany singularvalues are smalltodo the

necessary

rankreduction,then we

apply

the

LSD

for an ultimateimprovement.

(a)

NT-SolutionsandLS-Solutions

X

Cramer’s

rule: NT-Solutions

Rows

1,2,3 det=44 208/44 4.72727 114/44 2.59091 -96/44 -2.18182

Rows

1,2,4 det=l 57/1

=57 -34/1 -34

Rows

1,3,4 det=-5

-55/-5

=11 -60/-5

12 -44/1

-44

-10/-5

=2

Rows

2,3,4 det=23 161/23

=7 138/23

=6

LS (SVD)-Solution

det=2491 13187/2491

5.29386 8456/2491 3.39462 -6334/2491

-2.54275

(b) I.SD

Solutions

LSD

Solutions 1det

44 208/44

4.72727 114/44 2.59091 -96/44 -2.18182

2dets

44,

23 12855/2465

5.21501 8190/2465 3.32251

3dets"

44,23, -5 13130/2490

5.27309 8490/2490 3.40964 -6340/2465

-2.57201

-6290/2490 -2.52610

4dets- 44,23,

-5,

1

13187/2491 5.29386 8456/2491 3.39462 -6334/2491

-2.54275 Table1. Exampleof

Least Squares

Decompositions.

sensorsdetermine ahyperbola.

Suppose

there aren sensors

(n 3),

thenthe intersection fo all the

hyperbolas

^willgivethe source location. This is the well known

technique

^ofhyperbolic fixing.

How-

ever, due tonoisytime

delay

measurements, these

hyperbolas

do notintersectataunique point.

Usu- ally,

the source isfar

away

fromthesensors and the

hyperbolas may

be

approximated by

their

asymptotes.

The

problem

isnowreduced to asystem ofpairs of 2x2linearequations.

A least-squares

solutiongivesthe source location. With the

LSD

theorem,weinterprettheLS-solutionas theweighted sum of allpossiblesource locationsaccordingtotheir denominator determinants. Eachdenominator is proportionaltothetangentof theanglebetween thetwohyperbolas.

Thus,

ifthehyperbolasintersect at almost arightangle,the source location is more accurate than those intersections at small

angles.

This

angle

interpretationissimpleandintuitive,and it isjustified

by

the

LSD

theorem. Furthermore,wecan

just

^selectthosesolutions withlargedenominators

only. Note

that the

SVD

methodhas noimprove-

ment because the rank isalways 2. Theoptimallocation is the

"center

of

mass"

ofthepossibleloca- tions.

Moreover,

insteadof using

hyperbolas,

Schmidt

[4]

has shownthatthe source location is thefocus ofaconicpassing throughthe3 sensors,hence the source is on thefocalline. With more than3 sensors, wehavemore than one focal lines. The intersections of these focal linesgive^{the source}

location(s).

Thus, weactually solving^linearequations,notjustanapproximation using asymptotesasin thehyperbolic fixing technique.

We

can usethe

LSD

tointerprettheanglesbetween the focal lines as ameasureof the

accuracy

of the solutions. Formulations of the localization in 3-dimensions usingSchmidt’s method and other equivalentmethods togetLS-solutionshave been done

[5], [6]. We

caninterpretall theseLS-solutions usingthe

LSD

similar tothe 2-dimensional case.

ACKNOWLEDGEMENT

The author wouldlike tothankProfessor

George

Bachman ofPolytechnic Universityfor hisproof reading of the manuscriptand valuablesuggestions,and to the Refereeforhis/hervaluable comments.

[ll [21 [3]

[4]

[51 [61

REFERENCES

J.J. Dongarra, C.B.

Moler,

J.R.

Bunch, and

G.W. Stewart, LINPACK User’s

Guide,

Chap.

11,

SIAM,

Philadelphia,

PA,

1979.

A.

Hald,Statistical

Theory

withEngineering

Applications, pp.

243-245, Wiley,

New

York,

NY,

1952.

C.L. Lawson

and

R.J. Hanson, Solving Least Squares Problems,

Prentic-Hall,

Englewood

Cliffs,

NJ,

1974.

R.O.

Schmidt,

A

new

approach

togeometry

of ^range difference

^location,

^{IEEE Trans. Aerosp.}

Electron.,

Vol.

AF.-8, Nov. 1972,

821-835.

H.C. Schau, A.Z.

Robinson,Passivesource localizationemploying intersecting spherical

surfaces from time-of-arrival differences, IEEE Trans. Acouts., Speech,

Signal

Process.,

Voi.

ASSP-35, Aug.

1987,

pp.

1223-1225.

J.O.

Smith,

J.S.

Abel,

Closed-form least-squares

source location estimation

from

range-difference measurements,

IEEE Trans. Acoust., Speech, Signal Process.,

Vol.

ASSP-35, Dec. 1987, pp.

1661-1669.