Source-linked AI summary
Structured Transforms for Small-Footprint Deep Learning
Vikas Sindhwani, Tara N. Sainath, Sanjiv Kumar
TL;DR
The paper addresses deploying deep-learning pipelines on mobile devices constrained by storage and power. It learns generalized structured parameter matrices through low displacement rank, yielding fast computation and tunable sharing. Experiments report favorable accuracy–compactness–speed tradeoffs, including strong keyword-spotting performance with more than 3.5-fold compression.
Problem
Dense deep-learning parameter matrices are costly to store and multiply, limiting deployment on storage- and power-constrained mobile devices.
Method
The paper learns generalized structured parameter matrices characterized by low displacement rank, with tunable statistical capacity between structured and unstructured configurations.
Results
More than 3.5-fold compression is reported in mobile keyword spotting while nearly retaining state-of-the-art performance and outperforming standard linear low-rank bottleneck layers.
Takeaways & Limitations
Structured transforms provide favorable accuracy–compactness–speed tradeoffs and can accelerate inference and forward/backward training passes.
Abstract
from arXiv · showhide
We consider the task of building compact deep learning pipelines suitable for deployment on storage and power constrained mobile devices. We propose a unified framework to learn a broad family of structured parameter matrices that are characterized by the notion of low displacement rank. Our structured transforms admit fast function and gradient evaluation, and span a rich range of parameter sharing configurations whose statistical modeling capacity can be explicitly tuned along a continuum from structured to unstructured. Experimental results show that these transforms can significantly accelerate inference and forward/backward passes during training, and offer superior accuracy-compactness-speed tradeoffs in comparison to a number of existing techniques. In keyword spotting applications in mobile speech recognition, our methods are much more effective than standard linear low-rank bottleneck layers and nearly retain the performance of state of the art models, while providing more than 3.5-fold compression.
1 Introduction
The paper targets compact deep-learning transforms for resource-constrained mobile deployment. It unifies structured matrices through low displacement rank, enabling tunable parameter sharing and fast computation.
- Motivation: Dense parameter matrices can make mobile deployment prohibitive because they require mn storage and O(mn) matrix-vector computation.The constraint is especially relevant to always-on keyword spotting and onboard video processing on low-power hardware.
- Motivation: Structured matrices reduce parameter counts while aiming to accelerate inference and training through fast matrix-vector products and gradient computations.The paper contrasts this goal with low-rankness, sparsity, random weights, low precision, parameter sharing, and distillation.
- Structured matrices: Toeplitz and Hankel matrices encode diagonal or anti-diagonal sharing and are closely related to one-dimensional discrete convolutions.Vandermonde and Cauchy matrices arise naturally in polynomial and rational interpolation.
- Displacement rank: Low displacement rank unifies diverse structured matrix classes by mapping them through class-specific operators to matrices whose rank is far below min(m, n).The approach extends to generalized matrices formed from combinations of structured matrices and inverses, with displacement rank controlling their structure.
- Contribution: The proposed transforms use generalized low-displacement-rank parameter matrices with fast multiplication and gradient computation, while tuning modeling capacity from structured to unstructured.The framework focuses on Toeplitz-related transforms but is intended to extend to other structured matrix generalizations.
2 Displacement Operators associated with Structured Matrices
Displacement operators expose shared structure by transforming matrix classes into low-rank representations. The paper specializes this framework to Toeplitz-like matrices and parameterizes them through low-displacement generators.
- Displacement operators: The Sylvester displacement operator is defined as ∇A,B[M] = AM − MB for fixed operator matrices A and B.The related Stein operator is introduced separately, and operator choices determine useful structured-matrix properties.
- Operator matrices: An f-unit-circulant matrix shifts vector entries downward while scaling the last entry by f before moving it to the top.The cases f = 1 and f = −1 yield circulant and skew-circulant matrices, respectively.
- Figures: Figure 1 compares displacement ranks across structured classes, while Figure 2 illustrates the low-rank transformation for a 4 × 4 Toeplitz matrix.The operator matrices are selected as diagonal and/or f-unit-circulant matrices.
- Generalized structure: Allowing rank(L(M)) ≤ r generalizes structured matrix classes into Toeplitz-like, Vandermonde-like, and Cauchy-like families.Low-rank factors G and H serve as displacement generators, and fast numerical linear algebra extends to these broader classes.
- Toeplitz-like matrices: The paper focuses on Toeplitz-like matrices characterized by the Sylvester operator ∇Z1,Z−1.The resulting parameterizations involve Krylov matrices generated by f-circulant matrices.
3 Learning Toeplitz-like Structured Transforms
The framework learns Toeplitz-like structured transforms through displacement factors, covering matrix classes from highly structured transforms to arbitrary dense matrices. These transforms support fast multiplication and gradient computation, including efficient minibatch implementations and rectangular variants.
- Representational capacity: Displacement factors G and H parameterize a rich family that includes structured matrices, Toeplitz products and inverses, linear combinations, and all n × n matrices when r = n.The listed inclusions show that increasing displacement rank expands the representable matrix class.
- Representational capacity: The displacement rank r controls the structure–capacity trade-off: low-r matrices are compact and highly structured, whereas high-r matrices approach unstructured dense matrices.At r = 1 or 2, the transforms also search over convolutional transforms, generalizing one-dimensional convolutional layers.
- Fast evaluation: Circulant and skew-circulant factors enable matrix-vector multiplication in O(n log n) time through the Fast Fourier transform.The multiplication uses diagonalization of f-circulant matrices and an FFT-based expression for the transform.
- Fast evaluation: 2(rb + r + b) FFTs compute a minibatch matrix-matrix product for a rank-r sum of circulant and skew-circulant products, instead of 6rb FFTs naively.The reduction shares transformed parameters, inputs, and the final inverse FFT across terms and minibatch vectors.
- Rectangular transforms: Rectangular transforms can use rectangular analogues of the representation theorems or derive rectangular outputs by subsampling or stacking square-transform outputs.For m < n, the approach subsamples outputs; for m > n, it can stack outputs when m is a multiple of n.
4 Empirical Studies
Experiments evaluate structured transforms for acceleration, compact neural-network learning, and mobile keyword spotting. Toeplitz-like transforms achieve strong accuracy–compactness–speed tradeoffs across these settings.
- Acceleration: Figure 3 evaluates inference, minibatch training, and gradient speedups for Circulant and Toeplitz-like transforms relative to dense matrices.The study varies displacement rank and transform dimension on random datasets.
- Compact neural networks: The compact-network experiments compare Toeplitz-like hidden-layer weights with Random Edge Removal, Low-rank Decomposition, reduced-size networks, Dark Knowledge, and HashedNets.The comparisons replicate the HashedNets experimental setting across image-classification datasets.
- Compact neural networks: Toeplitz-like structured transforms outperform all competing approaches on every image dataset, with similar or drastically fewer parameters.HashedNets parameter sharing does not provide FFT-like O(n log n) multiplication, while distillation can complement the proposed approach.
- Mobile speech recognition: At 1 false alarm per hour, a 3348-parameter displacement rank=1 Toeplitz-like transform reaches about 8.2% false rejects, versus 10.2% for Circulant and 14.2% for Fastfood.A displacement rank 10 model reaches 6.2% false rejects versus 6.8% for a three-times-larger rank=32 bottleneck.
- Mobile speech recognition: The best Toeplitz-like model comes within 0.4% of fully-connected and reference models that are respectively 80-times and 3.6-times larger.Models with displacement ranks 1, 2, and 10 also come within 0.2% accuracy while offering better accuracy–time tradeoffs than listed baselines.
5 Perspective
The paper presents structured-matrix parsimony as a foundation for compact deep learning and points toward broader structured-transform generalizations. It identifies Block and multi-level Toeplitz-like matrices as extensions related to multidimensional convolution.
- The paper introduces parsimony notions rooted in structured-matrix theory and demonstrates their effectiveness.
- The framework can extend to Block and multi-level Toeplitz-like matrices related to multidimensional convolution.The authors suggest these extensions might lead to new generalizations of Convolutional Neural Networks.
- The proposed perspective connects structured transforms with possible future generalizations of Convolutional Neural Networks.