Sparse Approximate Conic Hulls



Journal Title

Journal ISSN

Volume Title


Neural Information Processing Systems Foundation


We consider the problem of computing a restricted nonnegative matrix factorization (NMF) of an m × n matrix X. Specifically, we seek a factorization X ≈ BC, where the k columns of B are a subset of those from X and C ∈ ℝ{^{k×n} _{≥0}} k×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 ε-approximates 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 ε-fraction of the angular diameter of X. If k is the size of the smallest ε-approximation, then we produce an O(k/ε²/³) sized O (ε¹/³)-approximation, yielding the first provable, polynomial time ε-approximation 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 ε-approximated with an O(1/ε²) 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 d-SUM-hard, resolving an open problem. Finally, we provide experimental results for the convex and conic algorithms on a variety of feature selection tasks. © 2017 Neural information processing systems foundation. ©2017 Neural Information Processing Systems Foundation. All rights reserved.


Includes supplementary material


Factorization (Mathematics), Approximation theory, Polynomials, Matrices

NSF CRII Award-1566137; DARPA Explainable Artificial Intelligence Program under contract number N66001-17- 2-4032 and NSF grant III-1527312.


©2017 Neural Information Processing Systems Foundation. All rights reserved.