Non-negative matrix factorization (NMF) is a widely used tool for exploratory data analysis in many disciplines. In this paper, we describe an approach to NMF based on random projections and give a geometric analysis of a prototypical algorithm. Our main result shows the proto-algorithm requires κ¯klogk optimizations to find all the extreme columns of the matrix, where k is the number of extreme columns, and κ¯ is a geometric condition number. We show empirically that the proto-algorithm is robust to noise and well-suited to modern distributed computing architectures.
I note from the conclusion
...A third benefi t is that the approach gives interpretable results even when the matrix is not separable. When the matrix is not separable, the approach no longer gives the (minimum non-negative rank) NMF. However, the geometric interpretation remains valid and the approach gives non-negative factors U and V such that the columns of U are the extreme rays of a polyhedral cone that contains most of the columns of X....
If you recall a matrix is separable when at least one column represent a pure component. This has a clear interpretation when performing hyperspectral imaging. This is also interesting if the PSF of your imaging system is random. I wonder if I should add it to the Advanced Matrix Factorization Jungle page as an implementation is not there but then again, the implementation seems "simple" enough. An earlier implementation of NMF is XRAY was featured in: Fast Conical Hull Algorithms for Near-separable Non-negative Matrix Factorization by Abhishek Kumar, Vikas Sindhwani, Prabhanjan Kambadur
The separability assumption (Donoho & Stodden, 2003; Arora et al., 2012) turns non-negative matrix factorization (NMF) into a tractable problem. Recently, a new class of provably-correct NMF algorithms have emerged under this assumption. In this paper, we reformulate the separable NMF problem as that of finding the extreme rays of the conical hull of a finite set of vectors. From this geometric perspective, we derive new separable NMF algorithms that are highly scalable and empirically noise robust, and have several other favorable properties in relation to existing methods. A parallel implementation of our algorithm demonstrates high scalability on shared- and distributed-memory machines.
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.
No comments:
Post a Comment