  In this paper, we present an approach for minimizing the computational
complexity of trained Convolutional Neural Networks (ConvNet). The idea is to
approximate all elements of a given ConvNet and replace the original
convolutional filters and parameters (pooling and bias coefficients; and
activation function) with efficient approximations capable of extreme
reductions in computational complexity. Low-complexity convolution filters are
obtained through a binary (zero-one) linear programming scheme based on the
Frobenius norm over sets of dyadic rationals. The resulting matrices allow for
multiplication-free computations requiring only addition and bit-shifting
operations. Such low-complexity structures pave the way for low-power,
efficient hardware designs. We applied our approach on three use cases of
different complexity: (i) a "light" but efficient ConvNet for face detection
(with around 1000 parameters); (ii) another one for hand-written digit
classification (with more than 180000 parameters); and (iii) a significantly
larger ConvNet: AlexNet with $\approx$1.2 million matrices. We evaluated the
overall performance on the respective tasks for different levels of
approximations. In all considered applications, very low-complexity
approximations have been derived maintaining an almost equal classification
performance.
