Every day, a huge amount of video data is generated for different purposes and applications. Fast and accurate algorithms for efficient video search and retrieval are therefore essential. The interesting properties of sparse representation and the new sampling theory named Compressive Sensing (CS) constitute the core of the new approach to video representation and retrieval we are presenting in this paper. Once the representation (where sparsity is expected) has been chosen and the observations have been taken, the proposed approach utilizes Bayesian modeling and inference to tackle the retrieval problem. In order to speed up the inference process the use of Principal Components Analysis (PCA) to provide an alternative representation of the frames is analyzed. Experimental results validate the proposed approach whose robustness against noise is also examined.