or responsible for its content.
1051-320 Supplemental Notes, 12/21/2006 1
1051-320 Supplemental Notes, 12/21/2006
1.1
Transpose Matrix and Pseudoinverse Matrix
In an inverse problem, a nonsquare matrix with more rows than columns
yields more equations than unknowns. Consider the matrix A with 3 rows
and 2 columns:
A
=


1
0
2
4
4
4 This matrix may be applied to a two-element vector to produce a three-element
vector, e.g.,
x
=
317 ¸
A x
=
b


1
0
2
4
4
4
317 ¸ =
3
62
56 Now, what if A and b are known and x is to be found; we have three equations
in two unknowns:


1
0
2
4
4
4
x
0
x
1
¸= 36256
which implies that:
1 · x
0
+ 0 · x
1
=
3
2 · x
0
+ 4 · x
1
=
62
4 · x
0
+ 4 · x
1
=
56
We could use the principles of algebra to solve these three simultaneous equa-
tions, but lets try to use matrices. We know the system matrix A (3 rows and
2 columns) and the 3-element vector b. We need to construct a matrix from
A
that can operate legitimately on b. Our only choice is the transpose of A,
which is obtained by swapping the rows and columns:
A
=


1
0
2
4
4
4
= A
T
=
1 2 4
0
4
4
¸
We can apply this from the left to both sides of the matrix-vector product:
A
T
(A x)
=
A
T
b
³A
T
A
´ x = A
T
b
1 The product A
T
A
is square; in this case, A
T
A
is 2 × 2:
A
T
A
=
1 2 4
0
4
4
¸ 1 02444 = 21 24
24
32
¸
The determinant of this square matrix is nonzero:
det
21 24
24
32
¸=21·3224·24=96
which means that its inverse exists. We can use the equation for the inverse of
a 2 × 2 matrix that we derived last class to nd the inverse:
a c
b
d
¸
1
=
1
ad bc
d
c
b a
¸
³A
T
A
´
1
=
1
96
32 24
24 21
¸=
1
3 1
4 1
4
7
32
¸
We can multiply both sides of the equation by this term:
³A
T
A
´
1
·
³A
T
A
´ x=µ³A
T
A
´
1
· A
T
¶b
But
³A
T
A
´
1
·
³A
T
A
´=
1
3 1
4 1
4
7
32
¸· 21 24
24
32
¸= 1 0
0
1
¸=I
So the product of all the terms yields:
³A
T
A
´
1
·
³A
T
A
´ x = Ix=x
=
µ³A
T
A
´
1
· A
T
¶b
or:
x
=
µ³A
T
A
´
1
· A
T
¶b
This equation produces the matrix that inverts the imaging problem, but it
is not the strict inverse matrix. We call it the Moore-Penrose Pseudoinverse
and label it by a superscript dagger:
³A
T
A
´
1
· A
T
A In the current problem, the pseudoinverse is:
A =
³A
T
A
´
1
· A
T
= 1
3 1
4 1
4
7
32
¸· 1 2 4
0
4
4
¸
= 1
3 1
3
1
3 1
4
3
8 1
8
¸
2 Check the result by applying this matrix to the known vector b
A b
= 1
3 1
3
1
3 1
4
3
8 1
8
¸ 36256 = 317 ¸=x
which is the original input vector.
The Moore-Penrose pseudoinverse appears in many contexts, and not just
in imaging. If errors exist in the measurements of the known output vector
b
, the application of A produces the optimum estimate of the original input
vector x in a least-squares sense, i.e., the sum of the squares of the errors of
each component between x and its estimate A b
is a minimum.
1.2
Matrices as Imaging Systems
The input vector is viewed as samples of a 1-D continuous function f [x], as
in Figure 3.1 in the notes. The matrix that produces the ideal image is the
identity:
Ax
=
b
b
=
x
if A = I =




1
0
··· 0
0
1
··· 0
.
.
.
.
.
.
. .. ...
0
0
··· 1





The imaging system that translates the input by one component (by one
sample or one pixel) to the right is
A
=








0
0
··· 0 1
1
0
··· 0 0
0
1
. .. 0 0
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
0
0
··· 1 0








Note that each row is derived from that before by a circular translation (the
sample that disappears o the edge reappears on the other edge). This is
a circulant matrix, and only contains N unique components.
The sum of the identity matrix and the translation matrix is:
A
=








1
0
··· 0 0
0
1
··· 0 0
0
0
. .. 0 0
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
0
0
··· 0 1








+








0
0
··· 0 1
1
0
··· 0 0
0
1
. .. 0 0
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
0
0
··· 1 0








=








1
0
··· 0 1
1
1
··· 0 0
0
1
. .. 0 0
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
0
0
··· 1 1








3 This matrix computes a new image that is the sum of the original and an image
translated one pixel to the right. The matrix that computes the average of those
two pixels is:
A
=








1
2
0
··· 0
1
2
1
2
1
2
··· 0 0
0
1
2
. .. 0 0
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
0
0
···
1
2
1
2








In the 3 × 3 case, the determinant of the averaging matrix is:
det


1
2
0
1
2
1
2
1
2
0
0
1
2
1
2

= 14
which indicates that its inverse exists:


1
2
0
1
2
1
2
1
2
0
0
1
2
1
2


1
=


1
1
1
1 1
1
1
1 1 Note that the determinant of the inverse matrix is the reciprocal of the deter-
minant of the averaging matrix:
det


1
1
1
1 1
1
1
1 1
=4
Also note that the inverse of the averaging matrix computes dierences of the
values; it is a dierencer whereas the original matrix is an averager or an
integrator.
The 4 × 4 version of the 2-pixel averager is:
A
=




1
2
0
0
1
2
1
2
1
2
0
0
0
1
2
1
2
0
0
0
1
2
1
2




Its determinant is:
det




1
2
0
0
1
2
1
2
1
2
0
0
0
1
2
1
2
0
0
0
1
2
1
2



=0
So this matrix is NOT invertible.
4 As a last example, consider the operator that subtracts the original image
from the translated image. The matrix is:
A
=








1 0 ··· 0 +1
+1
1 ··· 0
0
0
+1
. ..
0
0
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
0
0
··· +1 1








In the 3 × 3 case, the matrix is:
A
=


1
0
+1
+1
1 0
0
+1
1 det


1
0
+1
+1
1 0
0
+1
1
= 0
So the inverse does not exist. The 4 × 4 matrix is:
A
=




1 0
0
+1
+1
1 0
0
0
+1
1 0
0
0
+1
1




det




1 0
0
+1
+1
1 0
0
0
+1
1 0
0
0
+1
1



= 0
So these matrices cannot be inverted. To see why, apply them to constant
input vectors:


1
0
+1
+1
1 0
0
+1
1 10
10
10
=
10 + 0 + 10
+10 10 + 0
0 + 10 10
=
0
0
0
0


1
0
+1
+1
1 0
0
+1
1 20
20
20
=
20 + 0 + 20
+20 20 + 0
0 + 20 20
=
0
0
0
0
Since two distinct input vectors produce the same output, we cannot
distinguish the two inputs from knowledge of the matrix A the output
vector b
; we need some additional information (what often is called a
boundary condition).
5