Non-negative matrix factorization (NMF) has increasingly been used for efficiently decomposing multivariate data into a signal dictionary and corresponding activations. In this paper, we propose an algorithm called sparse shift-invariant NMF (ssiNMF) for learning possibly overcomplete shift- invariant features. This is done by incorporating a circulant property on the features and sparsity constraints on the activations. The circulant property allows us to capture shifts in the features and enables efficient computation by the Fast Fourier Transform. The ssiNMF algorithm turns out to be matrix-free for we need to store only a small number of features. We demonstrate this on a dataset generated from an overcomplete set of bars.