\documentclass[landscape,12pt]{article}
\newcommand{\bmat}{\left[ \begin{array}}
\newcommand{\emat}{\end{array} \right]}
% \newcommand{\pFq} {^{\phantom{\alpha}}_pF_q^\alpha}
\newcommand{\pFq} {_pF_q}
\newcommand{\chk} {\resizebox{0.5in}{0.5in}{\includegraphics*{check.pdf}}}

\pagestyle{empty}
% \newcommand{\ignore}[1]{}
\newcommand{\IGNORE}[1]{}
\newcommand{\ignore}[1]{#1}
\newcommand{\bits}{{\rm \# bits}}
\newcommand{\size}{{\rm size}}
\newcommand{\diag}{{\rm diag}}
% \newcommand{\det}{{\rm det}}
\usepackage{color}
\usepackage{graphics}
\usepackage{amsmath,amssymb}
% \usepackage{lscape}
% \input{psfig.sty}

\pdfpagewidth 11in
\pdfpageheight 8.5in
\topmargin 0in
\headheight 0in
\headsep 0in


\textwidth10in
\oddsidemargin -0.5in
%\evensidemargin-0.5in
\textheight9.5in
\topmargin-1in


\newcommand{\cond}{{\rm cond}}
\newcommand{\tb}{\textcolor{blue}}
\newcommand{\tr}{\textcolor{red}}
% \newcommand{\det}{{\rm det}}


\newcommand{\slide}[1]
{
\newpage
\begin{center}
\phantom{X} \vskip0.2in
{\huge\bf #1}
\end{center}
\hrule
\bigskip
}


\begin{document}

\boldmath

\LARGE\bf

%-----------------------------------------------------------
\begin{center}

\centerline{\resizebox{11.5in}{!}{\includegraphics*{MIT3.jpg}}}
\vskip-6.8in

{\huge\bf Computing the Hypergeometric Function
\\
\medskip

of a Matrix Argument}
\bigskip

\end{center}

\bigskip
\bigskip

\hrule
\bigskip
\bigskip
\bigskip
\bigskip
\bigskip
\bigskip

{\LARGE \bf
\begin{center}
Plamen Koev \\
{\Large Massachusetts Institute of Technology }


\vspace*{.5in}

%\vspace*{1in}

{\rm \Large \bf Joint work with Alan Edelman}

\vspace*{1in}
\verb+http://math.mit.edu/~plamen+

\end{center}
}



\def\boxtext#1{%
\vbox{%
\hrule
\hbox{\strut \vrule{} #1 \vrule}%
\hrule
}%
}



%\mathversion{bold}
{%\sffamily

\LARGE\bf



%-----------------------------------------------------------

\slide{Why $\pFq(\cdot,\cdot,X)$?}

\begin{itemize}

\item Distributions of 
$$
\lambda_{\min}, \lambda_{\max}, \det, \mbox{ etc.}
$$
of 

\smallskip

\centerline{Wishart, Jacobi, Laguerre}

\medskip

expressed in terms of $\pFq(\cdot,\cdot,X)$

\item The distributions useful in:

\begin{itemize}
\item Hypothesis testing (e.g., $\Sigma=I$, etc.)
\item Parameter estimation: $A\sim W_m(n,\sigma^2I),\quad \sigma=?$
\end{itemize}


\item Applications in:
\begin{itemize}
\item  Population classification
\item  Automatic target classification
\item  Wireless communications
\end{itemize}

\item Computing $\pFq(\cdot,\cdot,X)$: 40-year-old open problem

\begin{itemize}
\item Notorious complexity and slow convergence


\item Empirical methods inefficient





\end{itemize}
\end{itemize}


% ---------------------------------------------------------------


\slide{Distribution of $\lambda_{\max}$ of $4\times 4$ Wishart with 7 DOF, 
$\Sigma=I$}

\bigskip

\centerline{\resizebox{8in}{5in}{\includegraphics*{maxeigwisharti.pdf}}}

\vskip0.3in

\begin{itemize}

\item \tb{Exact} vs Empirical with 20,000 replications

\end{itemize}




%-----------------------------------------------------------
\slide{James 1964}

If $A\sim W_n(m,\Sigma)$ then

\begin{eqnarray*}
P(\lambda_{\max}(A)<x)&\sim&
x^{\frac{m}{2}} \cdot 
     \tr{
     _1F_1\left(
     {\textstyle\frac{m}{2}};{\textstyle\frac{n+m+1}{2}};
     -{\textstyle\frac{1}{2}} x\Sigma^{-1}\right)}
\\
\\
\\
&=&
x^{\frac{m}{2}} \cdot 
     \sum_{k=0}^{\tr{\infty}}\sum_{\kappa\vdash k} p_\kappa \cdot x^k 
\cdot 
\tr{C_\kappa(\Sigma^{-1})}
\end{eqnarray*}


\vskip0.5in

\begin{itemize}



\item Slow convergence $\Rightarrow\quad \tr\infty \sim 50, 100, 150$ 

\item \tr{$C_\kappa(X)$} -- {\em Zonal Polynomial} -- \tr{Really hard: 
$O(n^m)$ 
terms in each!}

\item \tb{Our Contribution: $O(n)$}

\item Impossible until now
\begin{itemize}
\item Previous best algorithm ($n=5$): \hskip0.5in\tr{8 days}

{\large (Guti{\'e}rrez, Rodriguez, S{\'a}ez, 2000)}

\item New algorithm: \hskip2.8in\tb{$\frac{1}{100}$ second}


\end{itemize}
\end{itemize}


% ------------------------------------------------------------

\slide{Automatic 3D Target Classification}

{\large
\begin{center}
\begin{tabular}{cccccc}
\resizebox{1.5in}{!}{\includegraphics*{Tank-Blazer.jpg}} &
\resizebox{1.5in}{!}{\includegraphics*{Tank-hmmwv-2.jpg}} &
\resizebox{1.5in}{!}{\includegraphics*{Tank-M1-A1_Abrams2.jpg}} &
\resizebox{1.5in}{!}{\includegraphics*{Tank-Leopard.jpg}}     &
\resizebox{1.5in}{!}{\includegraphics*{Tank-T62-2.jpg}}    &
\resizebox{1.5in}{!}{\includegraphics*{TankBritishChallenger2.jpg}}\\
Blazer  & HMMWV & M1 A1 Abrams &
 Leopard & T62 & Challenger
 \\
 \\
 $X_1$ & $X_2$ & $X_3$ & $X_4$ & $X_5$ & $X_6$
\end{tabular}
\end{center}
}

\vskip0.5in


\begin{itemize}

\item $X_i$ --- $n\times 3$ matrices (given data)

\item Observation: $X= (X_i+E)Q, \quad\quad e_{ij}\sim N(0,\sigma^2)$

\item $X^TX$ --- noncentral Wishart, eigs do not depend on $Q$

\item Question: \tb{$i=?$}
\vskip0.3in

$$
L(i|X)\sim \mbox{}_1F_0(\cdot;X^TX)
$$

\vskip0.3in

\item Reference: Michael Jeffris (MITRE), Proceedings of SPIE 2005
\end{itemize}

%-----------------------------------------------------------
\slide{Computing $\pFq(\cdot;\cdot;X)$}

\begin{eqnarray*}
P(\lambda_{\max}(A)<x)&\sim&
x^{\frac{m}{2}} \cdot 
     \tr{
     _1F_1\left(
     {\textstyle\frac{m}{2}};{\textstyle\frac{n+m+1}{2}};
     -{\textstyle\frac{1}{2}} x\Sigma^{-1}\right)}
\\
&=&
x^{\frac{m}{2}} \cdot 
     \sum_{k=0}^{\tr{\infty}}\sum_{\kappa\vdash k} p_\kappa \cdot x^k 
\cdot 
\tr{C_\kappa(\Sigma^{-1})}
\end{eqnarray*}
\begin{itemize}

\item Means computing zonal polynomials $C_\kappa(\Sigma^{-1})$

\item $C_\kappa(\Sigma^{-1})$ depends only on the eigenvalues 
$x_1,x_2,\ldots,x_n$ 
of $\Sigma^{-1}$

\item Illustrate $\beta=2$ (complex); general $\beta$ analogous

\end{itemize}

%\vskip0.1in

\begin{center}
\begin{tabular}{ccc}
Partition $\kappa$& $C_\kappa$ & Number of terms \\
\hline
$(1)$ & $x_1+\cdots+x_n$ & $O(n)$ \\ \\
$(2)$ & $\displaystyle \sum_{i\le j} x_ix_j$ & $O(n^{\tr 2})$ \\ \\
$(1,1,1)$&$\displaystyle \sum_{i<j<k} x_ix_jx_k$ & $O(n^{\tr 3})$ \\  \\
$\kappa$ &  $\displaystyle \sum_T x^T$ & $O\left(n^{\tr{|\kappa|}}\right)$
\end{tabular}
\end{center}




%-----------------------------------------------------------
\slide{Computing $C_\kappa(X)$}

\centerline{\tb{IDEA: 
 $C_\kappa$ are $\chi(\mbox{GL}_n(\mathbb{C}));\quad\quad$
$\chi(\mbox{GL}_{n-1}(\mathbb{C}))$ induce 
$\chi(\mbox{GL}_n(\mathbb{C}))$}}

\bigskip
\bigskip
 Example:
\begin{eqnarray*}
C_{(1,1)}(X)&=&\sum_{i< j} x_ix_j \\
&=&
x_1 x_2 + (x_1+x_2) x_3 + \cdots + (x_1+\cdots+x_{n-1})x_n
\end{eqnarray*}

\medskip

Algorithm:
\begin{eqnarray*}
s_1&=&x_1 \\
s_2&=&s_1+x_2 \quad \quad \quad (=x_1+x_2)\\
s_3&=&s_2+x_3 \quad \quad \quad (=x_1+x_2+x_3)\\
& \vdots &\\
s_{n-1}&=&s_{n-2}+x_{n-1} \quad (=x_1+x_2+\cdots+ x_{n-1})\\
\\
C_{(1,1)}(X)&=& s_1 x_2 + s_2 x_3 +\cdots + s_{n-1} x_n
\end{eqnarray*}


\begin{itemize}
\item Cost: \tb{$O(n)$} versus \tr{$O(n^2)$}
\item In general: \tb{$O(n)$} versus \tr{$O(n^{|\kappa|})$}
\end{itemize}




\IGNORE{
%-----------------------------------------------------------
\slide{Performance}

\vskip0.2in

\centerline{\resizebox{7in}{!}{
\includegraphics*{performance-hyper.pdf}
}}


\begin{itemize}

\item Series truncated at $m=25$

\item Linear complexity in $n=$size$(X)$

\item ANSI C MEX function in MATLAB


\end{itemize}


%
%-----------------------------------------------------------
% Page 28
\newpage
\begin{center}
{\LARGE \bf EXAMPLE }
\end{center}
\hrule
\bigskip


%\centerline{\resizebox{10in}{6in}{
%\includegraphics*{pdfMinEigWishart.pdf}
%}}
}



%-----------------------------------------------------------
\slide{$A_p\sim W_p(n,I);\quad 
n/p=5; \quad(\lambda_{\max}(A_p)-\mu_p)/\sigma_p\rightarrow 
\mbox{TW}_1$}

\centerline{\resizebox{10in}{6in}{
\includegraphics*{sea06f2.pdf}
}}



%-----------------------------------------------------------
\slide{Jacobi:
$A_p\sim W_p(q,\Sigma),\; B_p\sim W_p(n,\Sigma), \, A_p-\lambda (A_p+B_p)$}
\centerline{\resizebox{10in}{6in}{
\includegraphics*{sea06f1.pdf}
}}
$$
p=4k+2,\; n/q=2,\; n/p=3,\;
\lambda_{\max}(A_pB_p^{-1})\rightarrow 
\lambda_{\max}(A_\infty B_\infty^{-1})\sim \mbox{TW}_1
$$



% -------------------------------------------------------------------
\slide{Future work}

\begin{itemize}

\item Incorporate the work of Johnstone, Richards, Chen, Tracy-Widom

\item New Cooley-Tukey-type algorithm:

\begin{itemize}

\item (DFT)$_{ij}$---characters of $\mathbb{Z}/n\mathbb{Z}
\quad\tr{\longleftrightarrow}\quad
C_\lambda$---characters of GL$_n(\mathbb{C})$

\item Main identity
$$
C_\kappa(x_1,x_2,\ldots,x_n)=\sum_{\lambda<\kappa}
C_\lambda(x_1,x_2,\ldots,x_{n-1})
\cdot x_n^{|\kappa|-|\lambda|} \cdot f_{\lambda\kappa}^{\alpha}
$$
In matrix form:
$$\mathcal{C}_n=\mathcal{C}_{n-1}\cdot Y_n(x_n)$$
where for example
$$
Y_2(x)=\bmat{cccc|cccc|cccc|cccc}
1 &x  & x^2 & x^3 &&&&&&&&&&&\\
  & 1 & x  & x^2 & x & x^2 & x^3 & x^4&&&&&&&\\
  &   & 1  & x   &   & x & x^2 & x^3& x^2&x^3&x^4&x^5&&&&\\
&&  & 1 &  & &x&x^2 & & x & x^2 & x^3 & x^3 &x^4&x^5& x^6
\emat
$$

\item $Y_n$ structured ... MVM takes \tb{linear} time

\item Cost(New Alg) $ \approx \sqrt{\mbox{Cost(Current Alg)}}\quad$ ... 
just like FFT

\end{itemize}
\end{itemize}




}
\end{document}
