  We present a technique for model-based derivative-free optimization called
\emph{basis sketching}. Basis sketching consists of taking random sketches of
the Vandermonde matrix employed in constructing an interpolation model. This
randomization enables weakening the general requirement in model-based
derivative-free methods that interpolation sets contain a full-dimensional set
of affinely independent points in every iteration. Practically, this weakening
provides a theoretically justified means of avoiding potentially expensive
geometry improvement steps in many model-based derivative-free methods. We
demonstrate this practicality by extending the nonlinear least squares solver,
\texttt{POUNDers} to a variant that employs basis sketching and we observe
encouraging results on higher dimensional problems.
