A computer-implemented video completion method is proposed for reconstructing a sparsely sampled video comprising sparsely sampled video frames comprising sparse sets of picture element intensity values. The method comprises: distributing the sparse sets of picture element intensity values onto a video frame coordinate system; determining a window size based on a sampling rate used to sample the sparsely sampled video, a window defining a region covering a subset of picture element positions within a video frame; dividing the video frames into overlapping and/or non-overlapping windows; determining a video frame range for a respective window, the video frame range defining video frames to be used to reconstruct one or more missing picture element intensity values of the respective window; and determining the missing picture element intensity values of the respective window under reconstruction by using known picture element intensity values of spatially corresponding windows from the video frames defined by the video frame range.