Exact NMF on Single Images via Reordering of Pixel Entries Using Patches

Non-negative Matrix Factorization (NMF) has been shown to be effective in providing low-rank, parts-based approximations to canonical datasets comprised of non-negative matrices. The approach involves the factorization of the non-negative matrix A into the product of two non-negative matrices W and H, where the columns of W serve as a set of dictionary vectors for approximating the matrix A. One drawback to this approach is the lack of an exact solution since the problem is not convex in both W and H simultaneously. Previous authors have shown that an exact solution can be achieved by using datasets with specified properties. In this paper we propose a factorial dataset for the use of NMF on patches of a single image. We show that when the multiplicative update is applied to a single image, we are successful in achieving a set of standard basis vectors for the image. We show that by reordering the patches of a specified dataset, the algorithm is successful in achieving exact approximations of single images while preserving the number of standard basis vectors. We use Mean Squared Error (MSE), Peak Signal-to-Noise Ratio (PSNR) and Mean Structured Similarity Index (MSSIM) as measures of the quality of the low rank approximations for a given rank k.