Pattern capacity of a perceptron for sparse discrimination

We evaluate the capacity and performance of a perceptron discriminator operating in a highly sparse regime where classic perceptron results do not apply. The perceptron is constructed to respond to a specified set of q stimuli, with only statistical information provided about other stimuli to which it is not supposed to respond. We compute the probability of both false-positive and false-negative errors and determine the capacity of the system for not responding to nonselected stimuli and for responding to selected stimuli in the presence of noise. If q is a sublinear function of N, the number of inputs to the perceptron, these capacities are exponential in N/q.