ECEn
Department | College
of Engineering | BYU
Syllabus
Text:
Tarantola: Inverse
Problem Theory and Methods for Model Parameter Estimation. Here
is a link to order it online. http://gettextbooks.com/search/?isbn=0898715725.
You may also download it for free if you cannot purchase it (this is
intended mainly for third-world countries but you can definitely use
this until the book comes). The download link is here (also
contains errata): http://www.ipgp.jussieu.fr/~tarantola/Files/Professional/SIAM/index.html
This is a new text with focus on the modern interpretation of Inverse
(Inference) Problems using Monte-Carlo sampling strategies.
However, the Appendices are rich with additional material. The
author has a strong background in the geosciences and so many of his
examples are bent in that direction. However, the material he
teaches is of general use. I will try to adapt his treatment for
people familiar with the shift-invariant systems where the
inverse-theory is easier to understand. I strongly
recommending reading the introductions from the three additional
chapters provided below.
Other references:
1) Bertero and Boccacci, Introduction
to Inverse Problems in Imaging,
IOP Publishing Ltd, 1998
The first three chapters are available from IOP Publishing and I have
copied them here: Chapter 1,
Chapter 2, Chapter 3.
2) Vogel, Computational
Methods for Inverse Problems, SIAM,
2002, ISBN 0-89871-507-5
The first three Chapters from an old monograph are linked to.
Chapter 1: Introduction
Chapter 2: Analytical Tools
Chapter 3: Numerical Tools
Bibliography
3) MacKay, Information Theory, Inference, and Learning Algorithms, This
book is available in pdf-form for viewing from http://www.inference.phy.cam.ac.uk/mackay/itila/book.html.
It may not be printed out (as a whole book) because the book is
available for purchase. Of special interest is Chapters
29-31. But, you may find Chapters 27, 28, 32-35 relevant as well.
4) Lecture notes from an Inverse
Problems Course taught by Sze
Tan and Collin Fox at Auckland
University in New Zealand.
Chapter 1: Introduction to Inverse
Problems
Chapter
2: Linear Transformations
Chapter
3: Regularization Methods for Linear Inverse Problems
Chapter
4: Introduction to Probability and Statistics
Chapter
5: Bayesian Statistical Inference and Parameter Estimation
Chapter
6: The Recursive Linear Inverse Problem
Chapter
7: Stochastic Simulation
Chapter
8: Sampled Solutions to Inverse Problems
Chapter
9: Output Analysis
Scharf, Statistical Signal
Processing: Detection, Estimation, and Time-Series Analysis,
Addision-Wesley, 1991
Natterer and Wubbeling, Mathematical Methods in Image
Reconstruction,
SIAM, 2001
Nocedal and Wright, Numerical
Optimization, Springer-Verlag, 1999
Lagendijk and Biemond, Iterative
Identification and Restoration of Images, Klewer Academic
Publishers, 1991
Epstein, Introduction to the
Mathematics of Medical Imaging, Pearson Education, Inc., 2003
Saad, Iterative Methods for Sparse
Linear Systems, PWS Publishing, 1996
Moon and Stirling, Mathematical Methods and Algorithms for Signal
Processing, Prentice-Hall, 2000
MacKay, Information Theory,
Inference, and Learning Algorithms, Cambridge Press, 2003 (view online)
Prerequisites
I have not required specific courses as prerequisites. You will
need
to have familiarity with complex numbers, linear algebra, Fourier
transforms,
probability theory, multivariable calculus, and some exposure to
partial
differential equations. We will emphasize the most important
concepts
of these fields as we need them. In the future I will be
requiring EcEn 671 which will definitely help
you if you've taken it.
Introduction
Although not often formally identified, "inverse problems" arise in
almost
every engineering discipline. The definition of an inverse problem is
something
we will spend some time on in this course. But, informally, you have an
inverse problem whenever you are trying to determine some parameters (a
model) from a set of data (some measurements) and there is a loss of
information
going from the model to the data. Therefore, going backwards to
the
model from the data requires that you add information back using a
priori
knowledge. Examples of inverse problems are: measuring the wind
velocity
over the ocean from satellite-borne radar measurements, making an image
of the insides of a person using computed tomography or magnetic
resonance,
determining the carrier frequency of a modulated signal, and mapping
the
insides of the earth using seismic waves. All of these can be thought
of
as "inverse problems." In this course we will define inverse problems
and
discuss some general methodology for their solution. In particular we
will
focus on linear inverse problem. Using these tools, we will study some
classic and modern inverse problems.
About half of the course will be theoretical development and the
other
half will be application to specific problems. The theoretical
development
will be interspersed with the applications.
Grades in this class will be determined by completion of periodic
homework
assignments and satisfactory performance on a report plus in-class
presentation on an inverse-problems technique of your choosing and
a take-home (group project) final. (If you can find a problem
that dove-tails
with your current research you will probably find the report more
satisfying).
If you have not taken EE671 or feel a little weak with the math
notation, you may find this math review
helpful. If your probability theory is weak, you might find this statistical review helpful.
Schedule: (under
construction)
| Week |
Date |
Topics |
Notes
|
Reading
|
| 1 |
1/9, 1/11, 1/13
|
States of Information
|
|
1
|
| 2 |
1/18, 1/20
|
Inverse Solution
|
Inverse Problem Solutions
|
|
| 3 |
1/23, 1/25, 1/27
|
Wiener Filter, Sampling and Monte-Carlo
methods.
|
|
2
|
| 4 |
1/30, 2/1, 2/3
|
Monte-Carlo methods; Tikhonov methods
|
Least-squares |
|
| 5 |
2/6, 2/8, 2/10
|
Least-squares methods
|
Derivatives
|
3,6
|
| 6 |
2/13, 2/15, 2/17
|
Iterative Methods
|
SVD
|
|
| 7 |
2/21,
2/22, 2/24 |
Iterative Methods: Landweber, Projected
Landweber, Van-cittert,
Steepest Descent, |
Iterative Methods
|
|
| 8 |
2/27, 3/1, 3/3
|
Conjugate Gradient, Newton, POCS
|
Nonlinear iterative
|
|
| 9 |
3/6, 3/8, 3/10
|
Nonlinear Conjugate Gradient, BFGS,
|
|
|
| 10 |
3/13, 3/15, 3/17
|
Examples
|
CT,
Inverse Scattering
|
|
| 11 |
3/20, 3/22, 3/24
|
Robust Methods
|
Conditional Probability |
4
|
| 12 |
3/27, 3/29, 3/31
|
EM Algorithm, Lucy Richardson
|
uncertainty, Bounds |
|
| 13 |
4/3, 4/5, 4/7
|
Quantifying uncertainty
|
optimization, simplex figures
|
|
| 14 |
4/10, 4/12, 4/14
|
Reports
|
choosing priors
|
|
| 15 |
4/17
|
Reports
|
|
|
Homework
Homework will be given about once every 3 weeks, with any solutions
posted
or handed out in class. Full credit will be given if it is evident that
each problem in the homework set was given serious effort.
Homework is due by the end of the day on the day indicated. Late
Policy on homework is 75% for first week, 50% for second week and 25%
for third week past due date. You should turn in all homework at
some point because you
cannot get a B out of the course without eventually turning in all of
the homework.
#
|
Assignment
|
Due
|
Solutions
|
1
|
All
Exercies in First set of notes; Summaries 1 and 2
|
2/3
|
|
2
|
Implement
Metropolis, Gibbs, and Hamilton method to sample from k exp(-x2y2-x2-y2);
Summaries 3, 4, 5
|
2/10
|
|
3
|
Implement
conjugate gradient, steepest descent, and projected Landweber (project
onto the convex set of functions with values between [0,1]--i.e. clip
the image);
Summaries 6-11. The image to fix is here it was blurred with a separable
37x37 blackman window (normalized so that it sums to 1) with Gaussian
noise (sigma =0.10) added. Make what ever other design decisions you
need to. You may want to use the Fourier domain to do
calculations in.
|
3/3
|
|
4
|
Summaries
12-16; fan beam reconstruction
|
3/17
|
|
5
|
Summaries
17-21
|
3/31
|
|
Summaries
These are write-ups you make (preferrably typed up using LaTeX -- see
LyX or TeXMacs for easy ways to do this) that summarize the concept
described. The idea here is that you write your own set of mini
lecture notes as if you were going to have to teach the idea to
yourself again in 10 years. These summaries don't have to
be long but should express the idea in your own language and from your
own background. You should connect the idea described to other
concepts you already understand --- as many as possible and
practical. These summaries should
not be copied from some other source. You may refer to
other sources but I envision you writing a draft of the summary based
only on your memory and then going back and filling in the holes in
your understanding. All summaries should tie the idea back to
Inverse Problems and why they are relevant to inverse problems.
Again, these summaries don't have to be long (maybe a paragraph each)
and should not be just technical descriptions. You must use your
own words and language so that you could understand the notes in 10
years.
- Explain from a high-level perspective what is the solution to all
Inverse Problems.
- Explain the homogenous distribution and when you should be
concerned about it.
- Explain the Metropolis method for sampling from a distribution
and how it can be adapted for sampling from the posterior distribution
if samples of the prior distribution are available.
- Explain the Gibbs sampling method, it's relationship to the
Metropolis method, and when it might be useful.
- Explain how gradient information for certain pdf's might be
usefully applied to speed up the Metropolis method.
- Explain Linear Operators, the Fréchet Derivative and
Singular Value Decomposition
- Explain the Generalized Inverse and Regularization
- Discuss the relationship between probability theory and the
generalized Tikhonov functional
- Explain when and how minimizing the generalized Tikhonov
functional can be thought of as solving a linear system of equations
and/or filtering the generalized inverse in the spectral domain.
- Explain the Projected Landweber method and when it may be useful
practically
- Explain the difference between Steepest Descent and Conjugate
Gradient algorithms
- Explain the relationship between nonlinear conjugate gradient and
BFGS optimization
- Explain the Radon Transform and describe two methods for it's
inversion.
- Explain Inverse Scattering reconstruction using Fourier methods
- Explain the relationship between the Bayesian MAP Estimator, the
Wiener filter, and generalized Tikhonov regularization (in other words
what is a Bayesian MAP Estimator).
- Explain how choosing the regularization parameter in the generalized
Tikhonov functional is properly
viewed as a probabilistic exercise.
- What are Kuhn-Tucker conditions?
- Explain the EM Algorithm and when it might be useful
- Derive the Lucy-Richardson algorithm as an application of the EM
Algorithm and as a constrained optimization problem.
- Explain the Cramer-Rao bound and when it should be replaced with
a "Bayesian" bound.
- Discuss the Weiss-Weinstein bound and how it relates to the
Cramer-Rao bound.
Exams
There will be one report due with an in-class presentation. There
will be one final exam (consisting of closed book test on the
summaries). The report
should be on a topic of interest to you related to inverse
problem. Ideally it will show how inverse problem theory applies
to a
research problem you are working on but other inverse-problem topics
are acceptable. Come and talk to me if you have a question.
A requirement of the project is that you implement either a
Monte-Carlo method, the
(nonlinear) conjugate gradient algorithm or the BFGS algorithm and use
it for your
problem (see me for exceptions) Anytime you have to estimate
something from noisy
data (or vague specifications) you can set up the problem as an inverse
problem. Most optimization problems can be cast as an inverse
problem as well. The write-up should be about 10-15 pages
and should specify the problem, how it relates to inverse problems in
general, how others have solved the problem in the past, how inverse
problem theory we have talked about could be used (or adapted) to solve
the problem. The project should take you from 20-50 hours to
complete so gauge your time accordingly.
Grading Policy
- Final Exam -- 35%
- Report -- 35% (write-up 20%, in-class 15%)
- Class Participation -- 10%
- Homework -- 20%
I hope to give all A's and B's provided you are
attentive
in class and show that you have learned the material. Full credit for
class
participation will be given to students who attend class regularly and
are not sleeping while in class (I know for some of you the 1:00 hour
will make this challenging).
Disabilities
If you have any disabilities that may affect your performance, please
notify
me at the beginning of the course.
Related Web Sites
Inverse Problem Sites
Inverse Problem Links: http://www.me.ua.edu/inverse/
Inverse Problems Journal: http://www.iop.org/EJ/journal/0266-5611
Optimization Sites
Optimization Guide: http://www.ece.northwestern.edu/OTC/
A nice tutorial paper is
An Introduction to the Conjugate Gradient Method Without the Agonizing
Pain
by J.R. Shewchuk.
Site with useful Optimization links (inluding a Matlab code for a
line-search algorithm): http://www.csit.fsu.edu/~navon/mad5420.html
Top
of Page | ECEn
Department | College
of Engineering | BYU
