In recent years, the application of tensor-based methods to high-dimensional data has gained considerable attention, particularly for tasks involving denoising, classification, and compression of complex data structures such as hyperspectral images. This thesis presents novel approaches to enhance Tensor Robust Principal Component Analysis (TRPCA), addressing challenges such as computational efficiency, noise removal, and real-time processing. Firstly, the thesis presents a new online robust principal component analysis (RPCA) algorithm that recursively decomposes incoming data into low-rank and sparse components. Unlike traditional approaches that operate on data vectors, this method preserves the multi-dimensional structure of data, such as video frames. Secondly, the thesis proposes a randomized blocked algorithm for tensor singular-value thresholding (T-SVT), aimed at reducing the computational demands of TRPCA when applied to noisy hyperspectral images. The proposed randomized blocked algorithm incrementally finds the singular values until they fall below the threshold, leveraging compression achieved by the fast Fourier transform (FFT) to accelerate TRPCA significantly. Finally, the tensor-robust CUR (TRCUR) method is introduced for hyperspectral data compression and denoising. This method heavily downsamples the input hyperspectral image to form small subtensors and performs TRPCA on these subtensors. The desired hyperspectral image is recovered by combining the low-rank solution of the subtensors using tensor CUR reconstruction. We provide theoretical guarantees showing that the desired low-rank tensor can be exactly recovered using our proposed TRCUR method. Numerical experiments demonstrate that our method is up to 14 times faster than performing TRPCA on the original input data, while maintaining the classification accuracy.