# Math 118: General Course Outline

## Course Description

118. Mathematical Methods of Data Theory. (4)
Lecture, three hours; discussion, one hour. Requisites: courses 42 and 115A. Introduction to computational methods for data problems with a focus on linear algebra and optimization. Matrix and tensor factorization, PageRank, assorted other topics in matrices, linear programming, unconstrained optimization, constrained optimization, integer optimization, dynamic programming, and stochastic optimization. P/NP or letter grading.

## Course Information:

Students will learn key processes of optimization and linear algebra which underlies data science. These include linear programming, unconstrained optimization, constrained optimization, integer optimization, dynamic programming, stochastic optimization, integer optimization, dynamic programming, and stochastic optimization.

## Textbook(s)

Required:
1. Elden, Lrs. Matrix Methods in Data Mining and Pattern Recognition. The Society for Industrial and Applied Mathematics, 2007.
2. Chong, E and S. Zak. An Introduction to Optimization, 4th edition. Wiley, 2013.

Supplemental:
3. Hillier, Frederick S. and Lieberman, Gerald J. Introduction to Operations Research, 9th edition. McGraw-Hill Higher Education, 2009.

## Schedule of Lectures

Lecture Section Topics

Week 1

Elden, Chong & Zak

Review of linear algebra, least squares, orthogonality; QR decomposition; Singular-value decomposition (SVD)

Elden:

Data Mining and Pattern Recognition, Vectors and Matrices (1.1)

Matrix-Vector Multiplication, Matrix-Matrix Multiplication, Scalar Product and Vector Norms, Matrix Norms, Linear Independence- Bases, The Rank of a Matrix (1.2, 2.1-2.6)

Linear Systems and Least Squares, LU Decomposition, Symmetric, Positive Definite Matrices, Perturbation Theory and Condition Number, Rounding Errors in Gaussian Elimination, Banded Matrices, The Least Squares Problem (3.1-3.6)

Orthogonal Vectors and Matrices., Elementary Orthogonal Matrices, Number of Floating Point Operations, Orthogonal Transformations in Floating Point Arithmetic (4.1-4.4)

Orthogonal Transformation to Triangular Form, Solving the Least Squares Problem, Computing or Not Computing Q, Flop Count for QR Factorization, Error in the Solution of the Least Squares Problem, Updating the Solution of a Least Squares Problem (5.1-5.2)

Singular Value Decomposition, Fundamental Subspaces, Matrix Approximation, Principal Component Analysis, Solving Least Squares Problems, Condition Number and Perturbation Theory for the Least Squares Problem, Rank-Deficient and Under-Determined Systems, Computing the SVD, Complete Orthogonal Decomposition (6.1-6.9)

Chong & Zak:

Real Vector Spaces, Rank of a Matrix, Linear Equations, Inner Products and Norms (2.1-2.4)

Linear Transformation, Eigenvalues and Eigenvectors, Orthogonal Projections, Quadratic Forms, Matrix Norms (3.1-3.5)

Week 2

Elden

Reduced-rank least squares; Tensor decomposition; Nonnegative matrix factorization

Elden:

Truncated SVD: Principal Components Regression, Krylov Subspace Method (7.1-7.2)

Introduction to Tensor Decomposition, Basic Tensor Concepts, A Tensor Singular Value Decomposition, Approximating a Tensor by HOSVD (8.1-8.4)

Week 3

Elden

Data analysis applications; Pagerank

Elden:

The k-Means Algorithm, Non-Negative Matrix Factorization (9.1-9.2)

Handwritten Digits and a Simple Algorithm, Classification using SVD Bases, Tangent Distance (10.0-10.3)

Preprocessing the Documents and Queries, The Vector Space Model, Latent Semantic Indexing, Clustering, Non-Negative Matrix Factorization, Lanczos-Golub-Kahan Bidiagonalization, Average Performance (11.1-11.7)

Pagerank, Random Walk and Markov Chains, The Power Method for Pagerank Computation, HITS (12.0-12.4)

Week 4

Chong & Zak

Linear optimization: modeling; Standard form; Duality

Chong & Zak:

Introduction to Linear Programing, Simple Examples of Linear Programs, Two-Dimensional Linear Programs, Convex Polyhedra and Linear Programming, Standard Form Linear Programs, Basic Solutions, Properties of Basic Solutions, Geometric View of Linear Programs (15.1-15.8)

Solving Linear Equations Using Row Operations, The Canonical Augmented Matrix, Updating the Augmented Matrix, The Simplex Algorithm, Matrix Form of the Simplex Method, Two-Phase Simplex Method, Revised Simplex Method (16.1-16.7)

Dual Linear Programs, Properties of Dual Problems (17.1-17.2)

Week 5

Chong & Zak

Linear optimization solvers (Simplex Method, Interior-Point Method)

Chong & Zak:

Introduction to Nonsimplex Methods, Khachiyan?s Method, Affine Scaling Method, Karmarkar?s Method (18.1-18.4)

Introduction to Problems with Equality Constraints, Problem Formulation, Tangent and Normal Spaces, Lagrange Condition, Second-Order Conditions, Minimizing Quadratics Subject to Linear Constraints (20.1-20.6)

Week 6

Chong & Zak

Unconstrained optimization: optimality condition, local-vs. global minimum, convex set and function; Solvers such as gradient descent and Newton Method

Chong & Zak:

Introduction to Convex Optimization Problems, Convex Functions, Convex Optimization Problems (22.1-22.3)

Week 7

Chong & Zak

Constrained optimization: KKT condition; Solvers such as Gradient Projection Method, Penalty Method and Multipliers Method

Chong & Zak:

Karush-Kuhn-Tucker Condition, Second-Order Conditions (21.1-21.2)

Introduction to Algorithms for Constrained Optimization, Projections, Projected Gradient Methods, Penalty Methods (23.1-23.3, 23.5)

Week 8

Hillier & Lieberman

Integer optimization: modeling, relaxations; Solvers such as cutting plane, Branch-N-Bound/Cut Methods

Hillier & Lieberman:

Perspectives on Solving Integer Programming Problems (12.1-12.5)

The Branch-and-Bound Technique and Its Application to Binary Integer Programming (12.6)

Branch-and-Bound Algorithm for Mixed Integer Programming (12.7)

Week 9

Hillier & Lieberman

Dynamic programming

Hillier & Lieberman:

A Prototype Example for Dynamic Programming (11. 1)

Characteristics of Dynamic Programming Problems (11.2)

Deterministic Dynamic Programming (11.3)

Week 10

Chong & Zak

Neural networks

Chong & Zak:

Introduction (13.1)

Single Neuron Training (13.2) (needs 12.3 - aolution to Ax=b minimizing |x| and 12.4 Kaczmarz?s Algorithm)

Backpropagation Algorithm (13.3)