Dimensional mismatch between a low-resolution (LR) surveillance face image and its high-resolution (HR) template makes recognition very difficult. A novel method called coupled cross-regression (CCR) is proposed to deal with this problem. Instead of processing in the original observing space directly, CCR projects LR and HR face images into a unified low-embedding feature space. Spectral regression is employed to improve generalization performance and reduce computational complexity. Meanwhile, cross-regression is developed to utilize HR embedding to increase the information of the LR space, thus improving the recognition performance. Experiments on the FERET and CMU PIE face database show that CCR outperforms existing structure-based methods in terms of recognition rate as well as computational complexity.