  Propagation of high-frequency wave in periodic media is a challenging problem
due to the existence of multiscale characterized by short wavelength, small
lattice constant and large physical domain size. Conventional computational
methods lead to extremely expensive costs, especially in high dimensions. In
this paper, based on Bloch decomposition and asymptotic analysis in the phase
space, we derive the frozen Gaussian approximation for high-frequency wave
propagation in periodic media and establish its converge to the true solution.
The formulation leads to efficient numerical algorithms, which are presented in
a companion paper [Delgadillo, Lu and Yang, arXiv:1509.05552].
