Orthogonal Functions and Fourier Series University of Texas at Austin CS395T - Advanced Image Synthesis Spring 2006 Don Fussell Vector Spaces Set of vectors Operations on vectors and scalars Vector addition: v1 + v2 = v3 Scalar multiplication: sn v1 = v2 Linear combinations: ai v i v i 1 Closed under these operations Linear independence Basis Dimension University of Texas at Austin CS395T - Advanced Image Synthesis Fussell Spring 2006 Don Vector Spaces Pick a basis, order the vectors in it, then all vectors in the space can be represented as

sequences of coordinates, i.e. coefficients of the basis vectors, in order. Example: Cartesian 3-space Basis: [i j k] Linear combination: xi + yj + zk Coordinate representation: [x y z] a [ x1 y1 z1 ] b[ x2 y2 z2 ] [ax1 bx2 ay1 by2 University of Texas at Austin CS395T - Advanced Image Synthesis Fussell az1 bz2 ] Spring 2006 Don

Functions as vectors Need a set of functions closed under linear combination, where Function addition is defined Scalar multiplication is defined Example: Quadratic polynomials Monomial (power) basis: [x2 x 1] Linear combination: ax2 + bx + c Coordinate representation: [a b c] University of Texas at Austin CS395T - Advanced Image Synthesis Fussell Spring 2006 Don Metric spaces Define a (distance) metric d( v 1 , v 2 ) R s.t. d is nonnegative v i , v j V : d( v i , v j ) 0 d is symmetric v i , v j V : d( v i , v j ) d( v j , v i ) Indiscernibles are identical v i , v j V : d( v i , v j ) 0 v i v j The triangle inequality holds v i , v j , v k V : d( v i , v j ) d( v j , v k ) d( v i , v k )

University of Texas at Austin CS395T - Advanced Image Synthesis Fussell Spring 2006 Don Normed spaces Define the length or norm of a vector v v V : v 0 Nonnegative v 0 v 0 Positive definite v V, a F : a v a v Symmetric The triangle inequality holds v i , v j V : v i v j v i v j Banach spaces normed spaces that are complete (no holes or missing points) Real numbers form a Banach space, but not rational numbers Euclidean n-space is Banach University of Texas at Austin CS395T - Advanced Image Synthesis Fussell

Spring 2006 Don Norms and metrics Examples of norms: p norm: p=1 manhattan norm p=2 euclidean norm Metric from norm Norm from metric if D xi i 1 p 1 p

d( v 1 , v 2 ) v 1 v 2 d is homogeneous v i , v j V, a F : d(a v i , a v j ) a d( v i , v j ) d is translation invariant v i , v j V, a F : d( v i , v j ) d( v i a, v j a) then v d( v, 0) University of Texas at Austin CS395T - Advanced Image Synthesis Fussell Spring 2006 Don Inner product spaces Define [inner, scalar, dot] product v i , v j R s.t. vi v j , vk vi , vk v j , vk a v i , v j a v i , v j vi , v j v j , vi v, v 0 v, v 0 v 0 For complex spaces:

Induces a norm: vi , v j v j , vi v v i , a v j a v i , v j v, v University of Texas at Austin CS395T - Advanced Image Synthesis Fussell Spring 2006 Don Some inner products Multiplication in R Dot product in Euclidean n-space D v 1 , v 2 v 1, i v 2, i i 1 For real functions over domain [a,b] b

f , g f ( x) g ( x)dx a For complex functions over domain [a,b] b f , g f ( x) g ( x) dx a Can add nonnegative weight function b f ,g w f ( x) g ( x) w( x)dx a University of Texas at Austin CS395T - Advanced Image Synthesis Fussell Spring 2006 Don Hilbert Space An inner product space that is complete wrt

the induced norm is called a Hilbert space Infinite dimensional Euclidean space Inner product defines distances and angles Subset of Banach spaces University of Texas at Austin CS395T - Advanced Image Synthesis Fussell Spring 2006 Don Orthogonality Two vectors v1 and v2 are orthogonal if v 1 , v 2 0 v1 and v2 are orthonormal if they are orthogonal and v , v v , v 1 1 1 2 2 Orthonormal set of vectors v i , v j i , j (Kronecker delta)

University of Texas at Austin CS395T - Advanced Image Synthesis Fussell Spring 2006 Don Examples Linear polynomials over [-1,1] (orthogonal) 1 B0(x) = 1, B1(x) = x x dx 0 1 Is x2 orthogonal to these? 2 3 x 1 orthogonal to them? (Legendre) Is 2 University of Texas at Austin CS395T - Advanced Image Synthesis Fussell

Spring 2006 Don Fourier series Cosine series B0 ( ) 1, B1 ( ) cos( ), Bn ( ) cos( n ) 2 cos(m ) cos(n )d 0 2 1 (cos[(m n) ] cos[(m n) ]) for m n 0 2 0 1 1 2 ( sin[(m n) ] sin[(m n) ]) 0 0 2( m n ) 2(m n) University of Texas at Austin CS395T - Advanced Image Synthesis Fussell

Spring 2006 Don Fourier series 2 2 cos (n )d for m n 0 0 2 2 cos (0)d 2 for m n 0 0 Sine series B0 ( ) 0, B1 ( ) sin( ), Bn ( ) sin(n ) 2

sin(m ) sin( n )d 0 for m n or m n 0 0 for m n 0 University of Texas at Austin CS395T - Advanced Image Synthesis Fussell Spring 2006 Don Fourier series Complete series f ( x) an cos(nx) bn sin( nx) n 0 2 cos(m ) sin(n )d 0

0 Basis functions are orthogonal but not orthonormal Can obtain an and bn by projection 2 2 f ( x) cos(kx) dx cos(kx) dx a cos(nx) b sin(nx) i 0 0 i n 0 2 ak cos 2 (kx) dx ak

(or 2 ak for k 0) University of Texas at Austin CS395T - Advanced Image Synthesis 0 Fussell Spring 2006 Don Fourier series 1 ak 2 f ( x) cos(kx) dx 0 1 a0 2 2

f ( x) dx 0 Similarly for bk 1 bk 2 f ( x) sin(kx) dx 0 University of Texas at Austin CS395T - Advanced Image Synthesis Fussell Spring 2006 Don