In this paper we address some of the main shortcomings of multi-channel (MC) linear restoration filters. The problem of restoring a MC image and simultaneously estimating the MC power spectrum of the image and the noise, required by linear minimum mean squared error (LMMSE) filters is investigated, using the expectation-maximization (EM) algorithm. Second, the problem of estimating, the regularization parameters and operator, required by regularized least-squares (RLS) MC restoration filters is investigated using the cross-validation (CV) function. Furthermore, a novel representation of MC signal processing is introduced. This notation leads to a more natural extension of single-channel (SC) signal processing algorithms to the MC case and yields a new class of matrices which we call semi-block- circulant (SBC) matrices. The properties of these matrices are examined and a family of new efficient algorithms is developed for the computation of the MC EM and CV functions.