Face recognition is a long-standing topic in machine learning. Recent advances promise successful applications in large-scale video surveillance. Recognizing millions of people in thousands of streaming cameras, however, implies significant costs in terms of computations and communication bandwidth. This work aims to reduce the complexity of face recognition in video and pursues two complementary strategies. We first investigate face recognition in the whitened descriptor space and improve the complexity of the state-of-the-art Matched Background Similarity (MBGS) approach. Second, we study frame selection and demonstrate robust recognition performance from a small fraction of video frames. For a better understanding of the advancing Deep Convolution Neural Networks field, we give a thorough introduction to the topic and briefly summarize the recent development with a focus on the ImageNet classification challenge. We evaluate our methods and present competitive results for the YTF and TSFT benchmarks while significantly reducing the complexity of previous methods.