Associated data and code

The files in this code repository are commented versions of the code used for the following work:

Efficient nonlocal linear image denoising: Bilevel optimisation with Nonequispaced Fast Fourier Transform and matrix-free preconditioning by Andrés Miniguano-Trujillo, John Pearson, Ben Goddard.

Main files in this repository

• ReadMe.md: This file.
• The Outputs subfolder contains all the plots generated by each test except for figures 8 and 9.
• The Images contains all the images used to test our proposed method, the scalings used, and the denoising outputs. The Catset subfolder contains pictures of different cats kindly provided by Bernhard Heinzelreiter (Maxwell Institute for Mathematical Sciences), Jennifer Buchberger, Belen Santacruz Reyes, and Alejandro Saenz Ortega.

Jupyter notebooks with code for all the results are included.

1. Figure 2 compares the eigenvalues of the original and preconditioned systems as well as the resulting condition number for different values of $\sigma$. See notebook Eigs plots - Main.ipynb for the main panels, Eigs plots - Small sigma.ipynb for an additional computational study when $\sigma < 10$, and Eig plots - Several images.ipynb for a test on the computational bounds around the spectra.

2. Figure 3 compares the eigenvalues of $\mathsf{P}^{-1}{\mathsf{a}} A$ and $\mathsf{P}^{-1}{\mathsf{b}} A$ for $\lambda = 10^{-9}$. See notebook Eigs plots - Main.ipynb.

3. Figure 3 compares the eigenvalues of $\mathsf{P}^{-1}{\mathsf{a}} A$, $\pi_2 ( \mathsf{D}^{-1}{\mathsf{a},, X} \mathsf{A}X)$, $\mathsf{P}^{-1}{\mathsf{b}} A$, and $\pi_2 ( \mathsf{D}^{-1}_{\mathsf{b},, X} \mathsf{A}_X)$. for $\lambda = 10^{-9}$. See notebook Eigs plots - Main.ipynb.

4. Table 1 is a time comparison of setting up a kernel via a NFFT--based fast summation method versus computing the kernel exactly as the dimension grows. See notebook Size times.ipynb

5. Table 2 is a time comparison for solving the nonlocal system without preconditioning, where the nonlocal operator (\Gamma) is either given by the NFFT--based fast summation method or by exact kernel computation. See notebook Unprec solve times.ipynb.

6. Table 6 displays the number of CG iterations for different regularisation values and each choice of preconditioner when solving the nonlocal system via the NFFT--based fast summation method. See notebook CG - All preconditioners.ipynb.

7. Figure 7 is a comparative display of the number of CG iterations for different regularisation values $\lambda \in \Lambda$ and each choice of preconditioner. See notebook CG - All preconditioners.ipynb. The selected image corresponds to $n=775$ as it showcases many methods still working for not to small $\lambda$.

8. Figures 8 and 9 display the results of the batch training using bilevel optimisation on the included dataset. See notebook Scalar Training - ParaCats.ipynb.

---

Dependencies

We use the following standard libraries: NumPy 1.23.0, Pandas 1.4.2, SciPy 1.11.1

A copy of the NFFT4ANOVA library by Theresa Wagner (TU Chemnitz) is included in the folder. It depends on the FastAdjacency package by Dominik Alfke and the Julia interface of the NFFT3 library. Refer to FastAdjacency for a comprehensive set of installation instructions.

For better visualisation of the notebooks, the codefolding for Jupyter extension is recommended.