  The low displacement rank (LDR) framework for structured matrices represents
a matrix through two displacement operators and a low-rank residual. Existing
use of LDR matrices in deep learning has applied fixed displacement operators
encoding forms of shift invariance akin to convolutions. We introduce a class
of LDR matrices with more general displacement operators, and explicitly learn
over both the operators and the low-rank component. This class generalizes
several previous constructions while preserving compression and efficient
computation. We prove bounds on the VC dimension of multi-layer neural networks
with structured weight matrices and show empirically that our compact
parameterization can reduce the sample complexity of learning. When replacing
weight layers in fully-connected, convolutional, and recurrent neural networks
for image classification and language modeling tasks, our new classes exceed
the accuracy of existing compression approaches, and on some tasks also
outperform general unstructured layers while using more than 20x fewer
parameters.
