Graphics Reference
In-Depth Information
where
D
−
1
is easy to compute—you simply invert all the elements of the diagonal.
If one of these elements is zero, the matrix is singular and no such inverse exists;
in this case, the
pseudoinverse
is also often useful. It's defined as
M
†
=
V
D
†
U
T
,
(10.44)
where
D
†
is just
D
with every nonzero entry inverted (i.e., you try to invert the
diagonal matrix
D
by inverting diagonal elements, and every time you encounter
a zero on the diagonal, you ignore it and simply write down 0 in the answer). The
definition of the pseudoinverse makes sense even when
n
=
k
; the pseudoinverse
can be used to solve “least squares” problems, which frequently arise in graphics.
The Pseudoinverse Theorem:
(a) If
M
is an
n
k
, the equation
Mx
=
b
generally represents
an overdetermined system of equations
2
which may have no solution. The vector
×
k
matrix with
n
>
x
0
=
M
†
b
(10.45)
represents an optimal “solution” to this system, in the sense that
Mx
0
is as close
to
b
as possible.
(b) If
M
is an
n
k
, and rank
n
, the equation
Mx
=
b
represents an underdetermined system of equations.
3
The vector
×
k
matrix with
n
<
x
0
=
M
†
b
(10.46)
represents an optimal solution to this system, in the sense that
x
0
is the
shortest
vector satisfying
Mx
=
b
.
Here are examples of each of these cases.
Example 1: An overdetermined system
The system
2
1
t
=
4
3
(10.47)
has
no
solution: There's simply no number
t
with 2
t
=
4 and 1
t
=
3 (see Fig-
ure 10.9). But among all the multiples of
M
=
2
1
, there
is
one that's closest to
(4
,
3)
the vector
b
=
4
3
, namely 2.2
2
1
=
4. 4
2.2
, as you can discover with elemen-
2
1
tary geometry. The theorem tells us we can compute this directly, however, using
the pseudoinverse. The SVD and pseudoinverse of
M
are
2
1
)
√
5
1
Figure
10.9:
The
equations
M
=
UDV
T
=(
1
t
2
1
have no common
solution. But the multiples of the
vector
[
21
]
4
3
√
5
(10.48)
=
M
†
=
VD
†
U
=
1
1
/
√
5
(
1
√
5
21
)
(10.49)
T
form a line in the
plane that passes by the point
(
4, 3
)
, and there's a point of this
line (shown in a red circle on the
topmost arrow) that's as close to
(
4, 3
)
as possible.
=
0.4
0.2
.
(10.50)
2. In other words, a situation like “five equations in three unknowns.”
3. That is, a situation like “three equations in five unknowns.”
