10
VOLTAGE LEAST-SQUARES
ALGORITHMS REVISITED
10.1 COMPUTATION PROBLEMS
The least-squares estimates and minimum-variance estimates described in
Section 4.1 and 4.5 and Chapter 9 all require the inversion of one or more
matrices. Computing the inverse of a matrix can lead to computational
problems due to standard computer round-offs [5, pp. 314–320]. To illustrate
this assume that
s ¼ 1 þ " ð10:1-1Þ
Assume a six-decimal digit capability in the computer. Thus, if s ¼ 1:000008,
then the computer would round this off to 1.00000. If, on the other hand,
s ¼ 1:000015, then the computer would round this off to 1.00001. Hence,
although the change in " is large, a reduction of 33.3% for the second case (i.e.,
0.000005=0.000015), the change in s is small, 5 parts in 10
6
(i.e., 0.000005=
1.000015). This small error in s would seem to produce negligible effects on the
computations. However, in carrying out a matrix inversion, it can lead to serious
errors as indicated in the example to be given now. Assume the nearly singular
matrix [5]
A ¼
s 1
11

ð10:1-2Þ
where s ¼ 1 þ ". Inverting A algebraically gives
A
À1
¼
1

À11:00001

0:00001
% 10
4
10 À10
À10 10

ð10:1-5Þ
Thus the 5 parts in 10
6
error in s results in a 50% error in each of the elements
of A
À1
.
Increasing the computation precision can help. This, however, can be costly
in computer hardware and /or computer time. There are, however, alternative
ways to cope with this problem. When doing a LSE problem this involves the
use of the voltage least-squares, also called square-root algorithms, which are
not as sensitive to computer round-off errors. This method was introduced in
Section 4.3 and will be described in greater detail in Section 10.2 and Chapters
11 to 14. Section 10.2.3 discusses a measure, called the condition number, for
determining the accuracy needed to invert a matrix.
The inverse of the matrices in (4.1-32) and (4.5-4) will be singular or nearly
singular when the time between measurements is very small, that is, when the
time between measurements T of (4.1-18) or (4.1-28) is small. Physically, if
range measurements are only being made and they are too close together, then
the velocity of the state vector X
Ã
n;n

and acceleration as it passed through the origin. In contrast, if the target were
being tracked far from the origin, way off to the right on the x axis in Figure
10.1-1, range only measurements would then provide a good estimate of the
target’s velocity and acceleration.
If the radar only measured target azimuth, then the radar measurements
would convey more information when the target passed through the origin than
when it was far from the origin. Thus it is desirable to make two essentially
independent parameter measurements on the target, with these being essentially
orthogonal to each other. Doing this would prevent the matrix inversion from
tending toward singularity, or equivalently, prevent T from not having full rank.
Methods are available to help minimize the sensitivity to the computer
round-off error problem discussed above. They are called square-root filtering
[79] or voltage-processing filtering. This type of technique was introduced in
Section 4.3. Specifically the Gram–Schmidt method was used to introduce this
type of technique. In this chapter we will first give further general details on the
technique followed by detailed discussions of the Givens, Householder, and
Gram-Schmidt methods in Chapters 11 to 13. For completeness, clarity,
convenience and in order that this chapter stand on its own, some of the results
Figure 10.1-1 Geometry for example
of target flying by radar. (From Morrison
[5, p. 319].)
266
VOLTAGE LEAST-SQUARES ALGORITHMS REVISITED
given in Section 4.3 will be repeated. However, it is highly recommended that if
Sections 4.2 and 4.3 are not fresh in the reader’s mind that he or she reread them
before reading the rest of this chapter.
10.2 ORTHOGONAL TRANSFORMATION OF
LEAST-SQUARES ESTIMATE ERROR
We proceed initially by applying an orthonormal transformation to eðX
Ã

Ã
n;n
À Y
ðnÞ
ð10:2-5Þ
or
eðX
Ã
n;n
Þ¼kEk
2
¼ e
T
ð10:2-6Þ
where e
T
was first used in (1.2-33).
Applying an s  s orthonormal transformation F to E, it follows from
(4.3-21), and also reference 79 (p. 57), that
eðX
Ã
n;n
Þ¼kFEk
2
¼kFTX
Ã
n;n
À FY
ðnÞ
k

0

|ffl{zffl}
m
0
gm
0
gs À m
0
ð10:2-8Þ
where U is an upper triangular matrix. For example U is of the form
U ¼
u
11
u
12
u
13
u
14
0 u
22
u
23
u
24
00u
33
u
34

0
ð10:2-10Þ
and
FY
ðnÞ
¼
Y
0
1
---
Y
0
2
2
4
3
5
o
m
0
o
s À m
0
ð10:2-11Þ
On substituting (10.2-10) and (10.2-11) into (10.2-7) for eðX
Ã
n;n
Þ,itisa
straightforward matter to show that
eðX

This was shown in Section 4.3 for the special case where s ¼ 3, m
0
¼ 2; see
(4.3-49). We shall now show that it is true for arbitrary s and m
0
. Equations
(10.2-12) and (10.3-13) follow directly from the fact that FTX
Ã
n;n
and FY
ðnÞ
are
column matrices so that FTX
Ã
n;n
À FY
ðnÞ
is a column matrix, E being given by
(10.2-5). Let the elements of FE be designate as "
0
1
¼ 1; 2; ...; s. Hence from
268
VOLTAGE LEAST-SQUARES ALGORITHMS REVISITED
(10.2-5), (10.2-10), and (10.2-11)
FE ¼ E
0
¼
"
0

6
6
6
6
6
6
4
3
7
7
7
7
7
7
7
7
7
7
7
7
5
¼
UX
Ã
n;n
À Y
0
1
--------------
ÀY

X
s
i¼m
0
þ1
"
2
1
ð10:2-15Þ
which yields (10.2-12) and (10.2-13) for arbitrary s and m
0
, as we wished to
show.
The least-squares estimate X
Ã
n;n
now becomes the X
Ã
n;n
that minimizes
(10.2-13). Here, X
Ã
n;n
is not in the second term of the above equation so that this
term is independent of X
Ã
n;n
. Only the first term can be affected by varying X
Ã
n;n

Ã
n;n
¼
x
Ã
1
x
Ã
2
x
Ã
3
x
Ã
4
2
6
6
6
4
3
7
7
7
5
ð10:2-17Þ
and
Y
0
1

44
x
Ã
4
¼ y
0
4
ð10:2-19Þ
and trivially
x
Ã
4
¼
y
0
4
u
44
ð10:2-20Þ
We next use the second equation from the bottom of (10.2-16), which is
u
33
x
Ã
3
þ u
34
x
Ã
4

, and in turn the top equation then is used to solve for x
Ã
1
.
The above technique for solving (10.2-16) when U is an upper triangular
matrix is called the ‘‘back-substitution’’ method. This back-substitution method
avoids the need to solve (10.2-16) for X
Ã
n;n
using
X
Ã
n;n
¼ U
À1
Y
0
1
ð10:2-23Þ
with the need to compute the inverse of U. The transformation of T to the upper
triangular matrix T
0
followed by the use of the back-substitution method to
solve (10.2-16) for X
Ã
n;n
is called voltage least-squares filtering or square-root
processing. The use of voltage least-squares filtering is less sensitive to
computer round-off errors than is the technique using (4.1-30) with W given by
(4.1-32). (When an algorithm is less sensitive to round-off errors, it is said to be