Introduction

There exists a large gap between the empirical evidence of the computational capabilities of neural networks and our ability to systematically analyze and design those networks. Although it is well known that classical Fourier analysis is a very effective mathematical tool for the design and analysis of linear systems, such a tool was not available for artificial neural networks, which are inherently nonlinear. In the late 1980s, the spectral analysis tool was introduced in the domain of discrete neural networks. The application of the spectral technique led to a number of new insights and results, including lower and upper bounds on the complexity of computing with neural networks as well as methods for constructing optimal (in terms of performance) feedforward networks for computing various arithmetic functions.

The focus of the presentation in this chapter is on an elementary description of the basic techniques of Fourier analysis and its applications in threshold circuit complexity. Our hope is that this chapter will serve as background material for those who are interested in learning more about the progress and results in this area. We also provide extensive bibliographic notes that can serve as pointers to a number of research results related to spectral techniques and threshold circuit complexity.