This paper presents a novel robust digital image watermarking scheme using subsampling and nonnegative matrix factorization. Firstly, subsampling is used to construct a subimage sequence. Then, based on the column similarity of the subimage sequence, nonnegative matrix factorization (NMF) is applied to decompose the sequence. A Gaussian pseudo-random watermark sequence is embedded in the factorized decomposition coefficients. Because of the high similarity of subimages and meaningful factorization for NMF, the proposed scheme can achieve good robustness, especially to common permutation attacks. Numerical experiment results demonstrate the good performance of the proposed scheme.