  Score-based generative models (SGMs) synthesize new data samples from
Gaussian white noise by running a time-reversed Stochastic Differential
Equation (SDE) whose drift coefficient depends on some probabilistic score. The
discretization of such SDEs typically requires a large number of time steps and
hence a high computational cost. This is because of ill-conditioning properties
of the score that we analyze mathematically. We show that SGMs can be
considerably accelerated, by factorizing the data distribution into a product
of conditional probabilities of wavelet coefficients across scales. The
resulting Wavelet Score-based Generative Model (WSGM) synthesizes wavelet
coefficients with the same number of time steps at all scales, and its time
complexity therefore grows linearly with the image size. This is proved
mathematically over Gaussian distributions, and shown numerically over physical
processes at phase transition and natural image datasets.
