Name
Abstract | ||
|---|---|---|
Quadratic optimization lies at the very heart of many structural pattern recognition and computer vision problems, such as graph matching, object recognition, image segmentation, etc., and it is therefore of crucial importance to devise algorithmic solutions that are both efficient and effective. As it turns out, a large class of quadratic optimization problems can be formulated in terms of so-called ''standard quadratic programs'' (StQPs), which ask for finding the extrema of a quadratic polynomial over the standard simplex. Computationally, the standard approach for attacking this class of problems is to use replicator dynamics, a well-known family of algorithms from evolutionary game theory inspired by Darwinian selection processes. Despite their effectiveness in finding good solutions in a variety of applications, however, replicator dynamics suffer from being computationally expensive, as they require a number of operations per step which grows quadratically with the dimensionality of the problem being solved. In order to avoid this drawback, in this paper we propose a new population game dynamics (InImDyn) which is motivated by the analogy with infection and immunization processes within a population of ''players.'' We prove that the evolution of our dynamics is governed by a quadratic Lyapunov function, representing the average population payoff, which strictly increases along non-constant trajectories and that local solutions of StQPs are asymptotically stable (i.e., attractive) points. Each step of InImDyn is shown to have a linear time/space complexity, thereby allowing us to use it as a more efficient alternative to standard approaches for solving StQPs and related optimization problems. Indeed, we demonstrate experimentally that InImDyn is orders of magnitude faster than, and as accurate as, replicator dynamics on various applications ranging from tree matching to image registration, matching and segmentation. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1016/j.cviu.2010.12.004 | Computer Vision and Image Understanding |
Keywords | Field | DocType |
average population payoff,standard quadratic program,fast evolutionary approach,quadratic lyapunov function,quadratic optimization,standard approach,population dynamics,graph-based quadratic optimization,graph matching,standard simplex,replicator dynamic,graph-based problems,quadratic optimization problem,quadratic polynomial,linear time,image registration,image segmentation,optimization problem,pattern recognition,lyapunov function,quadratic program,evolutionary game theory,population dynamic,computer vision,object recognition,space complexity | Population,Quadratic growth,Mathematical optimization,Replicator equation,Quadratic equation,Quadratic function,Artificial intelligence,Quadratic programming,Time complexity,Optimization problem,Mathematics,Machine learning | Journal |
Volume | Issue | ISSN |
115 | 7 | Computer Vision and Image Understanding |
Citations | PageRank | References |
39 | 1.09 | 42 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Samuel Rota Bulò | 1 | 564 | 33.69 |
| Marcello Pelillo | 2 | 1888 | 150.33 |
| Immanuel M. Bomze | 3 | 922 | 87.13 |