We study the computational complexity of Singular Spectrum Analysis and present a fast and memory efficient implementation that does not require building Hankel trajectory matrices. The key is to replace the singular value decomposition of Hankel matrices by a randomized QR decomposition. We also present a new strategy in which anti-diagonal averaging of the Hankel matrix is efficiently computed via convolution. The new algorithm significantly decreases the computational cost and memory requirement of Singular Spectrum Analysis data recovery. We test the effectiveness of the method through synthetic and real data examples.
展开▼
