Matrix Patch Reordering as a Strategy for Compression, Factorization, and Pattern Detection using Nonnegative Matrix Factorization Applied to Single Images

Recent improvements in computing and technology demand the processing and analysis of huge datasets in a variety of fields. Often the analysis requires the creation of low-rank approximations to the datasets. We see examples of these requirements in the following fields of application: facial recognition, fingerprint compression, email and document analysis as well as web searches. One tool being used in obtaining a low-rank approximation to large datasets is Nonnegative Matrix Factorization (NMF). NMF is a relatively new, dictionary construction approach that has gathered significant momentum when an application requires a low-rank, parts-based representation to the dataset. Paatero \u26 Tapper first introduced the scheme called Positive Matrix Factorization. Lee \u26 Seung popularized and developed the NMF technique by factoring the matrix A = WH and requiring that the matrices W and H be nonnegative. In this thesis we explore low-rank approximations using NMF and other factorization methods being applied to reordered pixels of a single image. The method reduces the dimensionality of the dataset by breaking up a single image into a series of non-overlapping, contiguous patches. We find that by simply reordering the entries of the matrix associated with the image prior to the application of the factorization technique, we are able to achieve better low rank approximations at lower computational cost. We discover that the application of NMF on these datasets preserve the sign structure of the datasource while providing a parts-based representation of the data. We also introduce a series of conjectures on the convergence of this approach when applied to single images and to patterns generated by wallpaper groups