The Active Appearance Model (AAM) algorithm is a powerful tool for modeling images of deformable objects. AAM combines a subspace-based deformable model of an object?s appearance with a fast and robust method of fitting this model to a previously unseen image. The speed of this algorithm comes from the assumption that the gradient matrix is fixed around the optimal coefficients for all images. In this paper, we propose a novel convergence scheme for AAM that adapts this gradient matrix to the target image?s texture during convergence by adding linear modes of change that are based on the texture eigenvectors of AAM. We show that this adaptive strategy for the gradient matrix provides a significant increase in the performance of the AAM algorithm.