University of Massachusetts Department of Electrical and Computer Engineering ECE 608 - Signal Theory Spring, 2006 Detailed Course Outline I. Introduction A. Motivation 1. Everybody needs to know optimization (they might just not know it!) a. Occurs in many brances of ECE (examples below) b. Tough idea to learn on your own c. Gives you an advantage over your research competition 2. Key ideas for the course: Take abstract concepts (functional optimization) and attack it using nice geometrical concepts [Picture of projection.] a. Approximation: estimate from a finite number of measurements (i) Motivation (ii) Examples - System modeling - Image/voice coding - Estimation (iii) Requirements - A framework (signal space, representation) - A measure of "closeness" (norm) - A method to find the closest (projection) b. Optimization: choose the best signal in some sense (i) Motivation (ii) Examples - optimal signal sets - optimal radar pulse - optimal power control (iii) Requirements: Efficient techniques for finding the constrained optimal solution 3. Example: A fading channel with transmitter fading knowledge B. Some basics 1. Set operations (pg. xv of text) a. Union, intersection, subset b. Complement c. Set equality (and how to prove, generally) d. The null set e. Cardinality (i) Finite (ii) Countably infinite (iii) Uncountably infinite 2. Signal spaces a. Definition of a signal b. Defn: signal space c. Example: L_2[a,b] II. Linear Spaces A. Vector Spaces 1. Definition (Section 2.2) a. Set of elements and two operators b. Properties list c. Key properties (i) Closed under "+" (ii) Closed under "." d. Examples (i) R (ii) R^n (iii) Collection of all real-valued continuous functions (iv) L_2[a,b] [On last two, get our first experience with demonstrating closed under "+" and closed under "."] e. Cartesian product 2. Subspaces and linear combinations (Sections 2.3, 2.5) a. Subspaces (i) Definition (ii) Example: Subspaces of R^2 (iii) Proposition 1: M, N subspaces => M \intersect N is a subspace [mostly for proof technique] b. Linear combinations (i) Definition (ii) Defn: [S] = span(S) (iii) Example of two spans (that are equal) [to demonstrate how you prove set equality] c. Linear independence and dimension (i) Defn: Linear independence (ii) Defn: Basis (iii) Fact: Any two bases have the same number of vectors (iv) Defn: Dimension d. Representation [not in Chapter 2 of Luenberger] (i) Representation vector (ii) Digital comm example (iii) Signals = vectors B. Normed linear spaces (Section 2.6) 1. Definition of normed linear space a. Non-negative b. Triangle inequality c. Scaling 2. Examples a. Euclidean space with distance norm (E^n) b. C[a,b] [and proof] c. Continuous functions with different norm C. Some mathematical review (before moving to Banach) 1. Convexity (Section 2.4) a. Convexity defined b. Scaled convext set is convex [and proof] c. Convex hull 2. Open and closed sets (Section 2.7) a. Interior points (and interior) (i) definition (ii) sphere: S(x,e) (iii) examples with empty interiors b. Definition of an open set c. Closure points (and closure) d. Definition of a closed set e. Examples (i) complements (ii) intersections [and proof] (iii) unions 3. Convergence and continuity (Sections 2.8, 2.9) a. "Epsilon" definition of convergence (different than Luenberger) (i) definition (ii) limits are unique (iii) A closed <==> limit points are contained in A [proof] b. Basics of functions (i) domain, range (ii) one-to-one (bijective) (iii) onto (surjective) (iv) linearity (v) functional defined c. "Epsilon-delta" definition of continuity (i) definition (ii) sum of two continuous functions is continuous [proof] d. Cauchy sequences (i) definition (ii) convergence ==> Cauchy (normed linear space), but not vice versa e. Function convergence on R (i) pointwise convergence - defined - simple example: t/n on [0,1] (ii) uniform convergence - defined - simple example: t/n on [0,1] - pointwise but not uniform: t^n on [0,1] D. Banach Spaces (Section 2.11) 1. Defn: Completeness 2. Defn: Banach Space 3. Examples a. Real numbers b. Space of all real-valued continuous functions on [0,1] (i) not complete with norm \int |x(t)| dt (ii) complete with norm max |x(t)| - pointwise convergence (on [0,1]) - uniform convergence (on [0,1]) - limit is continuous - convergence under max |x(t)| III. Hilbert Spaces A. Inner products (Luenberger, 3.2) 1. Definition and Induced Norm a. Definition of pre-Hilbert (inner product) space (i) commutivity (ii) distribution (iii) scaling (iv) norm is non-negative b. The induced norm (i) definition (ii) proof that it is a norm - non-negativity trivial from (iv) above - scaling requires (i) and (iii) above - easy, but understand it - triangle inequality + Cauchy-Schwarz inequality (and proof) + triangle inequality established c. Inner product => norm, Is there always an inner product that induces a given norm? (i) Parallelogram Law (and proof) (ii) Show that the norm of C[0,1] cannot be induced by any inner product. 2. Examples a. R^n with standard "dot product" b. L_2[a,b] with "correlation" inner product 3. Definition of a Hilbert Space B. Orthonormal bases 1. Review of representation a. Linear independence and dimension (i) Linear independence (ii) Basis (iii) Dimension b. Representation c. Example: inner product *not* same as dot product of representations 2. The Gram-Schmidt Procedure (Section 3.5) a. Definition b. Example 3. Representation on orthonormal bases a. Uniqueness (linearly independent set) b. Inner product the same as dot product of representations C. The (Orthogonal) Projection Theorem (Section 3.3) 1. Problem statement/proof a. Existence b. Uniqueness c. Orthogonality Principle 2. Communications example D. Approximation in Hilbert spaces 1. The general case (Section 3.6) a. Problem statement b. Projection theorem ===> normal equations c. Gram matrix (i) Defined (ii) Determinant + definition + linear independence \neq 0 proposition 2. "Least-squares" estimation (The Matrix Case) a. Theory (Section 4.3) (i) Problem formulation (ii) Translating into terms we know (iii) Solution b. Example 1: Radar c. Example 2: Equalization /********* EXAM COVERS UP THROUGH HERE ***********/ 3. Minimum mean squared error estimation a. Some probability basics (i) Distribution/density functions (ii) Expectations b. Hilbert space of random variables (i) Single-dimensional - elements - expectation as inner product - verification (ii) Vector form c. MMSE Estimation (i) Criterion (ii) General solution (iii) Linear case d. Example: Equalization e. Comparing ``Least Squares'' and MMSE 4. Infinite-dimensional bases a. Complete orthonormal sequences (Section 3.8) b. Examples (i) Fourier Series (Sections 3.7 and 3.9) (ii) Orthogonal polynomials (iii) Sinc functions (iv) Orthogonal wavelets IV. Linear Functionals and Operators A. Dual spaces B. Inverses C. Adjoints V. Optimization A. Derivatives and differentials B. Convexity C. Lagrange Multipliers D. Kuhn-Tucker conditions