Signal reconstruction using determinantal sampling

• URL: http://arxiv.org/abs/2310.09437v2
• Date: Tue, 12 Nov 2024 04:57:25 GMT
• Title: Signal reconstruction using determinantal sampling
• Authors: Ayoub Belhadji, Rémi Bardenet, Pierre Chainais,
• Abstract summary: We study the approximation of a square-integrable function from a finite number of evaluations on a random set of nodes. We show that determinantal point processes and mixtures thereof can yield fast convergence rates.
• Score: 13.531952725283027
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the approximation of a square-integrable function from a finite number of evaluations on a random set of nodes according to a well-chosen distribution. This is particularly relevant when the function is assumed to belong to a reproducing kernel Hilbert space (RKHS). This work proposes to combine several natural finite-dimensional approximations based two possible probability distributions of nodes. These distributions are related to determinantal point processes, and use the kernel of the RKHS to favor RKHS-adapted regularity in the random design. While previous work on determinantal sampling relied on the RKHS norm, we prove mean-square guarantees in $L^2$ norm. We show that determinantal point processes and mixtures thereof can yield fast convergence rates. Our results also shed light on how the rate changes as more smoothness is assumed, a phenomenon known as superconvergence. Besides, determinantal sampling generalizes i.i.d. sampling from the Christoffel function which is standard in the literature. More importantly, determinantal sampling guarantees the so-called instance optimality property for a smaller number of function evaluations than i.i.d. sampling.

Related papers

• In-and-Out: Algorithmic Diffusion for Sampling Convex Bodies [7.70133333709347]
  We present a new random walk for uniformly sampling high-dimensional convex bodies. It achieves state-of-the-art runtime complexity with stronger guarantees on the output.
  arXiv  Detail & Related papers  (2024-05-02T16:15:46Z)
• Noise-Free Sampling Algorithms via Regularized Wasserstein Proximals [3.4240632942024685]
  We consider the problem of sampling from a distribution governed by a potential function. This work proposes an explicit score based MCMC method that is deterministic, resulting in a deterministic evolution for particles.
  arXiv  Detail & Related papers  (2023-08-28T23:51:33Z)
• Adaptive Annealed Importance Sampling with Constant Rate Progress [68.8204255655161]
  Annealed Importance Sampling (AIS) synthesizes weighted samples from an intractable distribution. We propose the Constant Rate AIS algorithm and its efficient implementation for $alpha$-divergences.
  arXiv  Detail & Related papers  (2023-06-27T08:15:28Z)
• MESSY Estimation: Maximum-Entropy based Stochastic and Symbolic densitY Estimation [4.014524824655106]
  MESSY estimation is a Maximum-Entropy based Gradient and Symbolic densitY estimation method. We construct a gradient-based drift-diffusion process that connects samples of the unknown distribution function to a guess symbolic expression. We find that the addition of a symbolic search for basis functions improves the accuracy of the estimation at a reasonable additional computational cost.
  arXiv  Detail & Related papers  (2023-06-07T03:28:47Z)
• Coefficient-based Regularized Distribution Regression [4.21768682940933]
  We consider the coefficient-based regularized distribution regression which aims to regress from probability measures to real-valued responses over a kernel reproducing Hilbert space (RKHS) Asymptotic behaviors of the algorithm in different regularity ranges of the regression function are comprehensively studied. We get the optimal rates under some mild conditions, which matches the one-stage sampled minimax optimal rate.
  arXiv  Detail & Related papers  (2022-08-26T03:46:14Z)
• Generalized Kernel Ridge Regression for Causal Inference with Missing-at-Random Sample Selection [3.398662563413433]
  I propose kernel ridge regression estimators for nonparametric dose response curves and semiparametric treatment effects. For the discrete treatment case, I prove root-n consistency, Gaussian approximation, and semiparametric efficiency.
  arXiv  Detail & Related papers  (2021-11-09T17:10:49Z)
• Sensing Cox Processes via Posterior Sampling and Positive Bases [56.82162768921196]
  We study adaptive sensing of point processes, a widely used model from spatial statistics. We model the intensity function as a sample from a truncated Gaussian process, represented in a specially constructed positive basis. Our adaptive sensing algorithms use Langevin dynamics and are based on posterior sampling (textscCox-Thompson) and top-two posterior sampling (textscTop2) principles.
  arXiv  Detail & Related papers  (2021-10-21T14:47:06Z)
• A Note on Optimizing Distributions using Kernel Mean Embeddings [94.96262888797257]
  Kernel mean embeddings represent probability measures by their infinite-dimensional mean embeddings in a reproducing kernel Hilbert space. We show that when the kernel is characteristic, distributions with a kernel sum-of-squares density are dense. We provide algorithms to optimize such distributions in the finite-sample setting.
  arXiv  Detail & Related papers  (2021-06-18T08:33:45Z)
• Exact Recovery in the General Hypergraph Stochastic Block Model [92.28929858529679]
  This paper investigates fundamental limits of exact recovery in the general d-uniform hypergraph block model (d-HSBM) We show that there exists a sharp threshold such that exact recovery is achievable above the threshold and impossible below it.
  arXiv  Detail & Related papers  (2021-05-11T03:39:08Z)
• Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
  We consider the populationimation barycenter problem for random probability measures supported on a finite set of points and generated by an online stream of data. We employ the structure of the problem and obtain a convex-concave saddle-point reformulation of this problem. In the setting when the distribution of random probability measures is discrete, we propose an optimization algorithm and estimate its complexity.
  arXiv  Detail & Related papers  (2020-06-11T19:40:38Z)
• Efficiently Sampling Functions from Gaussian Process Posteriors [76.94808614373609]
  We propose an easy-to-use and general-purpose approach for fast posterior sampling. We demonstrate how decoupled sample paths accurately represent Gaussian process posteriors at a fraction of the usual cost.
  arXiv  Detail & Related papers  (2020-02-21T14:03:16Z)

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.