Geodesic regression on images enables studies of brain development and degeneration, disease progression, and tumor growth. The high-dimensional nature of image data presents significant computational challenges for the current regression approaches and prohibits large scale studies. In this paper, we present a fast geodesic regression method that dramatically decreases the computational cost of the inference procedure while maintaining prediction accuracy. We employ an efficient low dimensional representation of diffeomorphic transformations derived from the image data and characterize the regressed trajectory in the space of diffeomorphisms by its initial conditions, i.e., an initial image template and an initial velocity field computed as a weighted average of pairwise diffeomorphic image registration results. This construction is achieved by using a first-order approximation of pairwise distances between images. We demonstrate the efficiency of our model on a set of 3D brain MRI scans from the OASIS dataset and show that it is dramatically faster than the state-of-the-art regression methods while producing equally good regression results on the large subject cohort.