Multiscale scattered data analysis in samplet coordinates

• URL: http://arxiv.org/abs/2409.14791v1
• Date: Mon, 23 Sep 2024 08:07:47 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. We suggest to represent the resulting generalized Vandermonde matrices in samplet coordinates. We prove that the condition numbers of the linear systems at each level remain bounded independent of the particular level.
• 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 a 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 employed to capture varying levels of detail. To apply this approach to large data sets, we suggest to represent the resulting generalized Vandermonde matrices 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 geometrically decreasing dimension, the full multiscale system can be assembled with cost $\mathcal{O}(N \log N)$. We prove that the condition numbers of the linear systems at each level remain bounded independent of the particular level, allowing us to use an iterative solver with a bounded number of iterations for the numerical solution. Hence, the overall cost of the proposed approach is $\mathcal{O}(N \log N)$. The theoretical findings are accompanied by extensive numerical studies in two and three spatial dimensions.

Related papers

• 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)
• 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)
• 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)
• 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)

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.