In this paper we propose a new motion compensated prediction technique that enables successful predictive encoding during fades, blended scenes, tem- porally decorrelated noise, and many other temporal evolutions which force predictors used in traditional hybrid video coders to fail. We model reference frame blocks to be used in motion compensated prediction as consisting of two superimposed parts: One part that is relevant for prediction and another part that is not relevant. By performing prediction in a domain where the video frames are spatially sparse, our work allows the automatic isolation of the prediction-relevant parts. These are then used to enable better prediction than would be possible otherwise. Our sparsity induced prediction algorithm (SIP) generates successful predictors by exploiting the non-convex structure of the sets that natural images and video frames lie in. Correctly determining this non-convexity through sparse representations allows better performance in hybrid video codecs equipped with the proposed work.