Scalable Operator Learning via Nystr\"om Approximation With Denoising Applications

2026-06-26 · Source: stat.ML updates on arXiv.org · Field: Technology & Digital — Artificial Intelligence & Machine Learning, Data Science & Analytics · Depth: Expert, extended

Summary

The article introduces a scalable operator learning algorithm utilizing Nyström subsampling for vector-valued regression within reproducing kernel Hilbert spaces (vRKHS). This method addresses the significant computational and memory costs (O(n^3) time, O(n^2) memory) of traditional kernel methods, reducing them to O(nm^2) time and O(nm) memory, while supporting infinite-dimensional outputs. It establishes minimax-optimal convergence rates under general source conditions. The framework is applied to various denoising problems, including offline and real-time audio denoising, image denoising (motion blur and Gaussian noise), inverse Radon transform reconstruction, and energy-efficiency prediction. Numerical experiments, conducted on a MacBook Air with an Apple M4 processor, demonstrate that the proposed Nyström-based approach achieves performance comparable to full kernel methods and often outperforms wavelet-based and SVD-based baselines, with substantial computational savings.

Key takeaway

For Machine Learning Engineers evaluating scalable kernel methods for functional output prediction, you should consider Nyström subsampling. This approach significantly reduces computational complexity from O(n^3) to O(nm^2) and memory from O(n^2) to O(nm), making kernel methods viable for large datasets. You can apply this to real-time audio denoising, image reconstruction, or inverse problems, achieving comparable accuracy to full kernel methods with substantial efficiency gains.

Key insights

Nyström subsampling scales operator learning in vRKHS, achieving optimal convergence and efficient functional output prediction.

Principles

• Kernel methods face O(n^3) computational complexity.
• Nyström approximation reduces complexity to O(nm^2).
• General source conditions enable minimax-optimal convergence rates.

Method

The Nyström method constructs a low-rank kernel approximation from 'm' subsample points, minimizing empirical risk in a smaller vRKHS subspace for functional outputs.

In practice

• Apply to real-time audio denoising.
• Use for inverse Radon transform reconstruction.
• Predict building energy loads from features.

Topics

• Operator Learning
• Nyström Approximation
• Vector-valued RKHS
• Signal Denoising
• Image Denoising
• Inverse Radon Transform
• Kernel Methods

Best for: Computer Vision Engineer, AI Scientist, Machine Learning Engineer, Research Scientist

Related on AIssential

• Analysis of Nystrom method with sequential ridge leverage scores — INK-Estimate provides a single-pass, space-efficient sequential Nyström approximation with strong, continuous KRR solution guarantees.
• Fourier Neural Operators with rank-1 lattice points and hyperbolic cross — Replacing FNO's tensor product grids with rank-1 lattices and hyperbolic cross improves efficiency and accuracy using fewer resources.
• Attention at the Theoretical Minimum: A Mathematics of Arrays Framework for Memory-Optimal Transformer Kernels — A Mathematics of Arrays framework algebraically minimizes Transformer attention memory traffic, projecting significant speedup and energy reduction for AI kernels.
• State-of-art minibatches via novel DPP kernels: discretization, wavelets, and rough objectives — Wavelet-based DPPs and a novel discretization pipeline significantly enhance minibatch and coreset sampling efficiency for diverse ML tasks.
• Guaranteed Nonconvex Low-Rank Tensor Estimation via Scaled Gradient Descent — ScaledGD offers provably fast, condition-number-independent convergence for low-rank tensor estimation using t-SVD.
• SP$^3$: Spherical Priors for Plug-and-Play Restoration — Spherical Encoders can replace denoisers in Plug-and-Play image restoration for faster, high-quality results.

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by stat.ML updates on arXiv.org.