This letter proposes a novel video compression method – stochastic adaptive Fourier decomposition (SAFD) based joint spatiotemporal model (JSTM). SAFD is a recently developed sparse representation theory that combines the traditional signal decomposition method with machine learning to adaptively decompose multi-signals into common atoms of predefined interpretable Szeg o¨ kernel dictionary. Based on SAFD, this letter firstly proposes a learning-based 3D video to 2D data embedding method. The method learns common atoms based on the frames themselves that require to be compressed, without the need for pre-training on large-scale data like deep learning. Then the embedding-based JSTM and a feasible video compression architecture are developed. The contribution is twofold: introducing SAFD into video compression first time in the literature and developing a new video compression model JSTM. The experimental results are promising.