Virginia Tech · Spring 2018 · CRN 18781

CMDA 3606 is a course devoted to variations on the equation $Ax=b$. Not only do we see how such equations arise from static equilibrium problems in circuits and structures; we will also consider a variety of inverse problems, for example, associated with image deblurring. Course topics include modeling linear systems; the singular value decomposition; matrix approximation, PCA, and recommender systems; regularized least squares probelms and imaging applications; solving large-scale linear systems via Krylov methods; unconstrained nonlinear optimization.

Classes:

Monday/Wednesday, 2:30-3:45pm, McBryde 308

Instructor:

Mark Embree, embree@vt.edu, 575 McBryde

Office Hours:

Monday 4-5:30pm, Tuesday 4-5:30pm, Friday 12:30-1:30pm, or by appointment

Piazza:

The course Piazza page provides a forum for class discussions.

2 May 2018: Lecture 28

Summary of the course; review for final exam.
Thank you all for a great semester!

30 April 2018: Lecture 27

Nonlinear optimization: Overview of constrained optimization
Lagrange multipliers, quadratic programming and the Karush-Kuhn-Tucker matrices
You do not need to know details of these ideas for the final exam: this lecture just provided an overview of these important techniques.
Reading: Chapters 12 and 16 of Nocedal and Wright, Numerical Optimization.

25 April 2018: Lecture 26

Nonlinear optimization: Newton's method for multivariable optimization
Problem Set 11 is due on Thursday, April 26.

23 April 2018: Lecture 25

Nonlinear optimization: Line search algorithms
General descent directions and the Wolfe conditions for stepsize selection
Reading: Chapter 2 and Section 3.1 of Nocedal and Wright, Numerical Optimization.
Problem Set 11 is due on Thursday, April 26.

18 April 2018: Lecture 24

Introduction to nonlinear optimization
Line search algorithms: steepest descent
Reading: Chapter 2 of Nocedal and Wright, Numerical Optimization.
Problem Set 11 is due on Thursday, April 26.

16 April 2018: Lecture 23

The GMRES algorithm: restarting and smoothing
Preconditioning: Solve $(PAQ)y=Pb$ with $x = Qy$ to improve GMRES convergence.
Reading: course notes, Chapter 8: Iterations for Large Linear Systems (draft).
Problem Set 10 is due on Thursday, April 19.

11 April 2018: Lecture 22

The GMRES algorithm and its convergence
Reading: course notes, Chapter 8: Iterations for Large Linear Systems (draft).
Problem Set 9 is due on Thursday, April 12.
MATLAB code for Problem 3: blur2d.m, hokiebird.mat, mystery_plate.mat.
Problem Set 10 is due on Thursday, April 19.

9 April 2018: Lecture 21

Introduction to iterative methods for $Ax=b$, the GMRES algorithm
Reading: course notes, Chapter 8: Iterations for Large Linear Systems (draft).
Problem Set 9 is due on Thursday, April 12.
MATLAB code for Problem 3: blur2d.m, hokiebird.mat, mystery_plate.mat.

4 April 2018: Lecture 20

Exam 2 was proctored during the class period.
Problem Set 9 is due on Thursday, April 12.
MATLAB code for Problem 3: blur2d.m, hokiebird.mat, mystery_plate.mat.

2 April 2018: Lecture 19

Reading: course notes, Chapter 7: Inverse Problems and Regularization (draft).
Regularized least squares problems: image deblurring in two dimensions
See the books Hansen, Nagy, and O'Leary and by Hansen for many more details.
Exam 2 will be held in class on Wednesday, April 4.

28 March 2018: Lecture 18

Reading: course notes, Chapter 7: Inverse Problems and Regularization (draft).
Regularized least squares problems: Tikhonov regularization, deblurring in one dimension
See the books Hansen, Nagy, and O'Leary and by Hansen for many more details.
Problem Set 8 is due on Thursday, March 29.

26 March 2018: Lecture 17

Reading: course notes, Chapter 7: Inverse Problems and Regularization (draft).
Regularized least squares problems: truncated SVD and Tikhonov regularization
Problem Set 8 is due on Thursday, March 29.

21 March 2018: Lecture 16

Reading: course notes, Chapter 6: Singular Value Decomposition (draft).
Empirical principal component analysis (PCA)
MATLAB PCA demo: wine_pca.m and supporting data wine_data.m from the UCI Machine Learning Database.
Problem Set 8 is due on Thursday, March 29.

19 March 2018: Lecture 15

Reading: course notes, Chapter 6: Singular Value Decomposition (draft).
Principal component analysis (PCA)
Problem Set 7 is due on Thursday, March 22.

14 March 2018: Lecture 14

Reading: course notes, Chapter 6: Singular Value Decomposition (draft).
Singular Value Decomposition: pseudoinverse, matrix norms, low-rank approximation
Problem Set 6 is due on Thursday, March 15.
Problem Set 7 is due on Thursday, March 22.
Lenny Smith (London School of Economics) will present in the CMDA Distinguished Speaker Series on Pi Day (March 14), 4-5pm in NCB 260.

28 February 2018: Lecture 13

Reading: course notes, Chapter 6: Singular Value Decomposition (draft).
Singular Value Decomposition (full, reduced, and dyadic versions)
Problem Set 5 is due on Thursday, March 1.
Lenny Smith (London School of Economics) will present in the CMDA Distinguished Speaker Series on Pi Day (March 14), 4-5pm in NCB 260.

26 February 2018: Lecture 12

Reading: course notes, Chapter 6: Singular Value Decomposition (draft).
Introduction to the Singular Value Decomposition (full rank case)
Problem Set 5 is due on Thursday, March 1.

21 February 2018: Lecture 11

Exam 1 was proctored during the class period.
Problem Set 5 is due on Thursday, March 1.

19 February 2018: Lecture 10

Review of eigenvalues and eigenvectors
All eigenvalues of a symmetric matrix are real.
All eigenvectors of a symmetric matrix associated with distinct eigenvalues are orthogonal.
Practice Exam 1: Note that Exam 1 will take place during class on February 21.

14 February 2018: Lecture 9

Reading: course notes, Chapter 5: Orthogonality (draft).
Gram-Schmidt orthogonalization and $QR$ factorization.
MATLAB demos: projex1.m and projex2.m (use plotline3.m, plotplane3.m).
Eigenvalue valentine: be_mine.m
Problem Set 4 is due on Wednesday, February 14.
Practice Exam 1: Note that Exam 1 will take place during class on February 21.

12 February 2018: Lecture 8

Reading: course notes, Chapter 5: Orthogonality (draft).
Least squares theory: the solution is unique provided ${\cal N}(A)=\{0\}$.
The pseudoinverse $A^+ = (A^TA)^{-1} A^T$.
Introduction to projectors: matrices for which $P^2 = P$.
The matrix $AA^+$ is a projector.
Problem Set 4 is due on Wednesday, February 14.

7 February 2018: Lecture 7

Reading: course notes, Chapter 4: Fundamentals of Subspaces (draft).
Examples of least squares problems
The equation $(A^TA)x = A^Tb$ always has a solution.
Problem Set 4 is due on Wednesday, February 14.

5 February 2018: Lecture 6

Reading: course notes, Chapter 4: Fundamentals of Subspaces (draft).
The Fundamental Theorem of Linear Algebra
Introduction to least squares problems
Problem Set 3 is due on Wednesday, February 8.

31 January 2018: Lecture 5

Reading: course notes, Chapter 4: Fundamentals of Subspaces (draft).
Review of span, linear dependence, basis, dimension, rank, orthgonality
MATLAB codes for plotting lines and planes in 2d (plotline2.m, plotplane2.m) and 3d (plotline3.m, plotplane3.m).
Problem Set 3 is due on Wednesday, February 8.

29 January 2018: Lecture 4

Reading: course notes, Chapter 4: Fundamentals of Subspaces (draft).
Subspaces, column space, null space.
Problem Set 2: Problem 3 will be postponed until the next problem set. The updated problem set is available here.

24 January 2018: Lecture 3

Reading: course notes, Chapter 3: Simple Structures at Equilibrium (draft).
Modeling two-dimensional structures at equilibrium: potential for a null space.
Note: CMDA Computing Consultants are available to help with MATLAB. See the schedule for details.

22 January 2018: Lecture 2

Reading: course notes, Chapter 2: Linear Systems from Resistor Networks (draft).
Reading: course notes, Chapter 3: Simple Structures at Equilibrium (draft).
Circuit modeling.
Modeling one-dimensional structures at equilibrium.

17 January 2018: Lecture 1

Review of the course contract and discussion of notes/book options.
Reading: course notes, Chapter 1: Introduction.
Reading: course notes, Chapter 2: Linear Systems from Resistor Networks (draft).
Introduction to circuit modeling.

Problem Set 11

Posted 22 April 2018. Due Thursday 26 April 2018.
hw11.pdf: assignment

Problem Set 10

Posted 14 April 2018. Due Thursday 19 April 2018.
hw10.pdf: assignment

Problem Set 9

Posted 7 April 2018. Due Thursday 12 April 2018.
hw9.pdf: assignment
MATLAB code for Problem 3: blur2d.m, hokiebird.mat, mystery_plate.mat.

Problem Set 8

Posted 23 March 2018. Due Thursday 29 March 2018.
hw8.pdf: assignment
MATLAB code for Problem 3: coke_upc.m, mystery_upc.p.

Problem Set 7

Posted 17 March 2018. Due Thursday 22 March 2018.
hw7.pdf: assignment
MATLAB code for Problem 2: hello.m

Problem Set 6

Posted 8 March 2018. Due Thursday 15 March 2018.
hw6.pdf: assignment
MATLAB code for Problem 5: supreme_court.mat, cow.mat, planck.mat

Problem Set 5

Posted 23 February 2018. Due Thursday 1 March 2018.
hw5.pdf: assignment
MATLAB code for Problem 5: hw5.mat

Problem Set 4

Posted 8 February 2018. Due 14 February 2018.
hw4.pdf: assignment
MATLAB code for Problem 4: bridge.p, bridge_A.mat

Problem Set 3

Posted 1 February 2018. Due 8 February 2018.
hw3.pdf: assignment
MATLAB codes for plotting lines and planes in 2d (plotline2.m, plotplane2.m) and 3d (plotline3.m, plotplane3.m)

Problem Set 2

Posted 25 January 2018. Due 31 January 2018.
hw2.pdf: assignment

Problem Set 1

Posted 18 January 2018. Due 24 January 2018.
hw1.pdf: assignment

Full Course Contract

Download a copy of the electronic version of the course contract and tentative schedule.

Final course grades will be thus allocated:
40%: problem sets
40%: midterm exams (21 February and 4 April, in class)
20%: final exam (9 May, 10:05am-12:05pm)

Honor Code

Virginia Tech's Honor Code applies to all work in this course. Students must uphold the highest ethical standards, abiding by our Honor Code: "As a Hokie, I will conduct myself with honor and integrity at all times. I will not lie, cheat, or steal, nor will I accept the actions of those who do." From the Office for Undergraduate Academic Integrity: "Students enrolled in this course are responsible for abiding by the Honor Code. A student who has doubts about how the Honor Code applies to any assignment is responsible for obtaining specific guidance from the course instructor before submitting the assignment for evaluation. Ignorance of the rules does not exclude any member of the University community from the requirements and expectations of the Honor Code. For additional information about the Honor Code, please visit: www.honorsystem.vt.edu."

Text Books

We will not closely follow any one textbook; the instructor will provide notes for much of the course. The following books, all freely available online to Virginia Tech students, provide helpful background information.

Accommodations

Any student with special needs or circumstances requiring accommodation in this course is encouraged to contact the instructor during the first week of class, as well as Virginia Tech's SSD Office. We will ensure that these needs are appropriately addressed.