\documentclass{article}

% Packages required to support encoding
\usepackage{ucs}
\usepackage[utf8x]{inputenc}

% Packages required by code


% Packages always used
\usepackage{hyperref}
\usepackage{xspace}
\usepackage[usenames,dvipsnames]{color}
\hypersetup{colorlinks=true,urlcolor=blue}

\input{homework.tex}


\begin{document} 
\hypertarget{homework_2_1}{}\section*{{Homework 2}}\label{homework_2_1}

Please answer the following questions in complete sentences in a typed manuscript and submit the solution to me in class on January 31th, 2012.

In this homework, we probe a bit of theory around the topics we'{}ve covered in class so far. The goal is not to provide tedious work, but useful results that'{}ll rely upon later. For instance, the first problem tackles subspaces and null-spaces, which will frequently arise in our discussion of constrained optimization. The second problem asks you use the tools in class to discuss a variation on least squares that often arises in many applications. The third problem deals with convexity of a subspace in relationship to the constrained least squares problem. Finally, the fourth problem shows a different way of looking at a least squares problem.

\hypertarget{problem_1_constrained_least_squares_theory_2}{}\subsection*{{Problem 1: Constrained least squares theory}}\label{problem_1_constrained_least_squares_theory_2}

Let $A \in \RR^{m \times n}$ and $B \in \RR^{p \times n}$. Consider the constrainted least squares problem:

\begin{displaymath}
\MINone{}{\| \vb - \mA \vx\|}{\mB \vx = \vd}.
\end{displaymath}
\begin{enumerate}%
\item Show that $\text{rank}(\bmat{A \\ B}) = n$ is equivalent to the condition that the intersection between the null-spaces of $A$ and $B$ only has the trivial vector $\vx = 0$.


\item Show that the problem may not have any solution if $\text{rank}(\mB) < p$.


\item Show that the problem always has a unique solution, for any $\vd$, when $\text{rank}(\mB) = p$ and $\text{rank}(\bmat{A \\ B}) = n$.


\item Show that if the problem has a unique solution, for any $\vd$, then $\text{rank}(\bmat{A \\ B}) = n$. (You can combine this with the proof of the last one if you wish.)



\end{enumerate}
\hypertarget{problem_2_ridge_regression_3}{}\subsection*{{Problem 2: Ridge Regression}}\label{problem_2_ridge_regression_3}

The Ridge Regression problem is a variant of least squares:

\begin{displaymath}
\MIN{}{\| \vb - \mA \vx\|_2^2 + \lambda \| \vx\|_2^2. }
\end{displaymath}
This is also known as Tikhonov regularization.

\begin{enumerate}%
\item Show that this problem always has a unique solution, for \emph{any $\mA$} if $\lambda > 0$, using the theory discussed in class so far.

\end{enumerate}
This property is one aspect of the reason that Ridge Regression and used. It is also a common regularization method that can help avoid overfitting in a regression problem.

\begin{enumerate}%
\item Use the SVD of $\mA$ to characterize the solution as a function of $\lambda$.


\item What is the solution when $\lambda \to \infty$?\newline What is the solution when $\lambda \to 0$.



\end{enumerate}
\hypertarget{problem_3_convexity_4}{}\subsection*{{Problem 3: Convexity}}\label{problem_3_convexity_4}

\begin{enumerate}%
\item Show that $f(x) = \| \vb - \mA \vx \|$ is a convex function. Feel free to use the result proved on the last homework.


\item Show that the null-space of a matrix is a convex set.


\item Explain why these results allow us to conclude that constrained least squares is a convex optimization problem. (See Wikipedia for the definition of a convex problem.)



\end{enumerate}
\hypertarget{problem_4_alternate_formulations_of_least_squares_5}{}\subsection*{{Problem 4: Alternate formulations of Least Squares}}\label{problem_4_alternate_formulations_of_least_squares_5}

Consider the constrained least squares problem:

\begin{displaymath}
\MINone{\vr,\vy}{ \| \vr \|_2 } { \vr = \vb - \mC\vy }
\end{displaymath}
where $\mC \in \RR^{m \times n}$, $n \le m$ and rank $n$.

\begin{enumerate}%
\item Convert this problem into into the standard constrained least squares form.


\item Form the augmented system from the Lagrangian as we did in class.


\item Manipulate this problem to arrive at the normal equations for a least-squares problem: $\mC^T \mC \vy = \mC^T \vb$.\newline Discuss any advantages of the systems at intermediate steps.



\end{enumerate}

\end{document}
