The notion of word embedding plays a fundamental role in natural language\nprocessing (NLP). However, pre-training word embedding for very large-scale\nvocabulary is computationally challenging for most existing methods. In this\nwork, we show that with merely a small fraction of contexts (Q-contexts)which\nare typical in the whole corpus (and their mutual information with words), one\ncan construct high-quality word embedding with negligible errors. Mutual\ninformation between contexts and words can be encoded ca…