2020/02/26 by Ioannis Panageas, Stratis Skoulakis, Panageas, Ioannis +5
Computer Science · Engineering · #Advanced Adaptive Filtering Techniques #Blind Source Separation Techniques #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC) #Speech and Audio Processing
paper · pdf · doi:10.48550/arxiv.2002.11323
openalex publication_date 2020/02/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Non-negative matrix factorization (NMF) is a fundamental non-convex optimization problem with numerous applications in Machine Learning (music analysis, document clustering, speech-source separation etc). Despite having received extensive study, it is poorly understood whether or not there exist natural algorithms that can provably converge to a local minimum. Part of the reason is because the objective is heavily symmetric and its gradient is not Lipschitz. In this paper we define a multiplicative weight update type dynamics (modification of the seminal Lee-Seung algorithm) that runs concurrently and provably avoids saddle points (first order stationary points that are not second order). Our techniques combine tools from dynamical systems such as stability and exploit the geometry of the NMF objective by reducing the standard NMF formulation over the non-negative orthant to a new formulation over (a scaled) simplex. An important advantage of our method is the use of concurrent updates, which permits implementations in parallel computing environments.