Fiber Bragg Gratings (FBG) are often used as the key element for dynamic Optical Fiber Sensors (OFS). The relatively high backscatter energy of the FBGs is modulated by changes at the vicinity of the fiber. Changes such as temperature and strain are monitored in the reflection’s phase and/or frequency with high precision. However, these system’s sensitivity and spatial resolution are limited by optical parameters. For example, in an Optical Time Domain Reflectometry (OTDR) system, the interrogating optical pulse’s width defines the system’s spatial resolution, while the pulse’s power defines its sensitivity. While the spatial resolution can be increased by shortening the pulse width, the sensor’s sensitivity will deteriorate due to decreased optical power. An interesting observation of the FBG’s profile, with k-FBGs imprinted along it, is its approximation to a k-sparse signal. An ideal k-sparse signal has k non-zero elements. This assumption is reasoned in the fiber profile due to the high ratio between the Rayleigh and the FBGs back scattered light. To increase sensitivity and spatial resolution we propose the use of the Iterative Soft Thresholding Algorithm (ISTA) to reconstruct the sparse fiber profile. This algorithm is known for its remarkable results in image denoising by reconstructing the sparse data. In this paper, dynamic OFS experiments with a 1kHz strain perturbation are shown to have improved SNR by 10.5dB and spatial resolution improved by 30m to 2m with a 300ns interrogating pulse width.