  We propose new approximate alternating projection methods, based on
randomized sketching, for the low-rank nonnegative matrix approximation
problem: find a low-rank approximation of a nonnegative matrix that is
nonnegative, but whose factors can be arbitrary. We calculate the computational
complexities of the proposed methods and evaluate their performance in
numerical experiments. The comparison with the known deterministic alternating
projection methods shows that the randomized approaches are faster and exhibit
similar convergence properties.
