Multi-hypothesis prediction (MH) is a key technique in compressed video sensing (CVS) predictionresidual reconstruct-algorithm． Unfortunately，when dealing with fast moving sequences，high computational complexity and low prediction accuracy are unavoidable． Besides，MH in measurement domain just employs the sum of absolute difference (SAD) principle to select hypothesis blocks，which usually introduces noise in the prediction blocks and decreases the reconstruction quality for neglecting the oneto-many relationship between the given measurement and original signals． To address these issues，this paper takes advantage of the motion features in video and proposes a multi-hypothesis prediction scheme based on fast diamond search with two matching regions (MHDS)． The MH-DS uses the fast diamond search method to search in two different directions for two optimal matching regions，where hypothesis blocks are obtained． MH-DS reduces the computational complexity of the searching process and get more effective prediction information． Moreover，a new matching criterion integrating mean square error (MMSE) with maximum pixels counting (MPC) is proposed in MH-DS in order to get more relevant hypothesis blocks． Simulative results show that the proposed MH-DS reduce the computational complexity of prediction process at reconstruction side and obtain higher prediction accuracy and higher reconstruction quality than the stateofthe-art CVS prediction methods．