visual feature learning, which aims to construct an effective feature representation for visual data, has a wide range of applications in computer vision. it is often posed as a problem of nonnegative matrix factorization (nmf), which constructs a linear representation for the data. although nmf is typically parallelized for efficiency, traditional parallelization methods suffer from either an expensive computation or a high runtime memory usage. to alleviate this problem, we propose a parallel nmf method called alternating least square block decomposition (alsd), which efficiently solves a set of conditionally independent optimization subproblems based on a highly parallelized fine-grained grid-based blockwise matrix decomposition. by assigning each block optimization subproblem to an individual computing node, alsd can be effectively implemented in a mapreduce-based hadoop framework. in order to cope with dynamically varying visual data, we further present an incremental version of alsd, which is able to incrementally update the nmf solution with a low computational cost. experimental results demonstrate the efficiency and scalability of the proposed methods as well as their applications to image clustering and image retrieval.