A video encoded as a bit stream is decoded using trained sparse orthonormal transforms generated from decoded prediction residual signals, wherein the transforms have associated indices. A current macroblock is entropy decoded and inverse quantized to produce decoded coefficients. For the current macroblock, an L0-norm regularized training process generates a set of mode-dependent sparse orthonormal inverse transforms, selected according to a prediction mode signaled in the bit stream. Decoded coefficients are inverse transformed and then are combined with previously decoded macroblocks to generate an output macroblock of a reconstructed video.