A model-based dynamic MRI called k-t BLAST/SENSE has drawn significant attention from the MR imaging community because of its improved spatio-temporal resolution. Recently, we showed that the k-t BLAST/SENSE corresponds to the special case of a new dynamic MRI algorithm called k-t FOCUSS that is optimal from a compressed sensing perspective. The main contribution of this article is an extension of k-t FOCUSS to a more general framework with prediction and residual encoding, where the prediction provides an initial estimate and the residual encoding takes care of the remaining residual signals. Two prediction methods, RIGR and motion estimation/compensation scheme, are proposed, which significantly sparsify the residual signals. Then, using a more sophisticated random sampling pattern and optimized temporal transform, the residual signal can be effectively estimated from a very small number of k-t samples. Experimental results show that excellent reconstruction can be achieved even from severely limited k-t samples without aliasing artifacts.