Cosa: An accelerated ISTA algorithm for dictionaries based on translated waveforms

The use of compressive sensing techniques has become predominant in signal processing applications when dealing with sparse signals. Theoretical results on these tools involve drastic conditions on the dictionaries used, which are usually not met in practice. Nevertheless, it has been recently shown that even in the case of very correlated dictionaries, such as dictionaries based on translated waveforms, information can be retrieved from the observations with good accuracy. However, in numerous fields the signals that we have to process are extremely large, making the direct use of standard algorithms impossible. This paper presents a fast version of the Iterative Shrinkage-Thresholding Algorithm (ISTA) for sparse reconstruction based on dictionaries built from translated waveforms. By rearranging the columns of the dictionary, we show that matrix-vector multiplications can be alternatively expressed as convolutions, which can be performed efficiently using standard Fast Fourier Transforms (FFTs). Results on synthetic data validate the proposed convolutional ISTA (CoSA) method. Furthermore, we also show that CoSA is able to attain good results in a real-world application, where ISTA cannot be applied directly: spike localization and activity estimation in a large spectroscopic signal.