CDFlow: Building Invertible Layers with Circulant and Diagonal Matrices

AI summary

Overview

Research area: Deep generative modeling — specifically normalizing flows and the design of invertible linear layers.

Technical level: Intermediate. The paper assumes familiarity with normalizing flows, Jacobian determinants, the change-of-variables formula, and basic linear algebra (matrix inversion, determinants, the discrete Fourier transform).

Scope: The paper proposes a single structured linear layer built from alternating circulant and diagonal matrices, proves it reduces parameter and computational complexity, and evaluates it as the linear component of a multi-scale flow model (CDFlow) on image density estimation, periodic imagery, and runtime benchmarks.

What This Paper Is About

Normalizing flows generate data by pushing samples through invertible transformations, and they need two expensive operations to be fast: computing the log-determinant of the Jacobian (for training) and inverting the weight matrix (for sampling). Most prior work optimizes only the determinant while leaving inversion at roughly quadratic cost, and dense linear layers cost O(n²) parameters. This paper asks whether a weight matrix written as a product of circulant and diagonal matrices can approximate arbitrary linear transformations while making both the determinant and the inverse cheap, using the Fast Fourier Transform (FFT).

Key Contributions

1. A new invertible linear layer and flow model (CDFlow). The CD-Convolution layer represents its weight matrix as an alternating product of m diagonal matrices and m−1 circulant matrices, requiring storage that scales linearly with input dimension rather than quadratically.

2. Provable complexity reductions. Parameter complexity drops from O(n²) to O(mn); matrix inversion drops from O(n³) to O(mn log n); log-determinant drops from O(n³) to O(mn), where n is the input dimension. A single O(n log n) FFT at initialization precomputes the eigenvalues of circulant matrices, enabling O(n) log-determinant evaluation at runtime.

3. Demonstrated accuracy on image density estimation. CDFlow outperforms Glow, Emerging, Woodbury, and ButterflyFlow — all sharing the same modeling framework — and performs comparably to Residual Flows and i-DenseNet, on CIFAR-10 and ImageNet 32×32, measured in bits per dimension (BPD).

4. Demonstrated strength on periodic data and measured runtime speedups. On the Galaxy dataset CDFlow beats all compared models, and it speeds up matrix inverse by 1.17× and log-determinant by 4.31× relative to a general dense matrix at 96 channels.

Main Findings

• CIFAR-10 density estimation: CDFlow (44.2M parameters) reaches 3.31 ± 0.004 BPD, beating Glow (44.2M, 3.36 ± 0.002), Emerging (46.6M, 3.34 ± 0.002), Woodbury (45.3M, 3.42 ± 0.002), and ButterflyFlow (44.4M, 3.33 ± 0.003). Lower BPD is better. Residual Flows (3.28) and i-DenseNet (3.25) score lower.

• ImageNet 32×32 density estimation: CDFlow (44.2M) reaches 4.04 BPD, compared with 4.09 for Glow, Emerging, Woodbury, and ButterflyFlow, 4.01 for Residual Flows, 3.98 for i-DenseNet, 4.05 for i-ResNet, and 4.28 for Real NVP.

• Third reported data column: The paper's Table 2 is captioned for CIFAR-10, ImageNet 32×32, and Galaxy, while the column itself is labeled CIFAR-100. Values reported there include Real NVP 2.11, Glow 2.02, Emerging 1.98, ButterflyFlow 1.95, i-ResNet 2.04, Woodbury 2.01, Residual Flows 3.60, i-DenseNet 4.06, and CDFlow 1.92.

• Periodic/structured data: On the Galaxy dataset — described as 3,000 merged galaxies and 5,000 non-merged galaxies in the training and test sets — CDFlow outperforms all other models, achieving a 4.95% improvement in BPD compared to Glow.

• Runtime speedups: Compared to a general dense matrix at 96 channels, the method speeds up matrix inversion by 1.17× and log-determinant computation by 4.31×.

• Log-determinant scaling: Across channel sizes from 16 to 1024, log-determinant computation time stays consistent across different m values, between 0.095 ms and 0.097 ms.

• Hyperparameter m: Increasing m on CIFAR-10 gives only marginal BPD improvement while significantly increasing CD-Convolution parameter count. The default is m = 2 (two diagonal vectors and one circulant vector).

• Inverse vs. spatial size: The method outperforms 1×1 convolution at small spatial sizes in inverse computation but becomes slightly less efficient at larger spatial sizes, because it mainly reduces channel-wise rather than spatial complexity. It still clearly beats all baselines except 1×1 convolution.

• Forward pass: All baseline methods are slower than 1×1 convolution in forward runtime, while CDFlow is faster still. Periodic convolution suffers sharp runtime increases with more channels due to memory overhead from two-dimensional FFTs.

• Expressive power versus full matrices (Appendix A): In a reproduction of an earlier experiment comparing F-type (full matrix), L-type, U-type, LU-type, and the proposed DCD-type layers, the F-type achieves the lowest negative log-likelihood. DCD achieves second-best, outperforming the LU-type design.

• Flow Matching generalization (Appendix C): Replacing the linear layers of a 5-layer MLP in a Flow Matching framework on three 2D toy datasets (Chessboard, Moons, Circles), CDMLP uses 8.45K parameters — far fewer than MLP at 791.0K, EMLP at 1577.5K, WMLP at 40.5K, or BFMLP at 26.1K. It attains the lowest NLL on Chessboard (7.0425) and Circles, and the best MSE and FID on Moons (1.842 and 0.0016, the latter tied with WMLP).

Methodology in Plain English

The starting point is a known linear algebra result: any matrix in R^(n×n) can be written as an alternating product of circulant and diagonal matrices using no more than 2n−1 factors. The authors truncate this idea to m diagonal matrices and m−1 circulant matrices, and make that product the weight matrix of the flow's linear layer.

Two properties make this practical. First, a circulant matrix can be diagonalized by the discrete Fourier transform matrix: C = F⁻¹ diag(ĉ) F. Second, the determinant of a matrix product is the product of determinants, and the determinant of a diagonal-matrix-like object is just the product of its entries. Chaining these together turns the log-determinant of the whole weight matrix into a simple double summation over the diagonal entries and the circulant eigenvalues — this is what brings the cost down to O(mn). Because the eigenvalues of each circulant matrix depend only on the layer's own parameters, they are computed once at initialization with a single O(n log n) FFT and reused at runtime.

For inversion, diagonal matrices invert by taking reciprocals of their entries, and circulant matrices invert by taking reciprocals of their Fourier eigenvalues. Inverting the full weight matrix therefore reduces to a sequence of matrix-vector products, which cost O(mn log n). The authors store the frequency-domain vectors ĉ rather than the real-valued circulant vectors c to save computation in matrix-vector products, determinant, and inversion.

The resulting model, CDFlow, stacks flow modules of ActNorm, CD-Convolution, and a coupling layer, grouped into L blocks of K stacked modules, inside a multi-scale architecture with split and squeeze operations. Experiments use three blocks and 32 flow steps on standard image datasets, and a lighter two blocks and eight flow steps on the structured dataset; Woodbury uses d_s = d_c = 16 and ButterflyFlow uses butterfly level 1. Training uses spectral normalization on convolutional layers, with the maximum singular value efficiently computed from the circulant/diagonal structure, plus channel-aware learning rate scaling for the CD-Convolution parameters. Experiments ran on NVIDIA A100 and RTX 4090 GPUs, with runtime benchmarks on an NVIDIA A800 GPU, averaged over 100 runs.

Why This Matters

Impact on research: The paper targets a real asymmetry in flow-based modeling — most structured-matrix work optimizes the Jacobian determinant for training but leaves sampling-time inversion at O(n²) or worse. By reducing inversion to O(mn log n) and determinant to O(mn) simultaneously, it offers a design point that is cheap on both ends. It also extends the growing line of work applying circulant/diagonal factorizations (previously used in deep neural networks and parameter-efficient fine-tuning) to the reversibility problem specifically.

Real-world applications:

• Generative modeling of images, where likelihood-based training and fast sampling both matter — the paper demonstrates this on CIFAR-10 and ImageNet 32×32.
• Modeling data with inherent periodicity, such as the astronomical galaxy imagery evaluated here, where scattered light sources sit against predominantly dark boundaries.
• Any generative or invertible pipeline that needs to run under memory or compute budgets, since the layer stores only diagonal vectors and circulant eigenvalue vectors instead of a full n×n matrix.
• Flow Matching and other continuous-time generative frameworks, where the paper shows reduced parameter counts on 2D toy problems with competitive NLL, MSE, and FID.

Industry relevance: Reduced parameter storage and faster inversion translate directly into lower memory footprint and faster sampling at inference — relevant for deploying generative models on constrained hardware, and for large-channel convolutional feature maps where dense weight matrices dominate cost. The paper's explicit comparison against optimized 1×1 convolutions, Woodbury, and butterfly layers frames the contribution in practical engineering terms.

Future Directions

• Extension to d×d convolutions. The paper states explicitly that a current limitation is the reliance on 1×1 convolution, and that future work will extend to d×d convolutions. This would also address the observed gap where the method loses ground to 1×1 convolution at large spatial sizes, since it currently reduces channel-wise complexity rather than spatial complexity.
• Closing the gap to fully learnable matrices. The Appendix A experiment shows the DCD-type layer places second behind the unconstrained F-type in NLL. Whether more factors, better parameterization, or different initialization can close that gap is left open.
• Tuning the trade-off in m. Increasing m improves approximation power only marginally on CIFAR-10 while raising parameter count and latency; a principled way to choose m per layer or per resolution is not established.
• Wider evaluation. The reported density estimation is limited to CIFAR-10, ImageNet 32×32, a column labeled CIFAR-100, and the Galaxy dataset, and the Flow Matching study is limited to three 2D toy datasets. Higher-resolution and larger-scale benchmarks are untested.

Target Audience

Researchers and graduate students working on normalizing flows, invertible neural networks, and likelihood-based generative models; practitioners who need structured, memory-efficient linear layers with cheap determinants and inverses; and engineers interested in structured-matrix approaches — circulant, diagonal, Woodbury, or butterfly factorizations — who want a concrete comparison of parameter counts, log-determinant cost, and inversion cost across methods. Readers without prior exposure to the change-of-variables formula or Fourier diagonalization of circulant matrices will need background reading first.

Authors’ abstract

Normalizing flows are deep generative models that enable efficient likelihood estimation and sampling through invertible transformations. A key challenge is to design linear layers that enhance expressiveness while maintaining efficient computation of the Jacobian determinant and inverse. We introduce a novel invertible linear layer based on the product of circulant and diagonal matrices. This decomposition reduces parameter complexity from $\mathcal{O}(n^2)$ to $\mathcal{O}(mn)$ using $m$ diagonal matrices and $m-1$ circulant matrices while still approximating general linear transformations. By leveraging the Fast Fourier Transform, our approach reduces the time complexity of matrix inversion from $\mathcal{O}(n^3)$ to $\mathcal{O}(mn\log n)$ and that of computing the log-determinant from $\mathcal{O}(n^3)$ to $\mathcal{O}(mn)$, where $n$ is the input dimension. We build upon this layer to develop Circulant-Diagonal Flow (CDFlow), which achieves strong density estimation on natural image datasets and effectively models data with inherent periodic structure. Furthermore, CDFlow significantly accelerates key operations in normalizing flows, providing practical benefits for scalable generative modeling.