\section{THEORY}
Selecting reference velocities can be thought of as a non-linear
problem.
Choosing a reference velocity to use at a given location is a function
of which reference velocity is actually closest to the given velocity,
which makes posing the problem in a traditional linear framework
difficult.
When compressing signals, electrical engineers face a similar problem.
They try to describe a signal with as few bytes as possible.
To do this they develop a codebook. Each member of the codebook
represents a region described by a single value. 

\section{Lloyd's Method}

Lloyd's method
attempts to find the best codebook by a simple iterative procedure.
Lloyd's method starts from a given initial codebook, then  it
follows a fairly simple algorithm:
\begin{description}
\item  [1] Find the nearest centroid for all points breaking up the points into cells.
\item [2]  Recalculate the centroids for each cell.
\item [3] Remove any empty cells.
\end{description}
Steps {\bf 1-3} are repeated until the solution no longer changes significantly.
\sideplot{ref}{width=3.2in}{
In step 1, the data is dividing into cells. In step2, the centroid
of each cell is calculated. In the third step new cell boundaries
are calculated between the centroids. If a cell contains no
points, the cell is removed.}
\par
Lloyd's method can be effective but relies on a good initial
codebook and can get stuck in local minima.   To avoid prejudicing the solution
the initial model is often a random set of vectors. To solve the second
problem, several methods have been developed \cite{linde}.
These methods often rely on replacing  empty cell by
splitting regions with high variance.
\subsection{Selecting reference velocities}
Lloyd's methods translate fairly easily for a
reference velocity selection problem.
The  values become velocities, the centroids become the reference velocities, and the
cells are regions with the  same reference velocity.
For selecting the initial reference velocities, I used evenly spaced
quantiles of the velocity.
At early iterations I replace step {\bf 3} of Lloyd's method
by something a bit more complex.
\begin{description}
\item [3a] Remove cells  whose  centroids are closer than a certain percentage from its neighbors (typically 3-8\%).
\item [3b] Remove cells with fewer than  a given number of points (typically 1-3\%).
\item [3c]  Given the removed points in steps 3a and 3b, find the regions
with the highest variance that are a given distance away from its neighbors.
If no regions meeting these criteria are found, remove them.
\end{description}
The purpose of modifying Lloyd's method is to attempt to avoid  local
minima. 
Regions whose centroid are close to its neighbor, or  are sparsely
populated, are replaced by splitting up regions that seem to be least accurately
described by their current centroid.
