# Parallel Backpropagation for Inverse of a Convolution with Application to Normalizing Flows

arXiv: https://arxiv.org/abs/2410.14634 · HTML: https://mlsanity.com/paper/2410.14634/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 29 references that are in the map.
- First posted on arXiv 18 Oct 2024.

## Builds on (most cited first, 17 of 17)

- [Flow Matching for Generative Modeling](https://mlsanity.com/paper/2210.02747/) (2022)
- [Large Scale GAN Training for High Fidelity Natural Image Synthesis](https://mlsanity.com/paper/1809.11096/) (2018)
- [Density estimation using Real NVP](https://mlsanity.com/paper/1605.08803/) (2016)
- [Glow: Generative Flow with Invertible 1x1 Convolutions](https://mlsanity.com/paper/1807.03039/) (2018)
- [Normalizing Flows for Probabilistic Modeling and Inference](https://mlsanity.com/paper/1912.02762/) (2019)
- [Masked Autoregressive Flow for Density Estimation](https://mlsanity.com/paper/1705.07057/) (2017)
- [Improving Variational Inference with Inverse Autoregressive Flow](https://mlsanity.com/paper/1606.04934/) (2016)
- [Neural Spline Flows](https://mlsanity.com/paper/1906.04032/) (2019)
- [Invertible Residual Networks](https://mlsanity.com/paper/1811.00995/) (2018)
- [MoFlow: An Invertible Flow Model for Generating Molecular Graphs](https://mlsanity.com/paper/2006.10137/) (2020)
- [MaCow: Masked Convolutional Generative Flow](https://mlsanity.com/paper/1902.04208/) (2019)
- [Emerging Convolutions for Generative Normalizing Flows](https://mlsanity.com/paper/1901.11137/) (2019)
- [End-to-end Interpretable Learning of Non-blind Image Deblurring](https://mlsanity.com/paper/2007.01769/) (2020)
- [Self Normalizing Flows](https://mlsanity.com/paper/2011.07248/) (2020)
- [ButterflyFlow: Building Invertible Layers with Butterfly Matrices](https://mlsanity.com/paper/2209.13774/) (2022)
- [CInC Flow: Characterizable Invertible 3x3 Convolution](https://mlsanity.com/paper/2107.01358/) (2021)
- [FInC Flow: Fast and Invertible k × k Convolutions for Normalizing Flows](https://mlsanity.com/paper/2301.09266/) (2023)

## Abstract (arXiv)

The inverse of an invertible convolution is an important operation that comes up in Normalizing Flows, Image Deblurring, etc. The naive algorithm for backpropagation of this operation using Gaussian elimination has running time O(n3) where n is the number of pixels in the image. We give a fast parallel backpropagation algorithm with running time O(√n) for a square image and provide a GPU implementation of the same. Inverse of Convolutions are usually used in Normalizing Flows in the sampling pass, making them slow. We propose to use the Inverse of Convolutions in the forward (image to latent vector) pass of the Normalizing flow. Since the sampling pass is the inverse of the forward pass, it will use convolutions only, resulting in efficient sampling times. We use our parallel backpropagation algorithm to optimize the inverse of the convolution layer, resulting in fast training times. We implement this approach in various Normalizing Flow backbones, resulting in our Inverse-Flow models. We benchmark Inverse-Flow on standard datasets and show significantly improved sampling times with similar bits per dimension compared to previous models.