Multi-modal sensing is increasingly becoming important in a number of applications, providing new capabilities and new processing challenges. In this paper we explore the benefit of combining of a low-resolution depth sensor with a high-resolution optical video sensor, in order to provide a highresolution depth map of the scene. We propose a new formulation that is able to incorporate temporal information and exploit the motion of objects in the video to significantly improve the results over existing methods. In particular, our approach exploits the space-time redundancy in the depth and intensity using motionadaptive low-rank regularization. We provide experiments to validate our approach and confirm that the quality of the estimated high-resolution depth is improved substantially. Our approach can be a first component in systems using vision techniques that rely on high resolution depth information.