Transcript Document

Signal Processing
and
Representation Theory
Lecture 1
Outline:
• Algebra Review
–
–
–
–
–
Numbers
Groups
Vector Spaces
Inner Product Spaces
Orthogonal / Unitary Operators
• Representation Theory
Algebra Review
Numbers (Reals)
Real numbers, ℝ, are the set of numbers that we
express in decimal notation, possibly with infinite,
non-repeating, precision.
Algebra Review
Numbers (Reals)
Example: =3.141592653589793238462643383279502884197…
Completeness: If a sequence of real numbers gets
progressively “tighter” then it must converge to a
real number.
Size: The size of a real number aℝ is the square
root of its square norm:
a  a2
Algebra Review
Numbers (Complexes)
Complex numbers, ℂ, are the set of numbers that we
express as a+ib, where a,bℝ and i= 1.
Example: ei=cos+isin
Algebra Review
Numbers (Complexes)
Let p(x)=xn+an-1xn-1+…+a1x1+a0 be a polynomial
with aiℂ.
Algebraic Closure:
p(x) must have a root, x0 in ℂ:
p(x0)=0.
Algebra Review
Numbers (Complexes)
Conjugate: The conjugate of a complex number a+ib
is:
a  ib  a  ib
Size: The size of a real number a+ibℂ is the square
root of its square norm:
a  ib  (a  ib )(a  ib )  a 2  b 2
Algebra Review
Groups
A group G is a set with a composition rule + that
takes two elements of the set and returns another
element, satisfying:
– Asscociativity: (a+b)+c=a+(b+c) for all a,b,cG.
– Identity: There exists an identity element 0G such that
0+a=a+0=a for all aG.
– Inverse: For every aG there exists an element -aG
such that a+(-a)=0.
If the group satisfies a+b=b+a for all a,bG, then
the group is called commutative or abelian.
Algebra Review
Groups
Examples:
– The integers, under addition, are a commutative group.
– The positive real numbers, under multiplication, are a
commutative group.
– The set of complex numbers without 0, under
multiplication, are a commutative group.
– Real/complex invertible matrices, under multiplication
are a non-commutative group.
– The rotation matrices, under multiplication, are a noncommutative group. (Except in 2D when they are
commutative)
Algebra Review
(Real) Vector Spaces
A real vector space is a set of objects that can be
added together and scaled by real numbers.
Formally:
A real vector space V is a commutative group with a scaling operator:
(a,v)→av,
aℝ, vV, such that:
1. 1v=v for all vV.
2. a(v+w)=av+aw for all aℝ, v,wV.
3. (a+b)v=av+bv for all a,bℝ, vV.
4. (ab)v=a(bv) for all a,bℝ, vV.
Algebra Review
(Real) Vector Spaces
Examples:
•
•
•
•
•
The set of n-dimensional arrays with real coefficients is a
vector space.
The set of mxn matrices with real entries is a vector space.
The sets of real-valued functions defined in 1D, 2D,
3D,… are all vector spaces.
The sets of real-valued functions defined on the circle,
disk, sphere, ball,… are all vector spaces.
Etc.
Algebra Review
(Complex) Vector Spaces
A complex vector space is a set of objects that can be
added together and scaled by complex numbers.
Formally:
A complex vector space V is a commutative group with a scaling operator:
(a,v)→av,
aℂ, vV, such that:
1.
2.
3.
4.
1v=v for all vV.
a(v+w)=av+aw for all aℂ, v,wV.
(a+b)v=av+bv for all a,bℂ, vV.
(ab)v=a(bv) for all a,bℂ, vV.
Algebra Review
(Complex) Vector Spaces
Examples:
•
•
•
•
•
The set of n-dimensional arrays with complex coefficients
is a vector space.
The set of mxn matrices with complex entries is a vector
space.
The sets of complex-valued functions defined in 1D, 2D,
3D,… are all vector spaces.
The sets of complex-valued functions defined on the
circle, disk, sphere, ball,… are all vector spaces.
Etc.
Algebra Review
(Real) Inner Product Spaces
A real inner product space is a real vector space V
with a mapping V,V→ℝ that takes a pair of vectors
and returns a real number, satisfying:
– u,v+w= u,v+ u,w for all u,v,wV.
– αu,v=αu,v for all u,vV and all αℝ.
– u,v= v,u for all u,vV.
– v,v0 for all vV, and v,v=0 if and only if v=0.
Algebra Review
(Real) Inner Product Spaces
Examples:
– The space of n-dimensional arrays with real
coefficients is an inner product space.
If v=(v1,…,vn) and w=(w1,…,wn) then:
v,w=v1w1+…+vnwn
– If M is a symmetric matrix (M=Mt) whose eigenvalues are all positive, then the space of n-dimensional
arrays with real coefficients is an inner product space.
If v=(v1,…,vn) and w=(w1,…,wn) then:
v,wM=vMwt
Algebra Review
(Real) Inner Product Spaces
Examples:
– The space of mxn matrices with real coefficients is an
inner product space.
If M and N are two mxn matrices then:
M,N=Trace(MtN)
Algebra Review
(Real) Inner Product Spaces
Examples:
– The spaces of real-valued functions defined in 1D,
2D, 3D,… are real inner product space.
If f and g are two functions in 1D, then:

f , g   f (x )g (x )dx

– The spaces of real-valued functions defined on the
circle, disk, sphere, ball,… are real inner product
spaces.
If f and g are two functions defined on the circle, then:
2
f , g   f ( )g ( )d
0
Algebra Review
(Complex) Inner Product Spaces
A complex inner product space is a complex vector
space V with a mapping V,V→ℂ that takes a pair of
vectors and returns a complex number, satisfying:
– u,v+w= u,v+ u,w for all u,v,wV.
– αu,v=αu,v for all u,vV and all αℝ.
– u,v  v,u for all u,vV.
– v,v0 for all vV, and v,v=0 if and only if v=0.
Algebra Review
(Complex) Inner Product Spaces
Examples:
– The space of n-dimensional arrays with complex
coefficients is an inner product space.
If v=(v1,…,vn) and w=(w1,…,wn) then:
v,w  v1 w1  ...  vn wn
– If M is a conjugate symmetric matrix ( M  M t) whose
eigen-values are all positive, then the space of ndimensional arrays with complex coefficients is an
inner product space.
If v=(v1,…,vn) and w=(w1,…,wn) then:
v,wM=vMwt
Algebra Review
(Complex) Inner Product Spaces
Examples:
– The space of mxn matrices with real coefficients is an
inner product space.
If M and N are two mxn matrices then:
M, N  Trace M t N


Algebra Review
(Complex) Inner Product Spaces
Examples:
– The spaces of complex-valued functions defined in
1D, 2D, 3D,… are real inner product space.
If f and g are two functions in 1D, then:

f , g   f (x )g (x ) dx

– The spaces of real-valued functions defined on the
circle, disk, sphere, ball,… are real inner product
spaces.
If f and g are two functions defined on the circle, then:
2
f , g   f ( )g ( ) d
0
Algebra Review
Inner Product Spaces
If V1,V2V, then V is the direct sum of subspaces V1,
V2, written V=V1V2, if:
– Every vector vV can be written uniquely as:
v  v1  v2
for some vectors v1V1 and v2V2.
Algebra Review
Inner Product Spaces
Example:
If V is the vector space of 4-dimensional arrays, then
V is the direct sum of the vector spaces V1,V2V
where:
– V1=(x1,x2,0,0)
– V2=(0,0,x3,x4)
Algebra Review
Orthogonal / Unitary Operators
If V is a real / complex inner product space, then a
linear map A:V→V is orthogonal / unitary if it
preserves the inner product:
v,w= Av,Aw
for all v,wV.
Algebra Review
Orthogonal / Unitary Operators
Examples:
– If V is the space of real, two-dimensional, vectors and
A is any rotation or reflection, then A is orthogonal.
A(v1)
v2
v1
A=
A(v2)
Algebra Review
Orthogonal / Unitary Operators
Examples:
– If V is the space of real, three-dimensional, vectors
and A is any rotation or reflection, then A is
orthogonal.
A=
Algebra Review
Orthogonal / Unitary Operators
Examples:
– If V is the space of functions defined in 1D and A is
any translation, then A is orthogonal.
A=
Algebra Review
Orthogonal / Unitary Operators
Examples:
– If V is the space of functions defined on a circle and A
is any rotation or reflection, then A is orthogonal.
A=
Algebra Review
Orthogonal / Unitary Operators
Examples:
– If V is the space of functions defined on a sphere and
A is any rotation or reflection, then A is orthogonal.
A=
Outline:
• Algebra Review
• Representation Theory
– Orthogonal / Unitary Representations
– Irreducible Representations
– Why Do We Care?
Representation Theory
Orthogonal / Unitary Representation
An orthogonal / unitary representation of a group G
onto an inner product space V is a map  that sends
every element of G to an orthogonal / unitary
transformation, subject to the conditions:
1. (0)v=v, for all vV, where 0 is the identity element.
2. (gh)v=(g) (h)v
Representation Theory
Orthogonal / Unitary Representation
Examples:
– If G is any group and V is any vector space, then:
 ( g )v  v
is an orthogonal / unitary representation.
– If G is the group of rotations and reflections and V is
any vector space, then:
(g )v  det( g )v
is an orthogonal / unitary representation.
Representation Theory
Orthogonal / Unitary Representation
Examples:
– If G is the group of nxn orthogonal / unitary matrices,
and V is the space of n-dimensional arrays, then:
(g )v  g v 
is an orthogonal / unitary representation.
Representation Theory
Orthogonal / Unitary Representation
Examples:
– If G is the group of 2x2 rotation matrices, and V is
the vector space of 4-dimensional real / complex
arrays, then:
(g )x 1 , x 2 , x 3 , x 4   g (x 1 , x 2 ), g (x 3 , x 4 ) 
is an orthogonal / unitary representation.
Representation Theory
Irreducible Representations
A representation , of a group G onto a vector space
V is irreducible if cannot be broken up into smaller
representation spaces.
That is, if there exist WV such that:
(G)WW
Then either W=V or W=.
Representation Theory
Irreducible Representations
If WV is a sub-representation of G, and W is the
space of vectors perpendicular to W:
v,w=0
for all vW and wW, then V=WW and W is
also a sub-representation of V.
For any gG, vW, and wW, we have:
0  v , g 1 w  g v , g g 1 w g v ,w
So if a representation is reducible, it can be broken
up into the direct sum of two sub-representations.
Representation Theory
Irreducible Representations
Examples:
– If G is any group and V is any vector space with
dimension larger than one, then:
 ( g )v  v
is not an irreducible representation.
Representation Theory
Irreducible Representations
Examples:
– If G is the group of 2x2 rotation matrices, and V is
the vector space of 4-dimensional real / complex
arrays, then:
(g )x 1 , x 2 , x 3 , x 4   g (x 1 , x 2 ), g (x 3 , x 4 ) 
is not an irreducible representation since it maps the
space W=(x1,x2,0,0) back into itself.
Representation Theory
Why do we care?
Representation Theory
Why we care
In shape matching we have to deal with the fact that
rotations do not change the shape of a model.
=
Representation Theory
Exhaustive Search
If vM is a spherical function representing model M
and vn is a spherical function representing model N,
we want to find the minimum over all rotations T of
the equation:
D(T ,v M ,v N )  v M T v N 
 vM
2
 vN
2
2
 2 v M ,T v N 
Representation Theory
Exhaustive Search
If V is the space of spherical functions then we can
consider the representation of the group of rotations
on this space.
By decomposing V into a direct sum of its
irreducible representations, we get a better
framework for finding the best rotation.
Representation Theory
Exhaustive Search (Brute Force)
Suppose that {v1,…,vn} is some orthogonal basis for
V, then we can express the shape descriptors in terms
of this basis:
vM=a1v1+…+anvn
vN=b1v1+…+bnvn
Representation Theory
Exhaustive Search (Brute Force)
Then the dot-product of M and N at a rotation T is
equal to:
v M ,T v N 
 n
  a iv i ,T   b jv j
i 1
 j 1
n


n
n
1
1




a iv i ,  b jT v j 

i
j
n
ai b j

i j
, 1
v i ,T v j 
Representation Theory
Exhaustive Search (Brute Force)
So that the nxn cross-multiplications are needed:
v M ,T v N  
a i b j v i ,T v j 

i j
, 1
v1
T(v1)
+
+
v2
T(v2)
vn
+ =
+
…
=+
+
…
vM
n
T(vn)
T(vN)
Representation Theory
Exhaustive Search (w/ Rep. Theory)
Now suppose that we can decompose V into a
collection of one-dimensional representations.
That is, there exists an orthogonal basis {w1,…,wn}
of functions such that T(wi)wiℂ for all rotations T
and hence:
wi,T(wj)=0 for all i≠j.
Representation Theory
Exhaustive Search (w/ Rep. Theory)
Then we can express the shape descriptors in terms
of this basis:
vM=α1w1+…+αnwn
vN=β1w1+…+βnwn
Representation Theory
Exhaustive Search (w/ Rep. Theory)
And the dot-product of M and N at a rotation T is
equal to:
v M ,T v N 
 n
   i w i ,T    j w j
i 1
 j 1
n


n
n
1
1




 i w i ,   jT w j 

i
j
n
i  j

i j
, 1
n
w i ,T w j 
   i  i w i ,T w i 
i 1
Representation Theory
Exhaustive Search (w/ Rep. Theory)
So that only n multiplications are needed:
n
v M ,T v N     i i w i ,T w i 
i 1
T(w1)
+
+
w2
T(w2)
wn
+ =
+
…
=+
+
…
vM
w1
T(wn)
T(vN)