Multiplicative Updates for Nonnegative Quadratic Programming

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...

Full description

Saved in:
Bibliographic Details
Published in:Neural computation 2007-08, Vol.19 (8), p.2004-2031
Main Authors: Sha, Fei, Lin, Yuanqing, Saul, Lawrence K., Lee, Daniel D.
Format: Article
Language:English
Subjects:
Algorithms
Animals
Applied sciences
Artificial intelligence
Biological and medical sciences
Calculus of variations and optimal control
Computer programming
Computer science
control theory
systems
Exact sciences and technology
Fundamental and applied biological sciences. Psychology
General aspects
Heuristic
Humans
Information Storage and Retrieval - methods
Learning and adaptive systems
Mathematical analysis
Mathematics
Mathematics in biology. Statistical analysis. Models. Metrology. Data processing in biology (general aspects)
Miscellaneous
Neural Networks (Computer)
Optimization
Programming, Linear
Sciences and techniques of general use
Signal Processing, Computer-Assisted
Citations: Items that this one cites
Items that cite this one
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0899-7667
1530-888X
DOI:10.1162/neco.2007.19.8.2004