A mathematical solution to a network construction problem

One of the major open issues in neural networks includes a network construc tion problem (NCP) to find a procedure, polynomial time if possible, that p roduces a minimal structure (minimum size, threshold and weight) of a multi layer threshold feed-forward network where its output must not exceed any g iven admissible distortion from a sample. The NCP includes a subproblem, a network training problem (NTP), where the size is prespecified. Approximate versions of the NCP/NTP have been solved with iterative algorithms for the network construction/training. This paper provides a mathematically rigoro us solution to the NCP using rate distortion theory from information theory and linear algebra. This solution is used to develop a mathematical proced ure that specifically constructs a minimal structure from the sample. The p rocedure attains the exact minimum though its computational time is, at wor st, nonpolynomial. The paper also constructs a polynomial-time shortcut for approximate minimum sizes, which is a promising alternative to current alg orithms.