An Almost Optimal Algorithm for Computing Nonnegative Rank Ankur Moitra Institute for Advanced Study January 8, 2013 AnkurMoitra (IAS,PU) Provably January8,2013 m M n W m M = A inner−dimension n rank W m M = A inner−dimension n rank non−negative W m M = A inner−dimension n non−negative n o n − n e g a t i vraenk non−negative W m M = A inner−dimension n non−negative Combinatorics: extended formulation, log-rank conjecture [Yannakakis], [Lov´asz, Saks] Physical Modeling: interaction of components is additive visual recognition, environmetrics Applications Statistics and Machine Learning: extract latent relationships in data image segmentation, text classification, information retrieval, collaborative filtering, ... [Lee, Seung], [Xu et al], [Hofmann], [Kumar et al], [Kleinberg, Sandler] Physical Modeling: interaction of components is additive visual recognition, environmetrics Applications Statistics and Machine Learning: extract latent relationships in data image segmentation, text classification, information retrieval, collaborative filtering, ... [Lee, Seung], [Xu et al], [Hofmann], [Kumar et al], [Kleinberg, Sandler] Combinatorics: extended formulation, log-rank conjecture [Yannakakis], [Lov´asz, Saks] Applications Statistics and Machine Learning: extract latent relationships in data image segmentation, text classification, information retrieval, collaborative filtering, ... [Lee, Seung], [Xu et al], [Hofmann], [Kumar et al], [Kleinberg, Sandler] Combinatorics: extended formulation, log-rank conjecture [Yannakakis], [Lov´asz, Saks] Physical Modeling: interaction of components is additive visual recognition, environmetrics [Vavasis]: It is NP-hard to compute the nonnegative rank. [Cohen and Rothblum]: The nonnegative rank can be computed in time (nm)O(nr+mr). [Arora, Ge, Kannan and Moitra]: The nonnegative rank can be computed in time (nm)f(r) where f(r)=O(2r) and any algorithm that runs in time (nm)o(r) would yield a sub exponential time algorithm for 3-SAT. Theorem The nonnegative rank can be computed in time (nm)O(r2). ...these algorithms are about an algebraic question, about how to best encode nonnegative rank as a systems of polynomial inequalities The Complexity of Nonnegative Rank