  We consider the fundamental problem of maximizing a general quadratic
function over an ellipsoidal domain, also known as the trust region problem. We
give the first provable linear-time (in the number of non-zero entries of the
input) algorithm for approximately solving this problem. Specifically, our
algorithm returns an $\epsilon$-approximate solution in time
$\tilde{O}(N/\sqrt{\epsilon})$, where $N$ is the number of non-zero entries in
the input. This matches the runtime of Nesterov's accelerated gradient descent,
suitable for the special case in which the quadratic function is concave, and
the runtime of the Lanczos method which is applicable when the problem is
purely quadratic.
