Analysis on the Convergence Time of Dual Neural Network-Based $k{\rm WTA}$

A k-winner-take-all (kWTA) network is able to find out the k largest numbers from n inputs. Recently, a dual neural network (DNN) approach was proposed to implement the kWTA process. Compared to the conventional approach, the DNN approach has much less number of interconnections. A rough upper bound on the convergence time of the DNN-kWTA model, which is expressed in terms of input variables, was given. This brief derives the exact convergence time of the DNN-kWTA model. With our result, we can study the convergence time without spending excessive time to simulate the network dynamics. We also theoretically study the statistical properties of the convergence time when the inputs are uniformly distributed. Since a nonuniform distribution can be converted into a uniform one and the conversion preserves the ordering of the inputs, our theoretical result is also valid for nonuniformly distributed inputs.