medcouple: talk/talk.tex comparison

comparison talk/talk.tex @ 64:d5ec0659b26b

write last section

author	Jordi Gutiérrez Hermoso <jordigh@octave.org>
date	Tue, 17 May 2016 23:35:36 -0400
parents	73b369370665
children

comparison

equal deleted inserted replaced

-:bd102ae06bc4
+:d5ec0659b26b
 Pick the median.
 \end{frame}
 \begin{frame}{Computing the medcouple}
 \begin{overlayarea}{\textwidth}{8cm}
-\only<1>{%
+\only<1>{
 \begin{center}
 \pgfimage[height=2in]{img/naive/medc-computation-init.png}
 \end{center}
-Split up $X$ into $X^+$ and $X^-$ along the median.}
+Split up $X$ into $X^+$ and $X^-$ along the median.
-\only<2>{%
+}
+\only<2>{
 \begin{center}
 \pgfimage[height=2in]{img/naive/medc-computation.png}
 \end{center}
 Evaluate the kernel for all couples.
 \[
 \frac{ (x_i - x_m) - (x_m - x_j)}{x_i - x_j},
 \quad x_i \in X^+, \quad x_j \in X^-
-\]}
+\]
-\only<3>{%
+}
+\only<3>{
 \begin{center}
 \pgfimage[height=2in]{img/naive/medc-computation-done.png}
 \end{center}
-The median of this matrix is the medcouple.}
+The median of this matrix is the medcouple.
-\end{overlayarea}
+}
+\end{overlayarea}
+\end{frame}
+\begin{frame}
+Problem: this algorithm is $O(n^2)$!!
 \end{frame}
 \section{Computation of the Medcouple}
 \begin{frame}
-wtf
+Now pure CS:
+\pause
+\begin{problem}
+Find the median of a matrix with sorted rows and sorted columns.
+\end{problem}
+\end{frame}
+\begin{frame}
+\emph{Donald B. Johnson; Tetsuo Mizoguchi (May 1978). "Selecting The
+Kth Element In X + Y And X1 + X2 +...+ Xm". SIAM Journal of
+Computing 7 (2): 147-153. doi:10.1137/0207013.}
+\pause
+\begin{itemize}
+\item Old paper, hard to read. But cool ideas!
+\pause
+\item Paper generalises to $n$-dimensional array with sorted slices
+\end{itemize}
+\end{frame}
+\begin{frame}{Preliminaries}
+Helper algorithms:
+\pause
+\begin{description}
+\item[Selection Algorithm:] e.g. quickselect,
+\texttt{nth\_element} in C++ or \texttt{partition} in numpy, $O(n)$ time
+\pause
+\item[Weighted Median:] binary search using
+selection algorithm, $O(n)$ time.
+\end{description}
+\end{frame}
+\begin{frame}
+We now make two important observations
+\end{frame}
+\begin{frame}{Two observations}
+Compare against whole matrix in $O(n)$ time
+\begin{overlayarea}{\textwidth}{6cm}
+\only<1>{
+\begin{center}
+\pgfimage[width=2in]{img/kth-pair/greater-than}
+\end{center}
+Bottom-up.
+}
+\only<2>{
+\begin{center}
+\pgfimage[width=2in]{img/kth-pair/less-than}
+\end{center}
+Top-down.
+}
+\end{overlayarea}
+\end{frame}
+\begin{frame}{Two observations}
+Compare against half the matrix in $O(1)$ time
+\begin{center}
+\pgfimage[width=2in]{img/kth-pair/middle-of-middle}
+\end{center}
+\end{frame}
+\begin{frame}{Putting it together}
+Iteratively, we have bounds for the global median
+\begin{center}
+\pgfimage[width=2in]{img/kth-pair/row-medians}
+\end{center}
+\end{frame}
+\begin{frame}{Putting it together}
+If we align the row medians...
+\begin{center}
+\pgfimage[width=2in]{img/kth-pair/row-medians-aligned}
+\end{center}
+\end{frame}
+\begin{frame}{Putting it together}
+With the weighted median (in $O(n)$ time), we compare to at least half the
+remaining entries, discarding at least $1/4$.
+\begin{center}
+\pgfimage[width=2in]{img/kth-pair/row-medians-compared}
+\end{center}
+\end{frame}
+\begin{frame}
+So, final algorithm!
+\end{frame}
+\begin{frame}{Grand finale}
+Procedure (serves one medcouple)
+\begin{enumerate}
+\item Compute ingredients for medcouple matrix: $O(n \log n)$
+\pause
+\begin{enumerate}[(A)]
+\item \label{loop} Compute $t = \text{median of row medians}$: $O(n)$
+\pause
+\item \label{compare} Compare $t$ to the whole matrix: $O(n)$
+\pause
+\item Found the median? Found the medcouple! DONE.
+\pause
+\item \label{compare} Use comparison from \eqref{compare} to
+throw out entries.
+\pause
+\item More than $n$ entries remaining? LOOP TO \eqref{loop}.
+\end{enumerate}
+\pause
+\item Use selection algorithm on remaining entries: $O(n)$.
+\end{enumerate}
+\pause
+Step \eqref{compare} throws out at least $1/4$ of all entries, so
+the whole algorithm is $O(n \log n)$.
+\end{frame}
+\begin{frame}
+\begin{center}
+\LARGE{Questions?}
+\end{center}
 \end{frame}
 \end{document}

Mercurial > hg > medcouple

comparison talk/talk.tex @ 64:d5ec0659b26b