title: Multiplicative updates for nonnegative quadratic programming.
abstract: Many problems in neural computation and statistical learning involve optimizations with nonnegativity constraints. In this article, we study convex problems in quadratic programming where the optimization is confined to an axis-aligned region in the nonnegative orthant. For these problems, we derive multiplicative updates that improve the value of the objective function at each iteration and converge monotonically to the global minimum. The updates have a simple closed form and do not involve any heuristics or free parameters that must be tuned to ensure convergence. Despite their simplicity, they differ strikingly in form from other multiplicative updates used in machine learning. We provide complete proofs of convergence for these updates and describe their application to problems in signal processing and pattern recognition.
authors.affiliation: Computer Science Division, University of California, Berkeley, Berkeley, CA 94720, USA. feisha@cs.berkeley.edu
authors.forename: Fei
authors.initials: F
authors.lastname: Sha
authors.forename: Yuanqing
authors.initials: Y
authors.lastname: Lin
authors.forename: Lawrence K
authors.initials: LK
authors.lastname: Saul
authors.forename: Daniel D
authors.initials: DD
authors.lastname: Lee
mesh_terms: D000465:Algorithms; D000818:Animals; D006801:Humans; D016247:Information Storage and Retrieval / Q000379:methods*; D016571:Neural Networks, Computer; D011382:Programming, Linear; D012815:Signal Processing, Computer-Assisted