## Computational and Variational Inverse Problems, Fall 2015

This is the 1994-style web page for our class. Here you will find everything you need (other than slick web design!).

Handouts:
Assignments:
• Assignment #1 (Due September 23)
You will need the following MATLAB functions and other files for Assignment 1:
• deconv1D.m regularized 1D Gaussian deconvolution
• deconv2D.m regularized 2D Gaussian deconvolution
• apply.m matrix-free application of 2D blurring operator to an image
• longhorn.png Longhorn image
• Assignment #2 (Due October 14)
• descent.m and mycg.m. These are the Matlab codes that implement the (exact) Newton method to minimize the Rosenbrock function (i.e., the "banana" function); this was demo-ed in class on Oct. 5. If you wish you can build on these for Assignment 2 (you will have to add CG solution of the Newton system at each iteration and incorporate early termination to enforce positive curvature and to prevent "over-solving".)
• Assignment #3 (Due November 2)
You will need the following files to solve Problems 2 and 3 using FEniCS:
• circle.xml This file includes a finite element mesh for the unit circle for Problem 2.
• tntv.py This file includes some starter lines of python code for Problem 3 to define the mesh and finite element space and to evaluate the true and noisy images at each point of the mesh.
• unconstrainedMinimization.py This file includes an implementation of inexact Newton-CG to solve variational unconstrained minimization problems using the Eisenstat-Walker termination condition and an Armijo-based line search (early termination due to negative curvature is not necessary, since Problem 3 results in positive definite Hessians).
• energyMinimization.py This file includes an example of how to use the inexact Newton-CG nonlinear solver implemented in unconstrainedMinimization.py.
• image.dat This is the target image for Problem 3 that is read into tntv.py.
• nb.py This includes some utilities to plot functions on meshes. It's called by tntv.py. The default FEniCS plotting function warps the mesh in the vertical direction proportional to the magnitude of the field to be plotted, which doesn't look good for the image functions.
Besides these files, general FEniCS resources you will find useful for Problems 2 and 3 include the "Getting started with FEniCS" document and the two python notebooks linked above under "Handouts" (and dated 10/14/15).
• Assignment #4 (Due November 19)
• Assignment #5 (Due December 14) You will need the following files to solve Problem 2 using FEniCS (in addition to the usual nb.py):
• cgsolver.py An implementation of the standard conjugate gradient method (it will abort if it detects negative curvature). This implementation is appropriate to use for the Gauss-Newton approximation of the Hessian (which is guaranteed to be positive definite).
• cgsolverSteihaug.py This is an implementation of the conjugate gradient method that incorporates the Steihaug termination criterion (for negative curvature). This is required for the true Newton Hessian (which is not guaranteed to be positive definite).
• Poisson-InexactNewton.py This is the driver for the solution of the Poisson inverse problem using the inexact Newton method, with either the true Newton Hessian or the Gauss-Newton approximation of the Hessian.
Instructions for using Poisson-InexactNewton.py:
• To set the relative noise level and the regularization, you will have to edit the variables "noise_level" and "beta" (lines 87 and 88).
• To change the forward problem from diffusion to advection-diffusion, you will have to change the bilinear form "a_goal", which is used to generate the synthetic observations given the true parameter field (line 94); you will also have to change the bilinear forms "a_state" and "a_adj" for the forward and adjoint problems and their incremental variants (lines 148 and 152).
• To switch between Newton and Gauss_Newton methods, you will have to set the boolean flag "use_GaussNewton" in line 251. If the flag "use_GaussNewton" is set to "False", the true Newton Hessian and Steihaug-enhanced CG will be used. If the flag "use_GaussNewton" is set to "True", the Gauss Newton Hessian and standard CG will be used.
Lectures (Mon/Wed 9-11am, GDC 6.202)
• 08/26: Introduction to inverse problems
• 08/31: Prototype inverse problem: image deblurring; filter regularization, Tikhonov regularization
• 09/02: Error analysis for TSVD and Tikhonov regularization; choice of regularization parameter via L-curve and Morozov discrepancy principle
• 09/09: Solutions of prototype image deblurring problem for different regularization parameter, grid sizes, noise levels
• 09/14: Unconstrained optimization: first and second order optimality conditions; framework for a globally convergent line search method
• 09/21: Unconstrained optimization: Steepest descent method, convergence and examples; properties of quadratic forms
• 09/23: Unconstrained optimization: Newton's method and its convergence rate; numerical examples
• 09/28: Model PDE-constrained inverse problem and structure/properties of its Hessian operator
• 09/30: Unconstrained optimization: approximate Newton methods (BFGS, limited memory BFGS, Levenberg-Marquardt, modified Cholesky, Gauss-Newton)
• 10/05: Unconstrained optimization: Inexact Newton-conjugate gradient method
• 10/07: Introduction to variational calculus: linear elliptic boundary value problem
• 10/12: Introduction to variational calculus: nonlinear elliptic boundary value problem; infinite-dimensional Newton's method
• 10/14: Introduction to the FEniCS library for finite element solution of boundary value problems posed in weak form
• 10/19: Discretization of functionals and weak forms by finite elements; optimize-then-discretize vs. discretize-then-optimize
• 10/21: No class
• 10/26: Sensitivity analysis: computing the discrete gradient via the direct, adjoint, and Lagrangian methods; computing the infinite-dimensional gradient via the direct and adjoint methods
• 10/28: Sensitivity analysis: computing the infinite-dimensional gradient via the Lagrangian method; using hIPPYlib to solve inverse problems governed by PDEs using steepest descent
• 11/02: Sensitivity analysis: computing the discrete Hessian-vector product and infinite dimensional Hessian action via the second order Lagrangian
• 11/04: Discretization of inverse problems: optimize-then-discretize and discretize-then-optimize
• 11/09: Using hIPPYlib to solve inverse problems governed by PDEs using inexact Newton-conjugate gradients (Poisson log conductivity inversion example)
• 11/11: Sensitivity analysis: Nonlinear forward problems, mixed and inhomogeneous boundary conditions, boundary observations, and boundary inversion parameters
• 11/16: Use of FEniCS/hIPPYlib to study spectral properties of the Hessian operator for an advection-diffusion source inverse problem (dependence of the Hessian spectrum on mesh size, diffusivity coefficient, and noise level)
• 11/18: No class
• 11/23: Sensitivity analysis: Nonlinear forward problems, mixed and inhomogeneous boundary conditions, boundary observations, and boundary inversion parameters continued
• 11/25: No class
• 11/30: Sensitivity analysis: Time dependent advection-diffusion inverse problem
• 12/02: Bayesian approach to inverse problems; illustration for Antarctic ice sheet flow