Two-photon calcium imaging is an emerging experimental technique that enables the study of information processing within neural circuits in vivo. While the spatial resolution of this technique permits the calcium activity of individual cells within the field of view to be monitored, inferring the precise times at which a neuron emits a spike is challenging because spikes are hidden within noisy observations of the neuron's calcium activity. To tackle this problem, we introduce the use of sparse approximation methods for recovering spikes from the time-varying calcium activity of neurons. We derive sufficient conditions for exact recovery of spikes with respect to (i) the decay rate of the spike-evoked calcium event and (ii) the maximum firing rate of the cell under test. We find-both in theory and in practice-that standard sparse recovery methods are not sufficient to recover spikes from noisy calcium signals when the firing rate of the cell is high, suggesting that in order to guarantee exact recovery of spike times, additional constraints must be incorporated into the recovery procedure. Hence, we introduce an iterative framework for structured sparse approximation that is capable of achieving superior performance over standard sparse recovery methods by taking into account knowledge that spikes are non-negative and also separated in time. We demonstrate the utility of our approach on simulated calcium signals in various amounts of additive Gaussian noise and under different degrees of model mismatch.