  In this paper, we show that extending the butterfly operations from the FFT
algorithm to a general Butterfly Transform (BFT) can be beneficial in building
an efficient block structure for CNN designs. Pointwise convolutions, which we
refer to as channel fusions, are the main computational bottleneck in the
state-of-the-art efficient CNNs (e.g. MobileNets ). We introduce a set of
criteria for channel fusion and prove that BFT yields an asymptotically optimal
FLOP count with respect to these criteria. By replacing pointwise convolutions
with BFT, we reduce the computational complexity of these layers from O(n^2) to
O(n\log n) with respect to the number of channels. Our experimental evaluations
show that our method results in significant accuracy gains across a wide range
of network architectures, especially at low FLOP ranges. For example, BFT
results in up to a 6.75% absolute Top-1 improvement for MobileNetV1, 4.4 \% for
ShuffleNet V2 and 5.4% for MobileNetV3 on ImageNet under a similar number of
FLOPS. Notably, ShuffleNet-V2+BFT outperforms state-of-the-art architecture
search methods MNasNet, FBNet and MobilenetV3 in the low FLOP regime.
