Date: 20.05.2022

Time: 15:00 CEST (Central European Summer Time)

Title of the Talk: On the Sufficiently Scattered Condition for Unique Simplex-Structured Matrix Factorizations

Speaker: Dr. Tim Marrinan (Postdoctoral research associate at Department of Electrical Engineering and Computer Science, Oregon State University)

Event  Link: Zoom

Abstract: A classical result of Freund and Orlin ("On the complexity of four polyhedral set containment problems'', Math. Prog., 1985) established that checking whether a ball is contained by a polytope described as a convex hull of a set of points is NP-complete. In the realm of simplex-structured matrix factorization (SSMF), which includes nonnegative matrix factorization (NMF) as a special case, checking the so-called sufficiently scattered condition (SSC) for uniqueness that is relevant in most practical applications is equivalent to this classical problem. The result of Freund and Orlin, therefore, implies that it is infeasible to check whether a factorization is unique for large-scale problems, even if the SSC  is  likely to be satisfied. On the other hand, stricter sufficient conditions exist that can be checked efficiently, but their assumptions are too restrictive for many settings. Since many downstream applications of SSMF require the decomposition to be essentially unique, we propose a novel sufficient condition that can be checked efficiently in many practical scenarios. In fact, the complexity of the method is a function of the desired rank of the factorization, rather than of the number of columns of the matrix to be factorized, and the complexity decreases in a stepped fashion as a function of the sparsity of the input data. Thus, the proposed conditions build a bridge between the "easy-to-check but infrequently applicable" conditions and the "frequently satisfied but intractable" conditions that currently exist in the literature.

Biography of the Speaker: Tim Marrinan is an applied mathematician focused on bridging computational mathematics and rigorous machine learning. This goal is achieved by advancing the understanding of factorization models, latent representation models, and constrained optimization methods to come up with theory-guaranteed data analytical/computational methods.  At the moment, Tim is an instructor and postdoctoral researcher at Oregon State University, where he works with Professor Xiao Fu. Prior to Oregon State, Tim got his PhD in mathematics from Colorado State University and did research appointments at both the University of Paderborn in Germany and the University of Mons in Belgium. Outside of research Tim is working to support the mental health of students in math and engineering and advocating for students from historically excluded groups. His hobbies include canoeing, basketball, ultimate frisbee, and taking walks with his Irish wolfhound, Reggie.