Time complexity analysis of the Stochastic Diffusion Search
Nasuto, S.; Bishop, Mark (J. M.) and Lauria, S. 1998. Time complexity analysis of the Stochastic Diffusion Search. Neural Computation '98, pp. 260-266. [Article]No full text available
Official URL: http://www.doc.gold.ac.uk/~mas02mb/Selected%20Pape...
Abstract or Description
The Stochastic Diffusion Search algorithm -an integral part of Stochastic Search Networks is investigated. Stochastic Diffusion Search is an alternative solution for invariant pattern recognition and focus of attention. It has been shown that the algorithm can be modelled as an ergodic, finite state Markov Chain under some non-restrictive assumptions. Sub-linear time complexity for some settings of parameters has been formulated and proved. Some properties of the algorithm are then characterised and numerical examples illustrating some features of the algorithm are presented.