\documentclass[11pt]{article} 

\usepackage{verbatim}
\usepackage{amsmath,amsfonts}
\usepackage[mathscr]{eucal}
\usepackage{amssymb,amsmath}
\usepackage{latexsym}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{amsthm}



\newcommand {\C}{\mathbb {C}}
\newcommand {\R}{\mathbb {R}}
\newcommand {\T}{\mathbb {T}}
\newcommand {\D}{\mathcal {D}}
\newcommand {\I}{\mathcal {I}}
\newcommand {\G}{\mathcal {G}}
\newcommand {\N}{\mathcal {N}}
\newcommand {\Z}{\mathbb {Z}}

\topmargin=-0.5in
\textheight=9.0in 

\oddsidemargin=-0.05in
\textwidth=6.25in 

\begin{document} 


\noindent{\bf Math 273} \ \ \ \ \ {\bf Homework \#4} \ \ \ \ \ Due on Friday, March 22nd 

\noindent (you can leave your homework in my mailbox, under the door at my office MS 7620-D, or 
with Babette Dalton at MS 7619 before 3pm every day, or you can send it by email). 

\medbreak

 \noindent{\bf [1]} Let $V$ be a real vector space and $F:V\rightarrow \overline{\R}$ be a convex 
function, thus for every $u,v\in V$, we 
have $F(\lambda u+(1-\lambda)v)\leq \lambda F(u)+(1-\lambda)F(v)$, $\forall\lambda\in [0,1]$, 
whenever the RHS is defined (the RHS is not defined when $F(u)=-F(v)=+\infty$ or 
$F(u)=-F(v)=-\infty$).

(a) If $F$ is convex, show that for every $u_1,...,u_n$ of points of $V$ and for every family 
$\lambda_1,...,\lambda_n$, $\lambda_i\geq0$, $\sum_{i=1}^n\lambda_i=1$, we have
$$F(\sum_{i=1}^n\lambda_i u_i)\leq\sum_{i=1}^n\lambda_iF(u_i).$$

(b) If $F:V\rightarrow \overline{\R}$ is convex, show that the sets $\{u:\ F(u)\leq a\}$ and 
$\{u: \ F(u)<a\}$ are convex sets. Show that the converse is not true.

\medbreak

\noindent{\bf [2]} The {\it epigraph} of a function $F:V\rightarrow \R$ is the set
$$\mbox{epi}F=\{(u,a)\in V\times \R|\ f(u)\leq a\},$$
where $V$ is a Banach space.
Show that the function $F$ is convex if and only if its epigraph is convex.

\medbreak 

\noindent{\bf [3]} Assume that $V$ and $V^*$ are normed vector spaces in duality. Let
$F:V\rightarrow \overline{\R}$ and let $F^*:V^*\rightarrow \overline{\R}$ be the polar or 
conjugate of $F$. We define $F^*$ by
$$F^*(u^*)=\sup_{u\in V}\Big\{\langle u^*,u\rangle-F(u)\Big\},$$
where $\langle u^*,u\rangle = u^*(u)$. 

Show

(i) $F^*(0)=-inf _{u\in V} F(u)$.

(ii) $(\lambda F)^*(u^*)=\lambda F^*(\frac{1}{\lambda}u^*)$ for every $\lambda >0$.

\medbreak

\noindent{\bf [4]} Let $V=V^*=\R^n$. Let $Q$ be a symmetric positive definite $n\times n$ matrix, 
$b\in\R^n$, and consider $f(x):=\frac{1}{2}\langle x,Qx\rangle+\langle b,x\rangle$, for all 
$x\in\R^n$. Find the polar (or the conjugate) $f^*$ and deduce that, in particular, 
$\frac{1}{2}\|\cdot\|^2$ is its own polar (or conjugate).

\medbreak

\noindent{\bf [5]} Let $F:V\rightarrow \R$ and $F^*$ its polar. Then $u^*\in \partial F(u)$ if and only if $F(u)+F^*(u^*)=\langle u^*,u\rangle$.

\medbreak

\noindent{\bf [6]} Show that the polar $F^*$ is convex.

\medbreak

\noindent{\bf [7]} Let $f\in \R^{N^2}$ be given, and let $u\in\R^{N^2}$ be an unknown minimizer 
of the functional (already seen before)
$$E(w)=\sum_{i,j=0}^{N-1}|\nabla w_{i,j}|^2+\lambda \sum_{i,j=0}^{N-1}(w_{i,j}-f_{i,j})^2,$$
for $w\in \R^{N^2}$, where
$$\nabla w_{i,j}=\left(                                                                                                                                                                                                        
\begin{array}{cc}                                                                                                                                                                                                              
(D_xw)_{i,j}\\                                                                                                                                                                                                                 
(D_yw)_{i,j}                                                                                                                                                                                                                   
\end{array}                                                                                                                                                                                                                    
\right)=                                                                                                                                                                                                                       
\left(                                                                                                                                                                                                                         
\begin{array}{cc}                                                                                                                                                                                                              
w_{i+1,j}-w_{i,j}\\                                                                                                                                                                                                            
w_{i,j+1}-w_{i,j}                                                                                                                                                                                                              
\end{array}                                                                                                                                                                                                                    
\right),                                                                                                                                                                                                                       
$$
for $(i,j)\in \{0,...,N-1\}^2$ (we assume that all vectors $f$, $u$, $w$ are periodic outside of their support).

(a) Find the adjoint operators $D_x^*$ and $D^*_y$ of $D_x$ and $D_y$.

(b) Find a linear operator $B:\R^{N^2}\rightarrow\R^{N^2}$, a $c\in \R^{N^2}$, and $C(f)$, independent of $w$, such that for all $w\in \R^{N^2}$,
$$E(w)=\langle Bw,w\rangle+\langle c,w\rangle+C(f).$$

(c) Show that $B$ is self-adjoint.

(d) Find the Gateaux differential of $E(w)$ in the direction $v$ and thus give a necessary (and sufficient) condition for $u$ to be a minimizer, by setting this differential to zero (as the zero functional).

\bigbreak

\noindent{\bf Optional Problems}

\medbreak

\noindent{\bf [1]} Note that a function $F:V\mapsto \overline{\R}$, with $V$ a normed vector space, is lower semi-continuous (l.s.c.) on $V$ by the equivalent definition:
$$\forall a\in \R: \ \ \Big\{u\in V| \ F(u)\leq a\Big\} \mbox{ is closed.}$$

Using this, show that $F$ is l.s.c. iff its epigraph is closed (hint: consider
 the function on $V\times \R$ defined by $f(u,a)=F(u)-a$).


\medbreak

\noindent{\bf [2]} Infimal convolution. Let $f_1$, . . . , $f_m$ be convex functions on $\R^n$. Their infimal convolution,
denoted $g = f_1 \circ ... \circ f_m$
(several other notations are also used), is defined as
$g(x) = \inf{f_1(x_1) + ... + f_m(x_m) | x_1 + ... + x_m = x}$,
with the natural domain (i.e., defined by $g(x) < \infty$).

(The name ``convolution'' presumably comes from the
observation that if we replace the sum above with the product, and the infimum above with integration, then we obtain the normal convolution.)

(a) Show that $g$ is convex.

(b) Show that $g^*= f_1^*+...+f_m^*$.

\medbreak

\noindent{\bf [3]} {\it Approximate total variation denoising.} Let $y\in \R^n$ be a given (corrupted, noisy) vector, $x\in \R^n$ is the denoised vector to be computed by minimizing the 1D-discrete TV function with data fidelity term:
$$f(x)=\|x-y\|^2_2 + \lambda \sum_{i=1}^{n-1}|x_{i+1}-x_i|.$$
We can make the second term twice differentiable using regularization:
$$TV(x)=\sum_{i=1}^{n-1}|x_{i+1}-x_i| \approx \sum_{i=1}^{n-1}\Big(\sqrt{\epsilon^2 +(x_{i+1}-x_i)^2}-\epsilon\Big),$$
where $\epsilon>0$ is a small parameter.
Apply gradient descent method and Newton's method for the minimization using the approximate formula for TV (simlar problem with the previous length minimization). Define a noisy vector $y$ as data.

\bigbreak

%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%

\end{document}
