Fast and accurate algorithms are essential for the efficient search and retrieval of the huge amount of video data that is generated for different purposes and applications every day. 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 to deal with the search of noisy video clips with also possibly missing frames. 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 to the retrieval of video clips with missing frames as well as its robustness against noise.