Springer International Publishing AG 2017. About a decade ago, a couple of groundbreaking articles revealed the possibility of faithfully recovering high-dimensional signals from some seemingly incomplete information about them. Perhaps more importantly, practical procedures to perform the recovery were also provided. These realizations had a tremendous impact in science and engineering. They gave rise to a field called compressive sensing, which is now in a mature state and whose foundations rely on an elegant mathematical theory. This survey presents an overview of the field, accentuating elements from approximation theory, but also highlighting connections with other disciplines that have enriched the theory, e.g., statistics, sampling theory, probability, optimization, metagenomics, graph theory, frame theory, and Banach space geometry.
