  Gaussian Processes (GPs) are highly expressive, probabilistic models. A major
limitation is their computational complexity. Naively, exact GP inference
requires $\mathcal{O}(N^3)$ computations with $N$ denoting the number of
modeled points. Current approaches to overcome this limitation either rely on
sparse, structured or stochastic representations of data or kernel respectively
and usually involve nested optimizations to evaluate a GP. We present a new,
generative method named Iterative Charted Refinement (ICR) to model GPs on
nearly arbitrarily spaced points in $\mathcal{O}(N)$ time for decaying kernels
without nested optimizations. ICR represents long- as well as short-range
correlations by combining views of the modeled locations at varying resolutions
with a user-provided coordinate chart. In our experiment with points whose
spacings vary over two orders of magnitude, ICR's accuracy is comparable to
state-of-the-art GP methods. ICR outperforms existing methods in terms of
computational speed by one order of magnitude on the CPU and GPU and has
already been successfully applied to model a GP with $122$ billion parameters.
