We propose a graph signal processing framework to overcome the computational burden of Tensor Robust PCA (TRPCA). Our framework also serves as a convex alternative to graph regularized tensor factorization methods. Our method is based on projecting a tensor onto a lower-dimensional graph basis and benefits from significantly smaller SVDs as compared to TRPCA. Qualitative and computational experiments on several 2D and 3D tensors reveal that for the same reconstruction quality, our method attains up to 100 times speed-up on a low-rank and sparse decomposition application.