Study guide for Examlet 7

$\let\b=\mathbf$ Here is a non-exhaustive list of questions you should be able to answer as you prepare for the examlet.

Past chapters

See the

(Recall from the course policies that our examlets are cumulative.)

In prepararation for the final, examlet 7 will have its questions drawn more evenly from the entirety of the class. (This is in contrast to examlets 1 through 6 that had a somewhat heavy focus on recent material.)

There is also not very much material that is new compared to examlet 6. Some guidelines on that new material are below.

SVD

Least Squares

  • (continued from examlet 6)
  • What is the pseudoinverse? of a diagonal matrix? of a full matrix? How is it computed? How can it be used to solve least-squares problems?
  • How do the normal equations compare, numerically speaking, to the solution of least-squares problems using the SVD?

Data Fitting

  • How can a linear model be fitted to given data using a least-squares problem? What does the matrix in the resulting least-squares problem mean? What type of matrix is it? What is the right-hand side? What do the components of the solution mean?
  • What will (typically) happen if you use more data in a data fitting problem?
  • What will (typically) happen if you increase model complexity (e.g. use a larger basis, with more coefficients) but keep the amount of data the same?
  • What types of models are suited for least-squares data fitting? Which ones are not?
  • What effect do outliers have on least-squares data fitting?

Applications of the VSD

  • How can the 2-norm of a matrix be computed using the SVD? (Why?)
  • How can the 2-norm condition number of a matrix be computed using the SVD? (Why?)

Low-Rank Approximation

  • What is an outer product? What is the rank of an outer product?
  • How can the SVD be interpreted as a sum of outer products? What is the 2-norm of each of the terms in the sum of outer products?
  • How can the 'sum-of-outer-products' interpretation of the SVD be used for low-rank approximation? What optimality guarantees are available for low-rank approximation? What does the Eckart-Young theorem say?

Iteration and Convergence

  • What does 'linear convergence' mean? What does 'quadratic convergence' mean? What is the 'convergence rate' for these?
  • How can both of these be recognized by the number of accurate digits in successive iterations of an iterative method?

Solving Equations

  • What is the bisection method? How does it work? What is its rate of convergence?