Timezone: »
We consider the problem of computing a restricted nonnegative matrix factorization (NMF) of an m\times n matrix X. Specifically, we seek a factorization X\approx BC, where the k columns of B are a subset of those from X and C\in\Re_{\geq 0}^{k\times n}. Equivalently, given the matrix X, consider the problem of finding a small subset, S, of the columns of X such that the conic hull of S \epsapproximates the conic hull of the columns of X, i.e., the distance of every column of X to the conic hull of the columns of S should be at most an \epsfraction of the angular diameter of X. If k is the size of the smallest \epsapproximation, then we produce an O(k/\eps^{2/3}) sized O(\eps^{1/3})approximation, yielding the first provable, polynomial time \epsapproximation for this class of NMF problems, where also desirably the approximation is independent of n and m. Furthermore, we prove an approximate conic Carathéodory theorem, a general sparsity result, that shows that any column of X can be \epsapproximated with an O(1/\eps^2) sparse combination from S. Our results are facilitated by a reduction to the problem of approximating convex hulls, and we prove that both the convex and conic hull variants are dsumhard, resolving an open problem. Finally, we provide experimental results for the convex and conic algorithms on a variety of feature selection tasks.
Author Information
Greg Van Buskirk (UT Dallas)
Benjamin Raichel (UT Dallas)
Nicholas Ruozzi (UTDallas)
More from the Same Authors

2021 Poster: How can classical multidimensional scaling go wrong? »
Rishi Sonthalia · Greg Van Buskirk · Benjamin Raichel · Anna Gilbert 
2015 Poster: Exactness of Approximate MAP Inference in Continuous MRFs »
Nicholas Ruozzi