THE CAPACITY OF SPARSELY ENCODED ASSOCIATIVE MEMORIES

We consider an asymptotically sparsely encoded associative memory. Patterns are encoded by n-dimensional vectors of -1 and +1 generated randomly by a sequence of biased Bernoulli trials and stored in the network according to Hebbian rule. Using a heuristic argument we derive the following capacities: c(n) = n(e)/4k log n' C(n) = n(e)/4k (1+e) log n' where, 0 < e < 1 controls the degree of sparsity of the encoding scheme and k is a constant. Here c(n) is the capacity of the network such that any stored pattern is a fixed point with high probability, whereas C(n) is the capacity of the network such that all stored patterns are fixed points with high probability. The main contribution of this technical paper is a theoretical verification of the above results using the Poisson limit theorems of exchangeable events.