  In this paper, we propose a novel Anderson's acceleration method to solve
nonlinear equations, which does \emph{not} require a restart strategy to
achieve numerical stability. We propose the greedy and random versions of our
algorithm. Specifically, the greedy version selects the direction to maximize a
certain measure of progress for approximating the current Jacobian matrix. In
contrast, the random version chooses the random Gaussian vector as the
direction to update the approximate Jacobian. Furthermore, our algorithm,
including both greedy and random versions, has an $n$-step super quadratic
convergence rate, where $n$ is the dimension of the objective problem. For
example, the explicit convergence rate of the random version can be presented
as $ \norm{\vx_{k+n+1} - \vx_*} / \norm{\vx_k- \vx_*}^2 =
\cO\left(\left(1-\frac{1}{n}\right)^{kn}\right)$ for any $k\geq 0$ where
$\vx_*$ is the optimum of the objective problem. This kind of convergence rate
is new to Anderson's acceleration and quasi-Newton methods. The experiments
also validate the fast convergence rate of our algorithm.
