PaperlayerView exact revision on arXiv

Source-linked AI summary

Variable Bandwidth Diffusion Kernels

Tyrus Berry, John Harlim

arXiv:1406.5064v3math.SPmath.NA

TL;DR

Existing kernel theory largely targets fixed bandwidths, despite widespread use of variable bandwidth kernels and the resulting need for density-sensitive error analysis. The paper derives asymptotic expansions and continuous and discrete pointwise error bounds for arbitrary bandwidth functions, showing that density-adapted bandwidths address sparse-sampling failures while improving robustness on compact domains.

  • Problem

    Existing asymptotic theory for kernel methods mainly covers fixed bandwidth kernels, leaving variable bandwidth kernels without comparable convergence rates and discrete error bounds.

  • Method

    The paper derives asymptotic expansions and pointwise error estimates for continuous and finite-data variable bandwidth operators, analyzing bandwidth choices tied to sampling density.

  • Results

    Variable bandwidth kernels overcome fixed-bandwidth convergence problems on non-compact domains and show greater robustness to bandwidth selection on compact domains.

  • Takeaways & Limitations

    For operator approximation when sampling density can approach zero, variable bandwidth kernels are necessary for convergence rather than merely an empirical improvement.

  • Takeaways & Limitations

    The bandwidth choice requires intrinsic manifold dimension, whose estimation can be difficult in the presence of noise.

Abstract

from arXiv · show

Practical applications of kernel methods often use variable bandwidth kernels, also known as self-tuning kernels, however much of the current theory of kernel based techniques is only applicable to fixed bandwidth kernels. In this paper, we derive the asymptotic expansion of these variable bandwidth kernels for arbitrary bandwidth functions; generalizing the theory of Diffusion Maps and Laplacian Eigenmaps. We also derive pointwise error estimates for the corresponding discrete operators which are based on finite data sets; generalizing a result of Singer which was restricted to fixed bandwidth kernels. Our analysis reveals how areas of small sampling density lead to large errors, particularly for fixed bandwidth kernels. We explain the limitation of the existing theory to data sampled from compact manifolds by showing that when the sampling density is not bounded away from zero (which implies that the data lies on an open set) the error estimates for fixed bandwidth kernels will be unbounded. We show that this limitation can be overcome by choosing a bandwidth function inversely proportional to the sampling density (which can be estimated from data) which allows us to control the error estimates uniformly over a non-compact manifold. We numerically verify these results on non-compact manifolds by constructing the generator of the Ornstein-Uhlenbeck process on a real line and a two-dimensional plane using data sampled independently from the respective invariant measures. We also verify our results on compact manifolds by constructing the Laplacian on the unit circle and the unit sphere and we show that the variable bandwidth kernels exhibit reduced sensitivity to bandwidth selection and give better results for an automatic bandwidth selection algorithm.

1. Introduction

Variable bandwidth kernels are widely used in practice, but the established asymptotic theory largely addresses fixed bandwidth kernels. This paper extends the analysis to variable bandwidth kernels and derives error bounds that expose the role of sampling density.

  • Kernel methods underpin machine-learning tasks including clustering and classification, while their mathematical analysis developed through Laplacian Eigenmaps and Diffusion Maps.
  • Most practical applications use variable bandwidth, or self-tuning, kernels rather than the fixed bandwidth kernels covered by much existing theory.
  • Variable bandwidth kernels are also used in density estimation, where bandwidth selection is especially important in distribution tails and sparsely sampled regions.
  • Prior variable-bandwidth theory established limiting operators but did not provide convergence rates or discrete error bounds.
  • The paper derives rigorous error bounds for variable bandwidth kernels and shows that pointwise errors depend intricately on both sampling measure and bandwidth function.

2. Main Result

The paper develops continuous and discrete asymptotic results for variable bandwidth kernels, then analyzes how normalization and bandwidth choices control the limiting operator and pointwise errors. The results identify why fixed bandwidths fail in sparse regions and how density-adapted bandwidths can maintain bounded errors.

  • The discrete operator is constructed from kernel evaluations over all data-point pairs and approximates a continuous Kolmogorov operator.
  • Theorem 1 provides error bounds for both continuous and discrete operators, extending prior asymptotic theory to variable bandwidth kernels.
  • The parameters α and β jointly control the limiting operator, with c1 = 0 yielding a Laplacian independent of sampling density.
  • The bandwidth can use an order-ϵ density estimate rather than exact knowledge of q, although the normalization requires higher-order control of qS_ϵ.
  • For non-compact manifolds, sparse sampling can make the final discrete error increase with data size when c2 > 0.
  • With fixed bandwidth β = 0, the error can become unbounded as sampling density q approaches zero; choosing β < 0 can make pointwise errors uniformly bounded.
  • On non-compact manifolds, sufficiently negative c2 can offset unbounded gradients and support bounded pointwise errors over finite data sets.
  • The theory does not cover non-compact manifolds with boundary and establishes only pointwise convergence on smooth functions, not spectral convergence.

3. Details of the numerical implementation

The implementation estimates a density-adaptive bandwidth, constructs normalized sparse kernel operators, and obtains their eigenvectors through a symmetric conjugate matrix. Numerical comparisons use sparse nearest-neighbor matrices and assess eigenfunction scaling and bandwidth sensitivity.

  • Bandwidth estimation: The method estimates the bandwidth function as ρ = q^β + O(ϵ), using nearest-neighbor information to approximate the sampling density.The numerical procedure uses k0 = 8 nearest neighbors and reports similar results for values up to k0 = 64.
  • Operator construction: The estimated bandwidth is used to evaluate the kernel on all data pairs and normalize the resulting discrete operator.The construction includes diagonal normalization and a conjugation step to obtain a symmetric matrix with the same eigenvalues.
  • Eigenvector computation: Eigenvectors of the normalized operator are recovered from the symmetric conjugate by applying the inverse diagonal conjugation.If ˆL = ˆUΛˆU⊤ and U = S^−1ˆU, then the columns of U are eigenvectors of L with eigenvalues Λ.
  • Eigenfunction comparison: Eigenvectors are rescaled using a Monte Carlo normalization because the data are sampled according to the density q.Repeated eigenvalues require an additional orthogonal transformation for visual comparison with known eigenfunctions.
  • Sparse implementation: Nearest-neighbor sparsification reduces storage from O(N^2) to O(Nk) memory while retaining a symmetric sparse matrix after symmetrization.A sparse eigenvalue solver is then used to compute the desired eigenvectors.

4. Application to Ornstein-Uhlenbeck processes on non-compact manifolds

Experiments on unbounded Ornstein–Uhlenbeck manifolds show that fixed bandwidth kernels become unreliable in low-density tails, while variable bandwidth kernels provide more stable eigenfunction estimates. Outlier removal does not resolve the issue without introducing boundary effects and can require vastly more data.

  • Real-line experiment: Variable bandwidth kernels approximate the Ornstein–Uhlenbeck fourth eigenfunction over a wider bandwidth range than fixed bandwidth kernels on a real line.For a carefully selected ϵ, fixed bandwidth can agree with the analytic eigenfunction, but its approximation is much more sensitive to ϵ.
  • Real-line experiment: As N increases to 20000, no fixed bandwidth value gives reasonable fourth-eigenfunction results, whereas variable bandwidth remains excellent and stable over a wide ϵ range.The fixed-bandwidth error bound diverges as sampled points reach regions where q approaches zero.
  • Outlier removal: Outlier removal creates a virtual absorbing boundary that alters the spectral properties of the discrete operator.This structural error produces poor convergence for fixed-bandwidth eigenvalues and eigenfunctions.
  • Outlier removal: Approximately 6 × 10^7 data points would be required for fixed bandwidth with outlier removal to reach the MSE of 0.002 obtained by variable bandwidth with 1000 points, if the observed power law persists.The comparison uses fixed-bandwidth datasets with N = 1000, 10000, and 100000 after outlier removal.
  • Higher-dimensional experiment: Across 10 random datasets of N = 20000 points, fixed bandwidth fails to agree well with the correct eigenfunction, while variable bandwidth improves with increasing data.The two-dimensional experiment likewise finds variable bandwidth reasonably close to the analytic eigenfunction and fixed bandwidth inaccurate despite tuning ϵ.

5. Application to non-uniformly sampled compact manifolds

On a non-uniformly sampled circle and sphere, variable bandwidth kernels provide more robust approximations across bandwidth choices and work well with automated tuning. The circle experiments also show that the tuning slope reaches the theoretically suggested value d/2 = 1/2, while estimating intrinsic dimension remains outside the paper’s scope.

  • Unit circle: The circle experiment approximates the Laplacian’s second eigenfunction, sin(θ), using variable and fixed bandwidth kernels under non-uniform sampling.The data contain N = 1500 points sampled from q(θ) = 1 4π(2 + cos(θ)).
  • Unit circle: Variable bandwidth kernels give better approximations over a larger range of ϵ values and remain less sensitive near the optimum after random perturbations.The comparison uses both a deterministic grid and a randomized data set, where each θi is perturbed by a uniform variable in [0, 0.5].
  • Bandwidth tuning: The automated tuning procedure selects ϵ = 2^-5 ≈ 0.031 for both kernels, and the maximal local slope is d/2 = 1/2.In the locally linear region, log(S(ϵ)) follows the predicted d/2 scaling.
  • Limitation: The proposed dimension-estimation possibility is not exhaustively compared with other methods, especially for noisy samples that do not lie exactly on the manifold.The paper suggests estimating dimension with a fixed bandwidth kernel before using that estimate for the variable bandwidth kernel.
  • Unit sphere: For the unit sphere, variable bandwidth kernels are less sensitive to ϵ and the automated tuning algorithm produces a nearly optimal value.The corresponding automated choice for the fixed bandwidth kernel produces very poor results, although fixed bandwidth can work well with careful tuning on compact manifolds.

6. Conclusion

The paper develops variable bandwidth kernel theory for operator approximation and shows its practical advantages, especially when sampling density becomes small. Numerical results support improved convergence on non-compact domains and reduced bandwidth sensitivity on compact domains, while several theoretical limitations remain.

  • Theory: The theory derives asymptotic expansions and discrete error estimates for variable bandwidth kernels, extending diffusion-map analysis beyond fixed bandwidths.The derivation proceeds through left, right, and symmetric kernel formulations, first under uniform sampling and then for non-uniform sampling.
  • Operator interpretation: Variable bandwidth kernels can encode gradient-flow generators through a density- or potential-dependent bandwidth function.For uniform sampling, the limiting operator includes a gradient term and corresponds to a generator with potential U(x) = −(d + 2) log(ρ).
  • Error estimates: When sampling density approaches zero, fixed-bandwidth operator error bounds may become unbounded, whereas suitable variable bandwidths can be necessary for convergence.The distinction arises because sampling density appears in the denominator of operator-approximation error bounds when β = 0.
  • Numerical validation: Numerical simulations show that variable bandwidth kernels overcome large fixed-bandwidth errors on non-compact domains and are more robust to nuisance-parameter choices on compact domains.The automated ε-tuning method empirically identifies ranges with small mean squared errors for the variable bandwidth kernel.
  • Limitations: The main practical drawback is that the proposed bandwidth choice requires knowledge of the manifold’s intrinsic dimension.Dimension enters both the formulas determining the limiting operator and the variable-bandwidth density estimate used for de-biasing.
  • Limitations: The theory does not cover non-compact manifolds with boundary, and convergence is established only pointwise for smooth functions rather than spectrally.Extending the results to spectral convergence and non-compact boundaries remains an open challenge.

Appendix A.1. Extending the asymptotic expansion of diffusion maps

This appendix extends the fixed-bandwidth kernel expansion from compact manifolds to non-compact manifolds under integrability, smoothness, and fast-decay assumptions. The proof localizes the kernel integral and preserves the local asymptotic expansion, but function growth remains constrained by sampling-density decay.

  • Assumptions: The non-compact extension assumes a positive sampling density q that is bounded above, integrable, and C3, together with a fast-decaying kernel profile.These assumptions appear in Lemma 2 for an embedded manifold without boundary.
  • Expansion: The fixed-bandwidth expansion contains a leading term m0 f(x)q(x), an order-ε Laplacian and geometry correction, and an O(ε^2) remainder.The expansion is stated for the product f q under the non-compact-manifold assumptions.
  • Proof strategy: Compactness is replaced by localization: Gaussian tail decay makes the contribution outside an ε^γ neighborhood negligible as ε approaches zero.The change of variables x − y = √ε z and the condition 0 < γ < 1/2 yield the localization argument.
  • Proof strategy: The proof otherwise follows the local asymptotic expansion used for compact manifolds, with no further modifications.The non-compact argument supplies the tail control needed before applying the local expansion.
  • Scope: The expansion applies only to functions in L2(M,q), so admissible function growth must be controlled by the decay of the sampling density.On unbounded manifolds, eigenfunctions may grow polynomially, motivating stronger decay assumptions on q.

Appendix A.2. Left formulation of uniformly sampled data

The left formulation analyzes a variable bandwidth depending on the evaluation point and derives its operator expansion by a local metric change. After normalization, the leading variable-bandwidth effect is a bandwidth-weighted Laplacian.

  • Kernel setup: The left-formulation kernel uses a positive bandwidth function ρ evaluated at the base point x.Its expansion is developed under uniform sampling before later extensions to non-uniform sampling.
  • Derivation: A local transformation rescales tangent-space coordinates by ρ(x), converting the variable-bandwidth calculation into the fixed-bandwidth expansion.The map is a local diffeomorphism with derivative ρ(x)Id on the tangent space.
  • Expansion: The unnormalized left operator has leading factor ρ(x)^(d/2) and an order-ε correction involving ρ(x)Δf(x).The shape-function constants m0 and m2 are the same type of constants as in the fixed-bandwidth expansion.
  • Normalization: Left normalization removes the leading multiplicative factor and isolates the order-ε operator term.The normalization divides by the corresponding operator applied to the constant function.
  • Sampling: The appendix notes that uniform-sampling Monte Carlo sums estimate a volume-scaled operator, while the normalization removes the irrelevant scale factor.For non-uniform sampling, the expansion is obtained by applying the operator to f q under suitable assumptions.

Appendix A.3. Right formulation of uniformly sampled data

The right formulation places the bandwidth function at the integration point, producing a different expansion from the left formulation. Its normalized limit includes both a bandwidth-weighted Laplacian and a gradient-drift term.

  • Formulation: The right formulation depends on ρ(y), and its expansion cannot be obtained by the same direct change of variables used for ρ(x).The dependence on the integration point makes an explicitly invertible joint transformation unavailable.
  • Derivation: A weak formulation exchanges integration order and applies the previously derived left-formulation expansion to the inner integral.Symmetry of the Laplacian then permits recombination into the right-formulation expansion.
  • Expansion: The unnormalized right operator has leading term m0ρ^(d/2)f and correction Δ(fρ^(d/2+1)).The resulting expression includes an O(ε^2) remainder.
  • Normalized operator: After left normalization, the order-ε term is ρΔf + (d + 2)∇ρ · ∇f.This differs from the left formulation by an explicit gradient contribution driven by spatial variation in ρ.
  • Interpretation: The normalized right operator has the form of a Kolmogorov diffusion generator in potential U(x) = −(d + 2) log ρ(x).The appendix verifies this interpretation numerically before turning to the symmetric kernel.

Appendix A.4. Symmetric bandwidth for uniformly sampled data

For uniformly sampled data, the symmetric variable-bandwidth kernel expansion yields operators involving the Laplacian and bandwidth-gradient terms, with numerical verification on a circle and flat torus.

  • The symmetric-kernel expansion produces terms proportional to ρ^2∆f and ρ∇ρ · ∇f.
  • Applying left normalization yields the operator LS for uniformly sampled data.
  • The formula is verified on a unit circle in R2 and a flat torus in R4 using uniformly spaced latent-space grids.
  • Figure A.8 evaluates LL, LR, and LS for ϵ = 0.1, 0.01, and 0.001 on circle and torus grids.The grids contain 3000 and 62,500 points, respectively.
  • For the circle example, the displayed reference is ∆f = −sin(θ), while the LS comparison includes the bandwidth-gradient contribution.

Appendix A.5. Symmetric bandwidth for non-uniformly sampled data

For non-uniform sampling, normalization removes sampling-density bias and variable bandwidth modifies the limiting operator, enabling targeted gradient-flow generators and density-adapted Laplacians.

  • Monte-Carlo kernel operators for sampling density q(x) require normalization to address the bias introduced by q.
  • Right normalization removes the sampling bias in the integral operator before left normalization produces the target operator.
  • Choosing ρ = e^−U/(d+2) makes the bandwidth-gradient term represent the gradient-flow potential U.
  • With α = 1, the sampling-density effect is removed and the generator becomes ∆f − ∇U · ∇f.
  • For q(θ) = exp(cos(θ)), β = −1/2 and α = 1/4 recover the circle Laplacian, whereas α = −1/4 yields the Kolmogorov operator for U(θ) = −cos(θ).
  • Order-ϵ errors in the estimated sampling density do not affect the order-ϵ operator estimate after left normalization.

Appendix B. Convergence Rates for Discrete Operators

The discrete-operator analysis extends convergence estimates to variable bandwidths and non-uniform sampling on possibly non-compact manifolds, using Monte-Carlo approximations of continuous kernel operators.

  • The analysis generalizes Singer’s discrete-operator error estimates to variable bandwidth kernels and non-uniform sampling.
  • Independent samples from density q(x) on a Riemannian manifold M are used to construct the discrete approximations.
  • The normalization factors ϵ^−d/2N^−1 cancel in the ratios used by the algorithm and therefore need not be computed.
  • The functionals Fi and Gi approximate the operator LS through discrete sums replacing continuous expectations.
  • The kernel’s exponential decay bounds the summands, supporting concentration estimates for the discrete approximation.

Appendix B.1. Sampling error in the renormalization factor

Sampling error in the renormalization factor is controlled through concentration bounds whose requirements depend strongly on density, bandwidth, dimension, and sample size.

  • The denominator analysis uses concentration bounds to control errors in the functionals Fi and Gi.
  • The diagonal sample term is typically included in implementations but can be omitted after estimating its expansion-based error.
  • The sampling error is analyzed by comparing discrete Monte-Carlo sums with continuous expectations using centered variables Yl.
  • As q approaches zero, the probability bound worsens because q(xj) appears in the denominator of the error estimate.
  • When q^1/2ρ^−d/2 = O(1), achieving the desired accuracy with high probability requires ϵ = O(N^−1/(4+d/2)).
  • The operator expansion uses LS f = ρ^2∆f + (d + 2)ρ∇ρ · ∇f for arbitrary f.
  • The variance calculation contains leading terms involving ϵ, q, ρ, and ||∇f||^2 before concentration converts them into error estimates.
Loading 1406.5064v3…