Recent findings indicate that over-parametrization, while crucial forsuccessfully training deep neural networks, also introduces large amounts ofredundancy. Tensor methods have the potential to efficiently parametrizeover-complete representations by leveraging this redundancy. In this paper, wepropose to fully parametrize Convolutional Neural Networks (CNNs) with a singlehigh-order, low-rank tensor. Previous works on network tensorization havefocused on parametrizing individual layers (convolutional or fully connected)only, and perform the tensorization layer-by-layer separately. In contrast, wepropose to jointly capture the full structure of a neural network byparametrizing it with a single high-order tensor, the modes of which representeach of the architectural design parameters of the network (e.g. number ofconvolutional blocks, depth, number of stacks, input features, etc). Thisparametrization allows to regularize the whole network and drastically reducethe number of parameters. Our model is end-to-end trainable and the low-rankstructure imposed on the weight tensor acts as an implicit regularization. Westudy the case of networks with rich structure, namely Fully ConvolutionalNetworks (FCNs), which we propose to parametrize with a single 8th-ordertensor. We show that our approach can achieve superior performance with smallcompression rates, and attain high compression rates with negligible drop inaccuracy for the challenging task of human pose estimation.