Streaming video completion is the practice that aims to fill in missing or corrupted pixels in a video stream by using past uncorrupted data. A method to tackle this problem is recently introduced called a Tensor Networked Kalman Filter (TNKF). It shows promising results in terms of performance compared to state-of-the-art methods for high percentages of missing pixels (≥ 95%). The main drawback of using a TNKF is the computational speed, which needs to be improved to compete with other existing methods and to be carried out in real-time by a regular computer. This work discusses three methods that reduce the computational load of the algorithm, which speeds up computations. The first method is replacing the existing algorithm with a Block Update TNKF. Secondly, the use of randomized rounding instead of deterministic rounding is investigated. The last method is the simplification of the TNKF update. Results that are presented in this report show that significant speedups of up to +132% can be achieved. In most situations, the considered speedup methods compromise the reconstruction’s accuracy. This thesis discusses the effects this has on the quality of the reconstruction.