In this paper we propose a novel framework that successfully combines random projection or compression to weighted Nonnegative Matrix Factorization (NMF). Indeed a large body of NMF research has focused on the unweighted case—i.e., a complete data matrix to factorize—with a few extensions to handle incomplete data. Also most of these works are typically not efficient enough when the size of the data is arbitrarily large. Random projections belong to the major techniques used to process big data and although have been successfully applied to NMF, there was no investigation with weighted NMF. For this reason we propose to combine random projection with weighted NMF, where the weight models the confidence in the data (or the absence of confidence in the case of missing data). We experimentally show the proposed framework to significantly speed-up state-of-the-art NMF methods under some mild conditions when applied on various data.