Conventional sampling theory is dictated by Shannon's celebrated sampling theorem: For a signal to be reconstructed from samples, it must be sampled with at least twice the maximum frequency found in the signal. This principle is key in all modern signal acquisition, from consumer electronics to medical imaging devices. Recently, a new theory of signal acquisition has emerged in the form of Compressed Sensing, which allows for complete conservation of the information in a signal using far fewer samples than Shannon's theorem dictates. This is achieved by noting that signals with information are usually structured, allowing them to be represented with very few coefficients in the proper basis, a property called sparsity. In this thesis, we survey the existing theory of compressed sensing, with details on performance guarantees in terms of the Restricted Isometry Property. We then survey the state-of-the-art applications of the theory, including improved MRI using Total Variation sparsity and restoration of seismic data using curvelet and wave atom sparsity. We apply Compressed Sensing to the problem of finding statistical properties of a signal based CS methods, by attempting to measure the Hurst exponent of rough surfaces by partial measurements. We suggest an improvement on previous results in seismic data restoration, by applying a learned dictionary of signal patches for restoration.