Summary

6 July

§1.1 - §1.2

Definition of Fourier Transform (L¹ version)

Motivated the inversion formula; stated these theorems:

• Jordan's theorem
• Pringsheim's theorem

Algebraic properties of the FT

• linearity
• symmetry (even and odd functions)
• conjugacy (FT of complex conjugate of f)
• dilations; notation: D_ag(t)=g_a(t):=a g(a t)
• translation in time: t_uf(t) := f(t-u)
• modulation (translation in frequency): t_wF(g)= F(g - w)
  Time domain modualtion of f: e^2ipwtf(t)

Modulation example; band-limited functions

HW -- 1.8(b,c)

---

7 July

§1.3, 1.4.1, 1.5, 1.6.3

Important functions

• sinc(x)=sin(px)/(px) or Dirichlet function d(x)=sin(x)/(px);
  FT[1_[-T,T]](g)=d_2pT(g)
• Poisson function, Fejér function
• Gaussian, g(t)=exp(-t²)/p^½
  FT[ g ](g)=exp(-(pg)²)

Analytic properties of the FT

• If f is L¹, then F is uniformly continuous and vanishes at infinity.
• FT[ f ^(m) ](g) = (2pig)^m F(g)
• FT[ (-2pit)^m f(t) ](g) = F^(m)(g)
• Convolution theorem: FT[ f*g ](g) = F(g) G(g)

Integral of sin(x)/x, all x, is p

HW -- 1.19(a) and 1.31

---

8 July

§1.7, 1.8.1

Inversion formula for FT

• Dini conditions on f at t
• Expressions for "partial sums"
• Proof of result

Solving a PDE (heat flow with a convective term) via FT techniques

HW -- 1.23(a) and 1.27

---

9 July

§1.10

Definition of FT on L² (space of finite energy signals)

If f is in both L¹ and L², then || F ||_L²=|| f ||_L²

Parseval/Plancheral Theorem: If f and g are in L², then

• || F ||_L²=|| f ||_L²
• < f,g > = < F,G > (Usual inner product.)

HW -- 1.26 and 1.35

---

12 July

§2.1-2.2 & §2.4

Dirac's delta function

Delta sequences (approximate identities)

• Gaussians
• "rectangles"

Distributions

• D, the space of infinitely differentiable, compactly supported functions; convergence in this space
• D', the dual to D, comprising all continuous linear functionals on D; these are the distributions
• Examples: delta functions; locally integrable functions

Elementary properties of distributions

• Linearity and continuity (definition)
• Equality of distributions
• Support of a distribution
• Sum of distributions
• Positive distributions

Schwartz space, S

• Infinitely differentiable functions with ``fast'' decay
• Seminorms or metric generate topology

HW -- 2.5(a) and 2.6

---

13 July

§2.4, §2.7.8-2.7.10

The Fourier transform of S is S.

Tempered distributions

• S', continuous linear functionals on S
• Fourier transform of a distribution FT[T](f) := T(FT[f])
• Derivatives of distributions: T'(f) := - T(f')
• Translation of distributions: (t_uT)(f) := T(t_-uf)
• Examples involving Dirac delta functions

Positive definite functions & Bochner's theorem

• Let f: R --> C be continuous. We say that f is positive definite if, for every set of distinct points {x₁,...,x_n} in R, the n×n matrix A with entries A_j,k = f(x_j - x_k) is positive semidefinite.
• Bochner's Theorem: f is positive definite if and only if f is the FT (distribution sense) of a nonnegative measure m.

HW -- 2.30, 2.34, 2.35

---

14 July

Multidimensional Fourier transform (§7.5, G. Folland, Fourier Analysis and Its Applications, Wadsworth & Brooks/Cole, Belmont, CA, 1992)

• Definition
• Convolution and Inversion theorems
• Multidimensional Schwartz space
• FT of Gaussians in several dimensions
• Properties--same as for one dimensional case, except that we have rotational invariance
• Radial functions

Fourier series, §3.1

• Definition for a 2W periodic L¹ function F(g)
• Fourier coefficients are regarded as a time series and F the frequency representaion of the time series
• Partial sums S_N(g)

HW -- 3.1(a), 3.7; problem on linear change of variables in FT

---

15 July

§3.3-3.4

Showed D_N(t)=sin((N+½)t)/sin(½t)

Dini conditions for convergence of FS; proved using FT version of results together with Dirichlet kernel

Operations with Fourier series

• Addition and scalar multiplication
• Integration
• Differentiation

Convolution theorem

Fejér Kernel W_N defined as the Cesáro mean of D_N

HW -- 3.11(b)

---

16 July

§3.4

Properties of Fejér's kernel W_N

F*W_N --> F (F continuous or L¹)

Approximate identity (delta sequence)

• Definition
• W_N is an example
• Get same convergence results as for W_N

Uniqueness theorem for fourier coefficients of F in L¹

Weierstrass approximation theorem

L² results

• {exp(-inpg/W)} is an orthonormal basis for square integrable 2W periodic functions
• Parseval's formula
• Riesz-Fischer theorem

HW -- 3.16

---

19 July

§3.5 and Notes

Wiener's Inversion Theorem

• A(T) is all 2W periodic functions that are Fourier series for l ¹ time series.
• Discrete convolution theorem
• Inversion theorem: If F is in A(T) and if F never vanishes, then 1/F is also in A(T).

Sampling Theorem

• Statement and proof in notes
• Band-limited functions
• Nyquist frequency
• Aliasing

HW

1. Show that the set {sinc(t - n)}_{n e Z} is orthogonal in L²(R).
2. What is the L²(R) span of this set?

---

20 July

§3.8 and notes on the DFT

HW

1. Prove that if f and g are in L(Z_N), then so it f*g.
2. Prove that DFT[f*g] = DFT[f]DFT[g]
3. Define the shift operator via t_jf[n]=f[n-j]. Find the DFT of t_jf in terms of the DFT of f.

---

21 July

Midterm test

---

22 July

§3.10 and class notes

The Poisson summation formula

• FT of the Dirac Comb
• Application to Gaussians

The discrete cosine transform (DCT)

---

23 July

Inverting the DCT

DCT and DFT

DFT and the FT

HW

1. Show that if the k^th entry of a row vector R_n is given by R_n[k] = cos(np(k+½)/N), then
   R_nR_m^T is N if m=n=0, N/2, if n=m>0, and 0 if m is not equal to n.
2. Write out the connection between the DFT and DCT for N=4.

---

26 July

§2.6.5-6 & class notes

Translation invariant systems

• Subspace X of distributions invariant under translations
• Operator L taking X to X, with these properties:
  1. L is linear
  2. L is translation invariant: t_aL = Lt_a

The operator L above is called a filter

Structure of filters

• Eigenfunctions L[e^2ipgt] = H(g) e^2ipgt (g fixed, real)
• FT(L[f]) = H(g) F(g) (H is the transfer function)
• L[f]=h*f (h is the impulse response (IR))

Causal filters

• "No output before input."
• Definition: L is causal if and only if f(t)=0 for all t < a implies L[f] = 0 for all t < a.
• L is causal iff h(t) = 0 for all t < 0. (Showed the condition on h was sufficient.)
• h(t) = 0 for all t < 0 iff H(g) is the Laplace transform of h evaluated at s = 2ipg
• Ideal low-pass filter is not causal

Discrete filters - act on two-sided sequences, the functions on Z

HW

1. Suppose that X is the space L¹. Show that if h is in L¹, then L[f] = h*f is a stable filter; i.e., ||L[f]|| < (constant)× ||f||.
2. Show that the condition h(t) = 0 for all t < 0 is necessary for L to be causal.
3. Show that if K and L are filters with IR functions g and h, respectively, then KL is a filter with IR g*h. (Take everything in L¹). If L is causal, what conditions on g make KL causal?

---

27 July

Surface fitting - class notes

• Problems come from geodesy, geophysics, graphics, map-making, meteorology, neural nets, and other areas.
• Common features. The data sites are in Rⁿ, where n may be 2, 3, or higher; one neural net application requires n=64. Sites where data are taken are scattered, possibly sparse. The function that fits the data should not "ripple" too much.
• For the one dimensional case, cubic splines provide an example of the type of solution that we want.

Background

• Roland Hardy empirically discovered the Hardy multiquadric approach, which uses interpolants that are linear combinations of m(x-x_j) = (1+|x-x_j|²)^1/2
• Jean Duchon took a variational approach similar to that used for splines, and got different interpolants. For the two dimensional case, he minimized the integral of the square of Du, subject to constraints. He obtained interpolants that are linear combinations of
  s(x-x_j) = |x-x_j| ² log(|x-x_j|²)
• Franke's conjecture. Richard Franke did a comparative sutdy of scattered data interpolation methods. The winners? Hardy's multiquadric method and Duchon's thin plate spline approach. Franke conjectured the invertibility of the interpolation matrix for the multiquadric.
• Madych/Nelson and Micchelli both proved the conjecture true. The Madych/Nelson approach was variational -- similar to Duchon's. Micchelli worked with "Laplace transforms" related to Gaussians.

HW
Let x₁=0, x₂=1, x₃=2. For each F below, find the eigenvalues for the interpolation matrix
A_j,k = F(|x_j - x_k|² )

1. F(r²)= exp(-r²) (Gaussian)
2. F(r²)= (1+r²)^1/2 (multiquadric)
3. F(r²)= r²log( r²) (thin plate spline)

References

1. J. Duchon, Interpolation des Fonctions de Deux Variables Suivant le Principe de la Flexion des Plaques Minces, Rairo Analyse Numerique 10 (1976), 5-12.
2. J. Duchon, Splines minimizing rotation invariant semi-norms in Sobolev spaces, pp. 85-100 in Constructive Theory of Functions of Several Variables, Oberwolfach 1976, W. Schempp and K. Zeller, eds., Springer-Verlag, Berlin, 1977.
3. R.L. Hardy, Multiquadric equations of topography and other irregular surfaces, J. Geophys. Res. 76 (1971), 1905-1915.
4. R.L. Hardy, Theory and Applications of the Multiquadric-Biharmonic Method, Comput. Math. Appl. 19 (1990), 163-208.
5. W.R. Madych and S.A. Nelson, Multivariate interpolation: a variational theory, manuscript, 1983.
6. W.R. Madych and S.A. Nelson, Multivariate interpolation and conditionally positive definite functions, Approx. Theory and its Applications 4 (1988), 77-79.
7. C.A. Micchelli, Interpolation of scattered data: distances, matrices, and conditionally positive definite functions, Const. Approx. 2 (1986), 11-22.

---

28 July

Radial basis functions & surface fitting

Polynomial reproducing methods.

• Let X = {x₁, ..., x_N} be a subset of Rⁿ and let p and q be any polynomials of degree m -1 or less. X is unisolvent if p(x_j) = q(x_j) implies that p=q; i.e., the two polynomials are identical.
• An interpolation method is polynomially reproducing if it reproduces a polynomial p of degree m-1 or less from data y_j = p(x_j) whenever X is unisolvent

Conditionally positive definite functions of order m.

• Let P be a matrix whose j^th row is a monomial of degree m -1 or less evaluated at x_j. The monomials used should span all polynomials of degree m-1 or less and X should be unisolvent.
• A continuous function h is said to be conditionlly positive definite of order m if for every n×1 column vector c in the null space of P we have c⁺Ac >= 0, with A=[h( x_k - x_j )].
• h is strictly conditionally positive definite if for c in the null space of P the equation c⁺Ac = 0 implies that c=0.
• If h is conditonally positive definite of order m and if the support of the distributional FT of h includes an open set in Rⁿ, then h is strictly CPD of order m.

Interpolation using translates - two types

1. No polynomial reproduction. Let h be a continuous strictly positive definite function. Use linear combinations of h( x - x_j ).
2. Degree m-1 polynomial reproduction is required. Let h be a continuous strictly CPD function of order m. Use linear combinations of h( x - x_j ), together with all monomials of degree m-1 or less.

HW

1. Show that X is unisolvent if and only if the rank of P mentioned above is the dimension of the space of polynomials of degree m-1 or less. Use this to show that if X contains a unisolvent subset, then X is also unisolvent.
2. Suppose that {x₁, ..., x_N} are distinct real numbers. Show that if
   c₁exp(-2ipgx₁) + ... + c_Nexp(-2ipgx_N) = 0
   holds for all g in R, then c_j = 0 for j = 1 ... N. (Note: the x_j's are not necessarily integers, so the exponentials are not orthogonal, in general.)

---

29 July

Radial basis functions & surface fitting (continued)

Order 1 SCPD functions

• Reproducing the constants
• Y_data=Ac+P^Tb, c^TP^T=0, where P^T = column of ones and b=scalar
• Hardy multiquadric is an example of an order 1 SCPD function

Order m SCPD functions

• Reproducing the polynomials of degree less than or equal to m-1
• Let P be a matrix whose j^th row is a monomial of degree m -1 or less evaluated at x_j, and let the data sites be a unisolvent set.
• Equations: Y_data=Ac+P^Tb, P*c=0
• The thin plate spline is an example of an order 2 SCPD function

HW

1. Let P be the matrix described above, X a unisolvent set, and h is an order m SCPD function. Show that the interpolant
   f(x) = c₁h( x - x_j )+ ... + c_Nh( x - x_N ) + p_{m - 1}(x),
   where p is a polynomial of degree m - 1 or less, reproduces polynomials if the equations below hold
   Y_data=Ac+P^Tb, P*c=0

---

30 July

Radial basis functions & surface fitting (continued)

Order m radial CPDF

• CPD functions of order m in all dimensions
• Connection with completely monotonic functions
• Berstein-Widder theorem (completely monotonic functions)
• Schoenberg's theorem (order 0)
• Micchelli (order 1)
• Guo, Hu, & Sun (order m)

Associated quadratic forms and SCPD order m radial functions

HW

1. Find the dimension of the space of polynomials of degree k in n variables.
2. Show that the matrix below is invertible whenever h is order m SCPD and the data sites are a unisolvent for the polynomials of degree m in n variables.

   A		PT
   P		0

---

2 August

MATLAB demonstration of surface fitting with the Hardy multiquadrics

Basics for S²

• Spherical coordinates
• Metric tensor
• Invariant volume element
• Geodesics (great circles)
• Laplace-Beltrami operator
• Connection with Laplacian on R³

Fourier analysis on S²

• Homogeneous harmonic polynomials on R³
• Eigenfunctions of the Laplace-Beltrami operator, D_S

HW

1. Let D_S be the Laplace-Beltrami operator on the 2-sphere. For the usual inner product on S², show that <D_S f, g> = < f, D_S g>
2. Suppose D_S Y + l Y = 0. Show that l = - || Y_q ||² / || Y ||²

---

3 August

Construction of the spherical harmonics

• Eigenvalues, eigenfunctions of the Laplace-Beltrami operator
• Ladder operators, L₊ and L_-

Properties of the spherical harmonics

• Relation to harmonic polynomials on R³
• Orthonormal basis for L²

HW

1. Show that L₊ D_S = D_S L₊.
2. Show that the eigenfunctions of D_S (the spherical harmonics)corresponding to the eigenvalue l(l+1) have the form sin^|m|(q) × p(cos(q)) × exp(imj), where p is a polynomial of degree l - |m|.
3. Find all spherical harmonics of order 3.

---

4 August

Rotations in R³

• Orthogonal matrices, O(3)
• Determinant one orthogonal matrices, SO(3)
• The space of harmonic polynpmials homogeneous of degree l in R³ is invariant under rotations.
• Spherical harmonics of order l form a space invariant under rotations

The Addition Theorem

Positive definite kernels and functions on S²

HW

1. Let t = x.y. Show that the sum
   (1/4p)(P₀(t) + 3P₁(t) + ... + (2L+1)P_L(t))
   is a reproducing kernel on the space of spherical harmonics having order L or less.
2. Show that P_l(x.y) is positive definite on S². (Hint: Use the Addition Theorem.)

---

5 August

Postive definite functions on spheres

Schoenberg's theorem for S²

• Legendre expansions with nonnegative coefficients
• Strictly positive definite functions and Legendre series with positive coefficients

Schoenberg-Bingham Theorem

• Schur products of matrices
• (x.y)^k is positive difinite on all spheres
• Functions strictly postive definite on all spheres
• Example: exp(x.y) is SPD on all spheres

Interpolation with SPD functions and kernels

Series for the gravitational potential exterior to a sphere

HW

1. Show that 1 is the maximum value of |P_l(t)| on [-1,1]. (Hint: Let t = x . y; use the Addition Theorem.)
2. Show that the Schur product of two positive sem-definite matrices is also positive semi-definite.