Missing data is a commonly encountered and challenging issue in data-driven process analysis. Several methods that attempt to estimate missing observations for the purpose of control, identification, etc. have been developed over the decades. However, existing methods tend to produce erroneous estimates when the percentage of missing data is high and mostly do not exploit the benefit of parsimonious or sparse signal representations. Recently developed compressed sensing (CS) techniques are naturally suited to handle the problem of missing data recovery since they provide powerful signal recovery methods that take advantage of sparse representations of signals in a set of functions, known as the overcomplete dictionary. A majority of these signal recovery algorithms assume that the dictionary is known beforehand. This paper presents a method to estimate missing observations using CS ideas, but with an adaptive learning of the overcomplete dictionary from data. The method is particularly devised for signals that have a block-diagonal sparse representation, an assumption that is not too restrictive. An iterative optimization method, consisting of an iterative CS problem on block-segmented data, for discovering this sparsifying dictionary is presented. Further, we present theoretical and practical guidelines for the segmentation size. It is shown that the error at each iteration is bounded for the exact, i.e., zero model mismatch and noise-free, case. Demonstrations on five different systems illustrate the efficacy of the proposed method with respect to recovery of missing data and convergence properties. Finally, the method is observed to require fewer observations than a fixed dictionary for a given reconstruction accuracy. (C) 2016 Elsevier Ltd. All rights reserved.