\documentclass{article}
\usepackage{amsmath,amsfonts}
\usepackage{latexsym}
\usepackage{bbm}
\usepackage[pdftex]{graphicx}
\marginparwidth 0pt
\oddsidemargin 0pt
\evensidemargin 0pt
\marginparsep 0pt
\topmargin 0pt
\textwidth 6.0in
\textheight 8.5in
\begin{document}
\begin{center}
{\bf CSE252C -- Object Recognition -- Assignment \#2}\\
Instructor: Prof.\ Serge Belongie.\\
\verb+http://www-cse.ucsd.edu/classes/sp11/cse252c+\\
Target Due Date: Monday April.~25, 2011.
\end{center}
\begin{enumerate}
\item Dimensionality reduction on the MNIST database.
\begin{enumerate}
\item Generate a random projection matrix $G\in{\mathbb R}^{d'\times d}$ with entries $G_{ij}\sim {\mathcal N}(0,1/d')$. Use $d'=49$, which represents a factor of 16 smaller than the full dimensionality ($d=784$). Compute the mean squared difference between the entries of $G^\top G$ and a $d\times d$ identity matrix. It should be close to $1/d'$.
\item Compute the ROC curve as in Homework \#1 problem 3 using $L_2$ distances on $G\boldsymbol{x}^i$ in place of $\boldsymbol{x}^i$. How does the new EER compare to the old one?
\item Repeat the preceding step with a different dimensionality reduction method of your choice, keeping $d'$ fixed.
\end{enumerate}
\item Mahalanobis distance.
The {\em Mahalanobis distance} between $\boldsymbol{x}^i$ and $\boldsymbol{x}^j$ is given by $\Delta^2=(\boldsymbol{x}^i-\boldsymbol{x}^j)^\top\Sigma^{-1}(\boldsymbol{x}^i-\boldsymbol{x}^j)$, where $\Sigma$ is a $d\times d$ covariance matrix.
\begin{enumerate}
\item A covariance matrix $\Sigma$, by definition, is symmetric and positive definite, which means $\boldsymbol{a}^\top\Sigma \boldsymbol{a}>0$ for all $\boldsymbol{a}\in {\mathbb R}^d$. Show that a necessary and sufficient condition for $\Sigma$ to be positive definite is that all of its eigenvalues are positive.
\item $\Delta^2$ is equivalent to the squared Euclidean distance between $\boldsymbol{y}^i$ and $\boldsymbol{y}^j$, where $\boldsymbol{y}$ is a linearly transformed version of $\boldsymbol{x}$. What is that transformation?
\item Give an example of an application for which Mahalanobis distance is appropriate (e.g., compared to $L_2$ distance) and explain intuitively what $\Sigma^{-1}$ captures in this case.
\end{enumerate}
\item Properties of Chi Squared distance.
Recall that the $\chi^2$ distance is given by $\chi^2_{ij}=\frac{1}{2}\sum_{k=1}^d(x_k^i-x_k^j)^2/(x_k^i+x_k^j)$ where the $\boldsymbol{x}$'s are normalized histogram vectors. Prove or disprove the following statements:
\begin{enumerate}
\item $\chi^2_{ij}\in[0,1]$.
\item The matrix $Q\in {\mathbb R}^{n\times n}$ with entries $Q_{ij}=\sum_{k=1}^dx_k^ix_k^j/(x_k^i+x_k^j)$ is positive definite.
\item $\chi^2_{ij}$ is a metric.
\end{enumerate}
\item Gabor Functions.
The expression for the (unnormalized) isotropic 2D Gabor function is given by a Gaussian times a complex exponential
\[
h({\boldsymbol{x}})=e^{-\| {\boldsymbol{x}} \|^2/2\sigma^2}e^{j 2\pi {\boldsymbol{u}}_o^\top {\boldsymbol{x}}}
\]
where $\boldsymbol{x}=(x,y)^\top$ and $\boldsymbol{u}_o=(u_{o},v_{o})^\top$, and it
serves as an oriented bandpass filter. The even and odd Gabor
functions are equal to the real and imaginary parts of $h$,
respectively.
\begin{enumerate}
\item Compute four examples of even and/or odd 2D
Gabor functions on the interval $\boldsymbol{x}\in[-14,13]\times[-14,13]$
using parameters chosen in the following ranges: $\sigma\in[1,3]$ and
$\boldsymbol{u}_o\in[0,0.3]\times[0,0.3]$. For each example, display the function as an image and as a surface plot.
\item Apply the above set of filters to two different MNIST digits and display the results. Select a few of the filtered images to explain what the filter responses are responding to in the input images.
\end{enumerate}
\end{enumerate}
\end{document}