Depth map sensed by low-cost active sensor is often limited in resolution, whereas depth information achieved from structure from motion or sparse depth scanning techniques may result in a sparse point cloud. Achieving a high-resolution (HR) depth map from a low resolution (LR) depth map or densely reconstructing a sparse non-uniformly sampled depth map are fundamentally similar problems with different types of upsampling requirements. The first problem involves upsampling in a uniform grid, whereas the second type of problem requires an upsampling in a non-uniform grid. In this paper, we propose a new approach to address such issues in a unified framework, based on sparse representation. Unlike, most of the approaches of depth map restoration, our approach does not require an HR intensity image. Based on example depth maps, sub-dictionaries of exemplars are constructed, and are used to restore HR/dense depth map. In the case of uniform upsampling of LR depth map, an edge preserving constraint is used for preserving the discontinuity present in the depth map, and a pyramidal reconstruction strategy is applied in order to deal with higher upsampling factors. For upsampling of non-uniformly sampled sparse depth map, we compute the missing information in local patches from that from similar exemplars. Furthermore, we also suggest an alternative method of reconstructing dense depth map from very sparse non-uniformly sampled depth data by sequential cascading of uniform and non-uniform upsampling techniques. We provide a variety of qualitative and quantitative results to demonstrate the efficacy of our approach for depth map restoration.