Radio maps are important enablers for many applications in wireless networks, ranging from network planning and optimization to fingerprint based localization. Sampling the complete map is prohibitively expensive in practice, so methods for reconstructing the complete map from a subset of measurements are increasingly gaining attention in the literature. In this paper, we propose two algorithms for this purpose, which build on existing approaches that aim at minimizing the tensor rank while additionally enforcing smoothness of the radio map. Experimental results with synthetic measurements derived via ray tracing show that our algorithms outperform state of the art techniques.