Background subtraction (BS) is a very important task for various computer vision applications. Higher-Order Robust Principal Component Analysis (HORPCA) based robust tensor recovery or decomposition provides a very nice potential for BS. The BG sequence is then modeled by underlying low-dimensional subspace called low-rank while the sparse tensor constitutes the foreground (FG) mask. However, traditional tensor based decomposition methods are sensitive to outliers and due to the batch optimization methods, high dimensional data should be processed. As a result, huge memory usage and computational issues arise in earlier approaches which are not desirable for real-time systems. In order to tackle these challenges, we apply the idea of stochastic optimization on tensor for robust low-rank and sparse error separation. Only one sample per time instance is processed from each unfolding matrices of tensor in our scheme to separate the low-rank and sparse component and update the low dimensional basis when a new sample is revealed. This iterative multi-dimensional tensor data optimization scheme for decomposition is independent of the number of samples and hence it reduces the memory and computational complexities. Experimental evaluations on both synthetic and real-world datasets demonstrate the robustness and comparative performance of our approach as compared to its batch counterpart without sacrificing the online processing.