In this paper, a novel sparse feature set is introduced into the Adaboost learning framework for multi-view face detection (MVFD), and a learning algorithm based on heuristic search is developed to select sparse features in granular space. Compared with Haar-like features, sparse features are more generic and powerful to characterize multi-view face pattern that is more diverse and asymmetric than frontal face pattern. In order to cut down search space to a manageable size, we propose a multi-scaled search algorithm that is about 6 times faster than brute-force search. With this method, a MVFD system is implemented that covers face pose changes over +/-45? rotation in plane (RIP) and +/-90? rotation off plane (ROP). Experiments over well-know test set are reported to show its high performance in both accuracy and speed.