  In this paper we explore avenues for improving the reliability of
dimensionality reduction methods such as Non-Negative Matrix Factorization
(NMF) as interpretive exploratory data analysis tools. We first explore the
difficulties of the optimization problem underlying NMF, showing for the first
time that non-trivial NMF solutions always exist and that the optimization
problem is actually convex, by using the theory of Completely Positive
Factorization. We subsequently explore four novel approaches to finding
globally-optimal NMF solutions using various ideas from convex optimization. We
then develop a new method, isometric NMF (isoNMF), which preserves
non-negativity while also providing an isometric embedding, simultaneously
achieving two properties which are helpful for interpretation. Though it
results in a more difficult optimization problem, we show experimentally that
the resulting method is scalable and even achieves more compact spectra than
standard NMF.
