Multiscale scattered data analysis in samplet coordinates

• URL: http://arxiv.org/abs/2409.14791v2
• Date: Sun, 16 Mar 2025 16:05:35 GMT
• Title: Multiscale scattered data analysis in samplet coordinates
• Authors: Sara Avesani, Rüdiger Kempf, Michael Multerer, Holger Wendland,
• Abstract summary: We study multiscale data scattered schemes for globally supported radial basis functions with focus on the Mat'ern class.<n>We prove that the condition numbers of the the diagonal blocks of the corresponding multiscale system remain bounded independently of the particular level.<n>We exploit this fact to derive a general error estimate bounding the consistency error issuing from a numerical approximation of the multiscale system.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study multiscale scattered data interpolation schemes for globally supported radial basis functions with focus on the Mat\'ern class. The multiscale approximation is constructed through a sequence of residual corrections, where radial basis functions with different lengthscale parameters are combined to capture varying levels of detail. We prove that the condition numbers of the the diagonal blocks of the corresponding multiscale system remain bounded independently of the particular level, allowing us to use an iterative solver with a bounded number of iterations for the numerical solution. Employing an appropriate diagonal scaling, the multiscale system becomes well conditioned. We exploit this fact to derive a general error estimate bounding the consistency error issuing from a numerical approximation of the multiscale system. To apply the multiscale approach to large data sets, we suggest to represent each level of the multiscale system in samplet coordinates. Samplets are localized, discrete signed measures exhibiting vanishing moments and allow for the sparse approximation of generalized Vandermonde matrices issuing from a vast class of radial basis functions. Given a quasi-uniform set of $N$ data sites, and local approximation spaces with exponentially decreasing dimension, the samplet compressed multiscale system can be assembled with cost $\mathcal{O}(N \log^2 N)$. The overall cost of the proposed approach is $\mathcal{O}(N \log^2 N)$. The theoretical findings are accompanied by extensive numerical studies in two and three spatial dimensions.

Related papers

• Gappy local conformal auto-encoders for heterogeneous data fusion: in praise of rigidity [6.1152340690876095]
  We propose an end-to-end computational pipeline in the form of a multiple-auto-encoder neural network architecture for this task. The inputs to the pipeline are several sets of partial observations, and the result is a globally consistent latent space, harmonizing (rigidifying, fusing) all measurements. We demonstrate the approach in a sequence of examples, starting with simple two-dimensional data sets and proceeding to a Wi-Fi localization problem.
  arXiv  Detail & Related papers  (2023-12-20T16:18:51Z)
• Polynomial-Time Solutions for ReLU Network Training: A Complexity Classification via Max-Cut and Zonotopes [70.52097560486683]
  We prove that the hardness of approximation of ReLU networks not only mirrors the complexity of the Max-Cut problem but also, in certain special cases, exactly corresponds to it. In particular, when $epsilonleqsqrt84/83-1approx 0.006$, we show that it is NP-hard to find an approximate global dataset of the ReLU network objective with relative error $epsilon$ with respect to the objective value.
  arXiv  Detail & Related papers  (2023-11-18T04:41:07Z)
• Multi-Grid Tensorized Fourier Neural Operator for High-Resolution PDEs [93.82811501035569]
  We introduce a new data efficient and highly parallelizable operator learning approach with reduced memory requirement and better generalization. MG-TFNO scales to large resolutions by leveraging local and global structures of full-scale, real-world phenomena. We demonstrate superior performance on the turbulent Navier-Stokes equations where we achieve less than half the error with over 150x compression.
  arXiv  Detail & Related papers  (2023-09-29T20:18:52Z)
• Samplet basis pursuit: Multiresolution scattered data approximation with sparsity constraints [0.0]
  We consider scattered data approximation in samplet coordinates with $ell_1$-regularization. By using the Riesz isometry, we embed samplets into reproducing kernel Hilbert spaces. We argue that the class of signals that are sparse with respect to the embedded samplet basis is considerably larger than the class of signals that are sparse with respect to the basis of kernel translates.
  arXiv  Detail & Related papers  (2023-06-16T21:20:49Z)
• Approximating a RUM from Distributions on k-Slates [88.32814292632675]
  We find a generalization-time algorithm that finds the RUM that best approximates the given distribution on average. Our theoretical result can also be made practical: we obtain a that is effective and scales to real-world datasets.
  arXiv  Detail & Related papers  (2023-05-22T17:43:34Z)
• Low-complexity subspace-descent over symmetric positive definite manifold [9.346050098365648]
  We develop low-complexity algorithms for the minimization of functions over the symmetric positive definite (SPD) manifold. The proposed approach utilizes carefully chosen subspaces that allow the update to be written as a product of the Cholesky factor of the iterate and a sparse matrix.
  arXiv  Detail & Related papers  (2023-05-03T11:11:46Z)
• Score-based Diffusion Models in Function Space [140.792362459734]
  Diffusion models have recently emerged as a powerful framework for generative modeling. We introduce a mathematically rigorous framework called Denoising Diffusion Operators (DDOs) for training diffusion models in function space. We show that the corresponding discretized algorithm generates accurate samples at a fixed cost independent of the data resolution.
  arXiv  Detail & Related papers  (2023-02-14T23:50:53Z)
• Bayesian Hyperbolic Multidimensional Scaling [2.5944208050492183]
  We propose a Bayesian approach to multidimensional scaling when the low-dimensional manifold is hyperbolic. A case-control likelihood approximation allows for efficient sampling from the posterior distribution in larger data settings. We evaluate the proposed method against state-of-the-art alternatives using simulations, canonical reference datasets, Indian village network data, and human gene expression data.
  arXiv  Detail & Related papers  (2022-10-26T23:34:30Z)
• Generalization Bounds for Stochastic Gradient Descent via Localized $\varepsilon$-Covers [16.618918548497223]
  We propose a new covering technique localized for the trajectories of SGD. This localization provides an algorithm-specific clustering measured by the bounds number. We derive these results in various contexts and improve the known state-of-the-art label rates.
  arXiv  Detail & Related papers  (2022-09-19T12:11:07Z)
• Super-resolution GANs of randomly-seeded fields [68.8204255655161]
  We propose a novel super-resolution generative adversarial network (GAN) framework to estimate field quantities from random sparse sensors. The algorithm exploits random sampling to provide incomplete views of the high-resolution underlying distributions. The proposed technique is tested on synthetic databases of fluid flow simulations, ocean surface temperature distributions measurements, and particle image velocimetry data.
  arXiv  Detail & Related papers  (2022-02-23T18:57:53Z)
• Local versions of sum-of-norms clustering [77.34726150561087]
  We show that our method can separate arbitrarily close balls in the ball model. We prove a quantitative bound on the error incurred in the clustering of disjoint connected sets.
  arXiv  Detail & Related papers  (2021-09-20T14:45:29Z)
• Square Root Bundle Adjustment for Large-Scale Reconstruction [56.44094187152862]
  We propose a new formulation for the bundle adjustment problem which relies on nullspace marginalization of landmark variables by QR decomposition. Our approach, which we call square root bundle adjustment, is algebraically equivalent to the commonly used Schur complement trick. We show in real-world experiments with the BAL datasets that even in single precision the proposed solver achieves on average equally accurate solutions.
  arXiv  Detail & Related papers  (2021-03-02T16:26:20Z)
• Multiscale regression on unknown manifolds [13.752772802705978]
  We construct low-dimensional coordinates on $mathcalM$ at multiple scales and perform multiscale regression by local fitting. We analyze the generalization error of our method by proving finite sample bounds in high probability on rich classes of priors. Our algorithm has quasilinear complexity in the sample size, with constants linear in $D$ and exponential in $d$.
  arXiv  Detail & Related papers  (2021-01-13T15:14:31Z)
• Optimal oracle inequalities for solving projected fixed-point equations [53.31620399640334]
  We study methods that use a collection of random observations to compute approximate solutions by searching over a known low-dimensional subspace of the Hilbert space. We show how our results precisely characterize the error of a class of temporal difference learning methods for the policy evaluation problem with linear function approximation.
  arXiv  Detail & Related papers  (2020-12-09T20:19:32Z)
• Linear-Sample Learning of Low-Rank Distributions [56.59844655107251]
  We show that learning $ktimes k$, rank-$r$, matrices to normalized $L_1$ distance requires $Omega(frackrepsilon2)$ samples. We propose an algorithm that uses $cal O(frackrepsilon2log2fracepsilon)$ samples, a number linear in the high dimension, and nearly linear in the matrices, typically low, rank proofs.
  arXiv  Detail & Related papers  (2020-09-30T19:10:32Z)
• Interpolation and Learning with Scale Dependent Kernels [91.41836461193488]
  We study the learning properties of nonparametric ridge-less least squares. We consider the common case of estimators defined by scale dependent kernels.
  arXiv  Detail & Related papers  (2020-06-17T16:43:37Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.