Transformers are expensive to train due to the quadratic time and space\ncomplexity in the self-attention mechanism. On the other hand, although kernel\nmachines suffer from the same computation bottleneck in pairwise dot products,\nseveral approximation schemes have been successfully incorporated to\nconsiderably reduce their computational cost without sacrificing too much\naccuracy. In this work, we leverage the computation methods for kernel machines\nto alleviate the high computational cost and introduce Skyformer, which\nreplaces the softmax structure with a Gaussian kernel to stabilize the model\ntraining and adapts the Nystr\\"om method to a non-positive semidefinite matrix\nto accelerate the computation. We further conduct theoretical analysis by\nshowing that the matrix approximation error of our proposed method is small in\nthe spectral norm. Experiments on Long Range Arena benchmark show that the\nproposed method is sufficient in getting comparable or even better performance\nthan the full self-attention while requiring fewer computation resources.\n