\documentclass[12pt,a4,finnish]{article}

\usepackage[applemac]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[finnish]{babel}

\usepackage{hyperref}


          % melkein article -tyyli
%\documentclass[landscape,11pt]{tentti}  % landscape -> landscape+twocolumn
\usepackage{amsmath,amsfonts}
\usepackage[dvips]{graphicx}
%\usepackage{jmp}

\newcommand{\FFF}{\ensuremath{\mathbf{F}}}
\newcommand{\rrr}{\ensuremath{\mathbf{r}}}
\newcommand{\iii}{\ensuremath{\mathbf{i}}}
\newcommand{\jjj}{\ensuremath{\mathbf{j}}}
\newcommand{\kkk}{\ensuremath{\mathbf{k}}}

\topmargin=-2cm \textheight=24cm \oddsidemargin=0cm
\evensidemargin=0cm \textwidth=15cm


%\selectlanguage{finnish}                 % tentin kieli: vaikuttaa otsikkoon
%\makeheader                              % tee otsake (ja aloita sivu)

\newcommand{\R}{{\mathbb R}}
\newcommand{\C}{{\mathbb C}}
\newcommand{\eye}{{\bf 1}}
\newcommand{\N}{{\mathbb N}}
\newcommand{\br}{{\bf r}} \newcommand{\bi}{{\bf i}}
\newcommand{\bff}{{\bf f}} \newcommand{\bS}{{\bf S}}
\newcommand{\bj}{{\bf j}} \newcommand{\bw}{{\bf w}}
\newcommand{\bv}{{\bf v}}\newcommand{\bu}{{\bf u}}
\newcommand{\bk}{{\bf k}} \newcommand{\ox}{{\overline x}}
\newcommand{\bx}{{\bf x}}
\newcommand{\mat}[1]{{\boldsymbol{#1}}}
\newcommand{\set}[2]{ \left\{ {#1}\,\big\vert\, {#2}\right\}}
\newcommand{\tpdop}[1]{\tfrac{\partial\ }{\partial #1}}
\newcommand{\Rnxn}{{\R^{n\times n}}}
\newcommand{\norm}[1]{\Vert #1 \Vert}
\newcommand{\thalf}{{\tfrac{1}{2}}}
\newcommand{\abs}[1]{\left| #1 \right|}


% Define arg min in a nice way
\newcommand{\argmin}{\mathop{\mathrm{arg\,min}}}

\begin{document}


\noindent
Inverse problems course exam \hfill  Published on March 17, 2017

\noindent
Lecturer: Samuli Siltanen
\bigskip

\noindent
This is a home exam. You are supposed to work alone; please do not collaborate or discuss your solutions with anyone.

Return your solutions by email to {\tt Samuli.Siltanen@helsinki.fi} no later than 12 o'clock noon on Monday, March 27, 2017. Instructions about the form of the material to be sent is given below in connection to each problem.

If you have practical questions about how to complete this home exam, please contact me by email. I will publish the questions and answers on the course website. 

\bigskip



\begin{enumerate}


\item {\bf How to return the solution to this problem? Send a scanned pdf document of your hand-written answer by email.} \\
Consider a computational model $\mathbf{A}\mathbf{f}=\mathbf{m}$ with $\mathbf{f}\in\R^n$ and $\mathbf{m}\in\R^k$. Assume given a data vector $\widetilde{\mathbf{m}}\in\R^k$. Regarding the inverse problem, we would like to find a mapping 
$\mathbf{R}:\R^k \rightarrow \R^n$ so that $\mathbf{R}(\widetilde{\mathbf{m}})$ would satisfy $\mathbf{A}\mathbf{R}(\widetilde{\mathbf{m}})=\widetilde{\mathbf{m}},$ but the construction of $\mathbf{R}$ may be an ill-posed problem. 
\begin{itemize}
\item[(a)] Write down such a matrix $\mathbf{A}$ and such a vector  $\widetilde{\mathbf{m}}$ that the construction of  $\mathbf{R}$ encounters problems with Hadamard's {\it uniqueness} condition. Take as small $k$ and $n$ as you can.
\item[(b)] Write down such a matrix $\mathbf{A}$ and such a vector  $\widetilde{\mathbf{m}}$ that the construction of  $\mathbf{R}$ encounters problems with Hadamard's {\it existence} condition. Take as small $k$ and $n$ as you can.
\item[(c)] Is it possible to give a finite-dimensional example of  a matrix $\mathbf{A}$ and  a vector  $\widetilde{\mathbf{m}}$ that the construction of  $\mathbf{R}$ encounters problems with Hadamard's {\it stability} condition? Why or why not?
\item[(d)] Write down the definition of a {\em regularization strategy}, following Definition 3.4.1 of the textbook. Explain in your own words (in less than one page) the idea of formula (3.11).
\end{itemize}

\newpage


\item {\bf How to return the solution to this problem? Use {\LaTeX} to write a pdf document containing your answers including the required plots. Send the pdf and your Matlab codes as email attachments.} \\
Let $f:[0,\infty)\rightarrow \R$. The Laplace transform $F$ of $f$ is defined by
\begin{equation}\label{laplace}
 F(s) = \int_0^\infty e^{-st}f(t)dt,\quad s\in\C ,
\end{equation}
provided that the integral converges. The direct problem is to determine $F$ for a given function $f$ according to (\ref{laplace}). The inverse problem is: {\em given a Laplace transform $F$, find the corresponding function $f$.}

Assume we know the values of $F$ at these real-valued points:
$$
 0<s_1<s_2<\ldots <s_n<\infty.
$$ 
Then we may approximate the integral in (\ref{laplace}) for example with the trapezoidal rule as
\begin{equation} \label{laptrap}
\begin{split}
 \int_0^\infty e^{-st}f(t)dt\, \approx\, \frac{t_k}{k} & \left( \frac{1}{2}e^{-st_1}f(t_1)+e^{-st_2}f(t_2)+e^{-st_3}f(t_3)+\ldots\right.\\   &\ \ \left. +e^{-st_{k-1}}f(t_{k-1})+\frac{1}{2}e^{-st_k}f(t_k)\right) ,
\end{split}
\end{equation}
where vector $t=[t_1\ t_2\ \ldots\ t_k]^T\in\R^k$, $0\leq t_1<t_2<\ldots <t_k$, contains the points at which the unknown function $f$ will be evaluated. By denoting $f_\ell=f(t_\ell), \ \ell=1,\ldots ,k$, and $m_j=F(s_j),\ j=1,\ldots ,n$, and using \eqref{laptrap}, we get a linear model of the form $m=Af+\epsilon$ with
\begin{equation}\label{LaplaceA} 
A = \frac{t_k}{k}\begin{bmatrix} \frac{1}{2}e^{-s_1t_1} & e^{-s_1t_2} & e^{-s_1t_3} & \ldots & e^{-s_1t_{k-1}} & \frac{1}{2}e^{-s_1t_k} \\
                       \frac{1}{2}e^{-s_2t_1} & e^{-s_2t_2} & e^{-s_2t_3} & \ldots & e^{-s_2t_{k-1}} & \frac{1}{2}e^{-s_2t_k} \\
                       \vdots & & & & & \vdots \\
                       \frac{1}{2}e^{-s_nt_1} & e^{-s_nt_2} & e^{-s_nt_3} & \ldots & e^{-s_nt_{k-1}} & \frac{1}{2}e^{-s_nt_k} \end{bmatrix}.
\end{equation}
\begin{itemize}
\item[(a)] Do a little literature study and explain in your own words what is the Laplace transform good for. Where is it used? The answer can be short, like half a page or so.
\item[(b)] Compute numerically and plot the Laplace transform of 
$$
  f(t) = \left\{\begin{array}{ll}1,&\mbox{ for }0\leq t \leq 1,\\0, &\mbox{ otherwise,}\end{array}\right.
$$
in an interval that nicely shows the crucial shape of the function.

\item[(c)] Construct matrix $A$ given by (\ref{LaplaceA}) for a suitable choice of points $t_\ell$ and $s_j$. Compute and plot the singular values of $A$. Do you detect ill-posedness?

\item[(d)] Use truncated SVD to compute the inverse Laplace transform of $F$. Plot the result and compute the relative error.
\end{itemize}



\newpage

\item {\bf How to return the solution to this problem? Use {\LaTeX} to write a pdf document containing your answers including the required plots. Send the pdf and your Matlab codes as email attachments.} \\[10pt]
Download the files\\ 
{\tt recon\_Haar\_comp.m}\\
{\tt scale01.m}\\
{\tt Smu\_wavelet\_oper.m}\\
{\tt Smu.m}\\
{\tt wavetrans2D\_inv.m}\\
{\tt wavetrans2D.m}\\
{\tt wavetrans2Donce\_inv.m}\\
{\tt wavetrans2Donce.m }\\
from the course website. They can be used to solve the sparsity-promoting variational regularization problem
\begin{equation}\label{variationalreg}
 \mathbf{f}_\mu=\argmin_{\mathbf{f}\in\R^n}\left\{ \|\mathbf{A}\mathbf{f}-\widetilde{\mathbf{m}}\|_2^2 + \mu \sum_{\nu=1}^n |(W\mathbf{f})_\nu|\right\},
\end{equation}
where $W\mathbf{f}\in\R^n$ denotes the wavelet coefficients of $\mathbf{f}$ organized as a vertical vector.
\begin{itemize}
\item[(a)] Use the Matlab routines available at the course website to simulate parallel-beam tomographic data with projection angles (in degrees) 
\begin{eqnarray*}
&&
0^\circ, 13^\circ, 24^\circ, 31^\circ, 35^\circ, 48^\circ, 55^\circ, 70^\circ, 82^\circ, 97^\circ,  \\
&&
105^\circ, 110^\circ, 120^\circ, 130^\circ, 140^\circ, 150^\circ, 160^\circ, 169^\circ, 178^\circ.
\end{eqnarray*}
Simulate the data for a $128{\times}128$ image; avoid inverse crime by computing at higher resolution and downsampling. The target is the custom-made {\tt SqPhantom.m} rectangle image we designed together. 
\item[(b)] Compute the Haar wavelet sparsity of the {\tt SqPhantom.m} rectangle image (use $D=5$ in the transform) at resolution $128{\times}128$.  In other words, find out how many of the $128^2=16384$ wavelet coefficients are significantly different from zero.
\item[(c)] Use the S-curve method described in the article \\
\href{http://www.siltanen-research.net/publ/HamalainenKallonenKolehmainenLassasNiinimakiSiltanen2013.pdf}{\tiny http://www.siltanen-research.net/publ/HamalainenKallonenKolehmainenLassasNiinimakiSiltanen2013.pdf}\\
to choose the regularization parameter $\mu$. Summarizing, compute the reconstruction by solving (\ref{variationalreg}) for a variety of values of $\mu>0$, calculate the number of nonzero wavelet coefficients in each reconstruction, and find the $\mu$ value that leads to approximately the same number of nonzero wavelet coefficients you computed in (b).
\end{itemize}


\end{enumerate}
\end{document}



