LFA Applied to CNNs: Efficient Singular Value Decomposition of Convolutional Mappings by Local Fourier Analysis
Antonia van Betteray2 • Karsten Kahl1 • Matthias Rottmann2
1 Department of Mathematics, University of Wuppertal, Wuppertal, Germany
2 Institute of Computer Science, University of Osnabrück, Osnabrück, Germany
Frontiers in Artificial Intelligence and Applications, Volume 413
ECAI 2025 doi: "10.3233/FAIA250793"
Abstract
The singular values of convolutional mappings encode interesting spectral properties, which can be used, e.g., to improve generalization and robustness of convolutional neural networks as well as to facilitate model compression. However, the computation of singular values is typically very resource-intensive. The naive approach involves unrolling the convolutional mapping along the input and channel dimensions into a large and sparse two-dimensional matrix, making the exact calculation of all singular values infeasible due to hardware limitations. In particular, this is true for matrices that represent convolutional mappings with large inputs and a high number of channels. Existing efficient methods leverage the Fast Fourier transformation (FFT) to transform convolutional mappings into the frequency domain, enabling the computation of singular values for matrices representing convolutions with larger input and channel dimensions. For a constant number of channels in a given convolution, an FFT can compute N singular values in O(N log N) complexity. In this work, we propose an approach of complexity O(N) based on local Fourier analysis, which additionally exploits the shift invariance of convolutional operators. We provide a theoretical analysis of our algorithm’s runtime and validate its efficiency through numerical experiments. Our results demonstrate that our proposed method is scalable and offers a practical solution to calculate the entire set of singular values – along with the corresponding singular vectors if needed – for high-dimensional convolutional mappings.
Motivation
Let $ A: \mathbb{R}^{m \times n \times c_{in}} \longrightarrow \mathbb{R}^{m \times n \times c_{out}} $a convolution mapping, i.e., a linear and translation-invariant transformation with $m, n$ spatial input dimension and $c_{in}$ and $c_{out}$ the respective number of input and output channels. The singular values of such a mapping reveals for example insights into regularization and robustness. However, the singular value decomposition is typically computed from matrices. In matrix representation, the convolution becomes a large sparse banded matrix, cf., Fig. 1(a). If $m = n$ and $c = c_{in} = c_{out}$ the computation complexity to compute the SVD of the convolution matrix is $\mathcal{O}(n^6c^3)$. It is easy to see, that this explicit SVD computation becomes infeasible.
Matrix representation of $3 \times 3$ convolution on $m \times n$ input.
Matrix composed of $m \cdot n$ blocks of size $c_{in} \times c_{out}$
⠀
Method Overview
To efficiently compute the SVD for large convolution mappings for large input and channel dimensions, we exploit the translation-invariance by using local Fourier analysis, which is a method developed for the analysis of iterative solvers. We make use of the convolution theorem, that states, that convolutions diagonalize under Fourier transform. In particular, by the application of a Fourier transform, the convolution becomes a block-diagonal operator and instead of computing the SVD from the large sparse matrix, the SVD can be computed from the smaller, independent block matrices.
A related approach is based on FFT and requires a complexity of $\mathcal{O}(n^2c^2(c + \log n))$. By exploiting the translation-invariance of the convolution operator, our approach requires only a complexity of $\mathcal{O}(n^2 c^3)$, which is asymptotically optimal with respect to the input dimension.
To formalize this, we express convolutional mappings as multiplication operators. To that end, we assume periodic boundary conditions, which corresponds to an infinite repetition of the input across space. Furthermore, the convolution acts on a local neighborhood $\mathcal{N}$, e.g., a $3 \times 3$ kernel centered around a spatial coordinate $x$, cf. Fig. 2)
Figure 2: $3 \times 3$ kernel neighborhood centered around $x$.
Collecting all coupled input and output channels corresponding to each neighboorhood $\delta \in \mathcal{N}$ location yields a matrix $ M_A^{(\delta)} \in \mathbb{R}^{c_{out}} \times \mathbb{R}^{c_{in}}.$ With that the convolution of $A$ with an input $f$ evaluated at $x$ can be written as a multiplication operator $ (A *f)(x) = \sum_{\delta \in \mathcal{N}} M_A^{(\delta)} \cdot f(x + \delta). $ To apply the convolution theorem, we choose the Fourier mode $f_k = e^{2 \pi \mathtt{i} \langle k, x \rangle}$ as ansatz function, with $k$ denoting a frequency. The convolution of $A$ with $f_k$ reduces to $ (A \ast f_k)(x) = \sum_{\delta \in \mathcal{N}} M^{(\delta)}_{A} \cdot e^{2 \pi \mathtt{i} \langle k, x + \delta \rangle} = \underbrace{\left( \sum_{\delta \in \mathcal{N}} M^{(\delta)}_{A} \cdot e^{2 \pi \mathtt{i} \langle k, \delta \rangle} \right)}_{A_k} e^{2 \pi \mathtt{i} \langle k, x \rangle} = A_k \cdot f_k, $ i.e., a matrix vector multiplication.
For each frequency $k$ we obtain a symbol matrix $A_k \in \mathbb{C}^{c_{out} \times c_{in}}$ and thus the convolution becomes a block diagonal operator. With that, the SVD can now be computed from each matrix $A_k$ independently as $ A_k = U_k \Sigma_k V^*_k, $ where $U_k, V_k^*$ are unitary matrices containing the singular vectors and $\Sigma_k$ is diagonal with singular values as entries.
To that end the SVD by LFA can be viewed as a two-staged diagonalization
1. (Block-) Diagonalization by Fourier transform
2. Diagonalization of the block-diagonal matrix by SVD
This process based on local Fourier analysis is summarized in the following algorithm.
Consequently, the overall complexity to compute the SVD by LFA requires only a complexity $\mathcal{O}(n^2 c^3)$, in the case of a square input.
Qualitative Results
Execution runtime
Besides the analysis of the computational complexity we study the execution runtime in seconds ($s$) for different input sizes $n$. The number of channels is fixed to $16$ for in- and output channels. We begin by comparing the runtimes of the explicit computation and the Fourier-based computations in Figure 3. For the computation of the explicit SVD we observe that the runtime grows rapidly with increasing input size. The maximum tractable size we were able to decompose was an input of $64 \times 64$. The computation of the corresponding $\approx 65$ thousand singular values took around 14 hours. On the other hand, the SVDs by Fourier-based approaches scale better. At $n=64$ the computation of $\approx 65$ thousand singular values takes only $\approx 0.1$ seconds. For very small input sizes, i.e., $n=4$, the FFT-based approach is slightly faster. When increasing the input dimension, our LFA-based approach becomes dominant. For example for an input of size $512 \times 512$ our LFA-based approach is about $14.5 \%$ faster. Furthermore, we observe, that Fourier-based approaches are scalable to very large input dimensions, as illustrated in Figure 3(b). As the input size increases, our LFA-based approach scales better than the FFT-based approach. For example at $n = 2^{14}$, which corresponds to the computation of $4$ billion singular values. With the FFT-based approach the compuation of $4$ billion singular values takes approximatively $3$ hours, with our LFA-based approach we obtain the same singular values in approximatevly $2$ hours. This corresponds to an improvement of $30.6\%$. Figure 3(a): Runtimes to compute SVD for input sizes $n \in \{4,8,16, \ldots, 512\}$ comparing the explixit computation and FFT-based computations. The number of channels is fixed to $16$ for input and output channel dimension respectively. Both axes are log-scaled. Figure 3(b): Runtimes to compute the SVD for inputs with $n \in \{2^i | i \in 8, 10, \ldots, 14\}$. The number if channels is fixed to $16$ and the $x$-axis is log-scaled.
Figure 3 (a)
Figure 3 (b)
Effect of boundary conditions
In order to enable diagonalization in the Fourier-domain, we assumed periodic boundary conditions. However, in CNNs, typically Dirichelt boundary conditions, i.e., zero padding, is applied. To this end, we studied the effect of boundary conditions on the singular values in Figure 4. Figure 4 "Effect on Dirichlet and periodic boundary conditions on the Singular values for input sizes in $n$ For small $n$ the boundary effects dominate, as the singular values differ noticeably. Nevertheless, as the input dimension increases, the influence becomes negligible and consequently, the computation by LFA remains accurate for large input feature maps in practical applications.
Figure 4
Memory layout
Additionally, in our experiments we observed, that our LFA-based implementation yields an memory layout, which allows for a faster computation of the subsequent SVD by a standard routine such as $\mathtt{NumPy}$.
Resources & Links
Acknowledgments
* This work is partially supported by the German Federal Ministry for Eco-
nomic Affairs and Climate Action, within the project “KI Delta Learning”
(grant no. 19A19013Q) and partially supported by the German Federal Ministry of Research and Technology and Space.
∗∗ M.R. acknowledges support by the German Federal Ministry of Education
and Research within the junior research group project “UnrEAL” (grant no.
01IS22069).
∗∗∗ The contribution of K.K. is partially funded by the European Union’s
HORIZON MSCA Doctoral Networks programme project AQTIVATE (grant
no. 101072344)
Citation
@inproceedings{vanBetteray2025LFA,
author = {Antonia van Betteray and Matthias Rottmann and Karsten Kahl},
title = {LFA Applied to CNNs: Efficient Singular Value Decomposition of Convolutional Mappings by Local Fourier Analysis},
booktitle = {Frontiers in Artificial Intelligence and Applications, Volume 413: ECAI 2025},
pages = {90--97},
year = {2025},
doi = {10.3233/FAIA250793},
publisher = {IOS Press} }
Contact
Have questions or want to collaborate? Reach out: