  We present a new approach for nonlocal image denoising, based around the
application of an unnormalized extended Gaussian ANOVA kernel within a bilevel
optimization algorithm. A critical bottleneck when solving such problems for
finely-resolved images is the solution of huge-scale, dense linear systems
arising from the minimization of an energy term. We tackle this using a Krylov
subspace approach, with a Nonequispaced Fast Fourier Transform utilized to
approximate matrix-vector products in a matrix-free manner. We accelerate the
algorithm using a novel change of basis approach to account for the (known)
smallest eigenvalue-eigenvector pair of the matrices involved, coupled with a
simple but frequently very effective diagonal preconditioning approach. We
present a number of theoretical results concerning the eigenvalues and
predicted convergence behavior, and a range of numerical experiments which
validate our solvers and use them to tackle parameter learning problems. These
demonstrate that very large problems may be effectively and rapidly denoised
with very low storage requirements on a computer.
