Near-separable Non-negative Matrix Factorization with $\ell_1$- and
  Bregman Loss Functions
  Recently, a family of tractable NMF algorithms have been proposed under the
assumption that the data matrix satisfies a separability condition Donoho &
Stodden (2003); Arora et al. (2012). Geometrically, this condition reformulates
the NMF problem as that of finding the extreme rays of the conical hull of a
finite set of vectors. In this paper, we develop several extensions of the
conical hull procedures of Kumar et al. (2013) for robust ($\ell_1$)
approximations and Bregman divergences. Our methods inherit all the advantages
of Kumar et al. (2013) including scalability and noise-tolerance. We show that
on foreground-background separation problems in computer vision, robust
near-separable NMFs match the performance of Robust PCA, considered state of
the art on these problems, with an order of magnitude faster training time. We
also demonstrate applications in exemplar selection settings.
