Ruozzi, Nicholas

Permanent URI for this collectionhttps://hdl.handle.net/10735.1/6930

Nicholas Ruozzi is an Assistant Professor of Computer Science and a member of UTD's Center for Machine Learning. His research interests include:

  • Combinatorial Optimization
  • Large-Scale Graphical Models
  • Approximate Inference and Learning
  • Belief Propagation Style Message-Passing Algorithms
  • Machine Learning

Browse

Recent Submissions

Now showing 1 - 1 of 1
  • Thumbnail Image
    Item
    Sparse Approximate Conic Hulls
    (Neural Information Processing Systems Foundation) Van Buskirk, Gregory; Raichel, Benjamin; Ruozzi, Nicholas; Van Buskirk, Gregory; Raichel, Benjamin; Ruozzi, Nicholas
    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.

Works in Treasures @ UT Dallas are made available exclusively for educational purposes such as research or instruction. Literary rights, including copyright for published works held by the creator(s) or their heirs, or other third parties may apply. All rights are reserved unless otherwise indicated by the copyright owner(s).