Robustness Analysis of HottTopixx, a Linear Programming Model for Factoring Nonnegative Matrices - implementation -

In a previous entry featuring a new approach to NMF (Hott Topixx: Factoring nonnegative matrices with linear programs - implementation -), we are beginning to see how NMF, the most overused advanced matrix factorization in all of engineering and science, is getting to be treated through a linear programming approach. With this approach, we are beginning to see that real reasons why NMF work or doesn't with the arrival of some sort of theoretical bounds. People like Victor Bittorf, Benjamin Recht, Christopher Ré, Joel Tropp and now Nicolas Gillis are draining the waters around these islands of knowledge. Here is a paper of the latter sorts: Robustness Analysis of HottTopixx, a Linear Programming Model for Factoring Nonnegative Matrices by Nicolas Gillis. The abstract reads:

Although nonnegative matrix factorization (NMF) is NP-hard in general, it has been shown very recently that it is tractable under the assumption that the input nonnegative data matrix is separable (that is, there exists a cone spanned by a small subset of the columns containing all columns). Since then, several algorithms have been designed to handle this subclass of NMF problems. In particular, Bittorf, Recht, R\'e and Tropp (`Factoring nonnegative matrices with linear programs', NIPS 2012) proposed a linear programming model, referred to as HottTopixx. In this paper, we provide a new and more general robustness analysis of their method. In particular, our analysis is almost tight and allows duplicates and near duplicates in the dataset. Moreover, we design a provably more robust variant using an appropriate post-processing strategy.

From Nicolas' code page:

"....This matlab code provides the constructions decribed in the paper below. It also contains a CVX code for the LP model from Bittorf, Recht, Ré, and Tropp, "Factoring nonnegative matrices with linear programs", Advances in Neural Information Processing Systems 25, pp. 1223-1231, 2012. (Note. There was an error in the post-processing in the first version.)..."

This algorithm and code will shortly be listed to the Advanced Matrix Factorization Jungle page.



Image Credit: NASA/JPL/Space Science Institute

N00199001.jpg was taken on December 12, 2012 and received on Earth December 12, 2012. The camera was pointing toward JANUS, and the image was taken using the CL1 and CL2 filters. This image has not been validated or calibrated.


Join the CompressiveSensing subreddit or the Google+ Community and post there !
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.