Questions tagged [kernels]
The kernels tag has no usage guidance.
101 questions
1
vote
0
answers
54
views
How computationally efficient are kernel tricks? [closed]
"If we compare to non-kernel polynomial regression it is O(Tnp) where is p is dimension of polynomial while kernel polynomial is O(n^2d) + O(T*n^2) where d is original number of attributes, ...
3
votes
1
answer
109
views
Literature request: Covariance operators for Gaussian measures
I am looking to answer the question:
If $\mathcal{B}$ is a separable Banach space and $R: \mathcal{B}^*\to\mathcal{B}$ is a symmetric and positive operator, then $\phi: \mathcal{B}^*\to\mathbb{R}, \...
- 171
4
votes
1
answer
420
views
Visualizing the elements of a finite group and does the Gram matrix determine the finite group?
Let $G$ be a finite group with $n = |G|$ elements. By Cayley's theorem for finite groups, we have an injective homomorphism of groups:
$$
\pi : G \rightarrow S_n, \quad g \mapsto \pi(g)
$$
where ...
- 3,032
5
votes
1
answer
192
views
Non-equivalent definitions of Markov process
As far as I know, there are three definitions of Markov processes (or of Markov chains).
DEFINITION 1 (WEAKER). A process $(X_t)_{t\in[0,\infty)}$ on $(\Omega,\mathcal{F},\mathbb{P})$ with values in ...
- 1,149
2
votes
1
answer
90
views
Heat kernel convergence when expanding domains
Let $\Omega$ be an arbitrary domain in $\mathbb{R}^n$. There exists a positive $C^{\infty}$ function $G_{\Omega} : \Omega \times \Omega \times (0, \infty) \rightarrow \mathbb{R}$ (Dirichlet heat ...
- 677
4
votes
2
answers
203
views
Results of invertibility of a matrix involving the Szego kernel
In the context of reproducing kernel Hilbert spaces, the Szego kernel is the function $k(z_i,z_j)=\frac{1}{1-z_j\overline{z_j}}$.
Given $2n$ points $\{z_1,\ldots,z_n\},\{w_1,\ldots,w_n\}\in\mathbb{D}\...
- 167
1
vote
1
answer
121
views
Characterization of Fellerian kernels
This question concerns Feller Markov kernels, similar to Vanessa's question.
Terminology
By 'Markov kernel' $N:E\to F$, we adopt exactly the same definition as Vanessa, with the exception that $E,F$ ...
- 235
1
vote
0
answers
47
views
Characterization of Gaussian Gram matrices
From Euclidean geometry we know that a matrix $C$ is a matrix of squared Euclidean distances between some points if and only if $-\frac{1}{2} H D H \succeq 0$ (positive semi-definite) with $H = (I - \...
- 407
2
votes
1
answer
63
views
Non-linear transforms of RKHS question
I was reading the paper Norm Inequalities in Nonlinear Transforms (referenced in this question) but ran into difficulties, so I was wondering if anyone could help?
I think I follow the paper until I ...
- 41
2
votes
1
answer
74
views
Conditions for absorption
Let $X$ be a Markov chain with countable state space $S$ and transition kernel $P$, and let $h \colon S \to [0,1]$ be a sub-harmonic or super-harmonic function. Assume that for all $\varepsilon >0$ ...
user514580
1
vote
0
answers
143
views
Estimator for the conditional expectation operator with convergence rate in operator norm
Let $X$ and $Z$ be two random variables defined on the same probability space, taking values in euclidian spaces $E_X$ and $E_Z$, with distributions $\pi$ and $\nu$, respectively.
Let $L^2(\pi)$ ...
- 111
6
votes
0
answers
184
views
Gaussian lower heat kernel bounds on non-convex bounded domain
I am looking for a proof the following theorem.
Let $U \subset \mathbb{R}^n$ be a bounded domain with $C^2$ boundary and $p(x,y,t)$ be the Neumann heat kernel. Then there exist a constant $C>0$ ...
- 61
2
votes
1
answer
145
views
Orthonormal bases in RKHSs via interpolating sequences
Definitions and setting
Let $\mathcal{H}$ be a separable, infinite-dimensional, reproducing kernel Hilbert space on a nonempty set $X$. As usual, denote the reproducing kernel on $\mathcal{H}$ by $K$ ...
- 5,407
1
vote
0
answers
110
views
Gradient estimate of Dirichlet Heat kernel (Classical Laplacian)
Let $p^D(t,x,y)$ be the heat kernel for the Dirichlet Laplacian in an open set $D$. Do we have the following estimate and where can I find it ? $$\lvert\nabla_xp^D(t,x,y)\rvert\le C\dfrac{1}{\min (\...
16
votes
3
answers
1k
views
A kernel 'more analytic' than $\exp(-x^2)$
I am looking for an analytic function $F: \mathbb{R} \rightarrow (0,\infty)$ with $\int_{\mathbb{R}} F(x) \, dx = 1$ and the property, that $\sum\limits_{k=0}^{\infty} |c_k| \varepsilon^k (2k)! < \...
- 1,295
2
votes
1
answer
91
views
Pair of positive harmonic functions with negative inner product in Drury-Arveson space
Define a reproducing kernel on the Euclidean ball in $\mathbb{C}^d$ by
$$k(z,w)=\frac{1}{1-\langle z,w\rangle}+\frac{1}{1-\langle w,z\rangle}-1.$$
Call the corresponding real reproducing kernel ...
- 1,429
5
votes
1
answer
256
views
Is $k(A, B) = \text{Tr}[(A^{1/2} B A^{1/2})^{1/2}]$ a positive definite kernel?
Let $\mathbb{S}_n$ denote the set of $n \times n$ symmetric positive semidefinite matrices. I am trying to figure out whether $k: \mathbb{S}_n \times \mathbb{S}_n \to \mathbb{R}_+$ defined as:
$$k(A, ...
- 204
2
votes
0
answers
73
views
RKHS lying in another RKHS
Suppose $H_1$ and $H_2$ are reproducing kernel Hilbert spaces such that $H_1 \subset H_2$. For $f \in H_1$, when can I bound $\|f \|_1$ with $C\|f\|_2$ (for some $C$)? Is there a relationship between ...
- 93
1
vote
2
answers
69
views
Monotonicity of kernel matrices with respect to hyperparameters
Let $\mathcal{X}$ be some nice space, let $\Phi$ be some ordered space, and let $K :\mathcal{X} \times \mathcal{X} \times \Phi \to \mathbf{R}$ be a positive-semidefinite kernel indexed by a ...
- 801
1
vote
0
answers
414
views
Conditions for equivalence of RKHS norm and $L^2(P)$ norm
Let $K$ be a psd kernel on an abstract space $X$ and let $H_K$ be the induced Reproducing Kernel Hilbert Space (RKHS). Let $P$ be a probability measure on $X$ such that $H_K \subseteq L^2(P_X)$ and ...
- 6,853
1
vote
0
answers
83
views
What is lost after RKHS embedding of the L1 space?
We know that every distribution or $L^1$ function $f$ over space $\mathcal{X}$ (e.g., $R^d$) can be embedded to an RKHS $\mathcal{H}$ with a $1$-bounded kernel $\mathcal{K}$ (e.g., the RBF kernel) ...
- 43
1
vote
0
answers
99
views
$L_1$ convergence rates for multivariate kernel density estimation
Let $X$ be a random variable on $\mathbb R^d$ with probability density function $f$, and let $X_1,\ldots,X_n$ of $X$ be $n$ iid copies of $X$. Given a bandwidth parameter $h=h_n > 0$ and a kernel $...
- 6,853
4
votes
2
answers
242
views
Sharp Dirichlet heat kernel estimates in exterior domains?
I am right now working on some linear parabolic problems studying the behaviour of its solutions for large initial data. To do this, I have needed to use some estimates of the Dirichlet and Neumann ...
- 61
1
vote
0
answers
63
views
Properties of a kernel convolution $K'(x,y) = \int_X\int_X K_0(x,a)K(a,b)K_0(b,y)d\mu(a)d\mu(b)$ where $K$ and $K_0$ are kernels on $(X,\mu)$
Let $(X,\mu)$ be a probability measure space and $K:X \times X \to \mathbb R$ be a (psd) kernel on $X$. Let $K_0$ be another kernel on $X$ and defined a new kernel $\widetilde K$ on $X$ by
$$
\...
- 6,853
2
votes
1
answer
157
views
Representer theorem for a loss / functional of the form $L(h) := \sum_{i=1}^n (|h(x_i)-y_i|+t\|h\|)^2$
Let $K:X \times X \to \mathbb R$ be a (positive-definite) kernel and let $H$ be the induced reproducing kernel Hilbert space (RKHS). Fix $(x_1,y_1),\ldots,(x_n,y_n) \in X \times \mathbb R$. For $t \ge ...
- 6,853
4
votes
0
answers
800
views
Reproducing kernel Hilbert space of Matérn kernels
I am trying to read a recent paper titled "Interpolation and learning with scale dependent kernels" by Pagliana, Ruidi, De Vito, and Rosasco. (The paper can be found on ArXiv)
On the top of ...
0
votes
0
answers
199
views
Is the kernel $\vert d_X - d_Y \vert^p$ conditionally negative definite?
Given two finite metric spaces $(X,d_X)$ and $(Y,d_Y)$, for $p > 0$, define the kernel ($4$-D tensor) $K$ on $(X \times Y)^2$ by:
$$K\big( (x_i, y_k), (x_j, y_l) \big) = \vert d_X(x_i, x_j) - d_Y(...
- 111
0
votes
1
answer
734
views
Proof: If a reproducing kernel exists for a Hilbert space, then it is unique
I really want to prove the statement in the title but I'm struggling with it. Here my current state:
Proof via contradiction. Let $\mathcal{H}$ be a RKHS with two reproducing kernels $k$ and $\hat{k}$ ...
- 13
3
votes
1
answer
427
views
Minimum upper bound for sum of the entries of the inverse covariance matrix
Let $x \in \mathbb{R}^n$ and $k$ is RBF kernel
$$k(x, x') := \exp \left(-\frac{\|x-x'\|^2}{2\sigma^2}\right)$$
and let $\mathbf{K}$ be the following $n \times n$ covariance matrix
$$\mathbf{K} = \...
3
votes
0
answers
282
views
Extending Ky Fan's eigenvalues inequality to kernel operators
--Migrating from MSE since it might fit better here--
Base result
The following result in Terry Tao's book, 'p. 47, Ky Fan inequality' reads as:
$$\sum_i\lambda_i(A+B) \leq \sum_i \lambda_i(A) + \...
- 255
0
votes
0
answers
233
views
A new method for processing music scores?
I have developed a method and python script:
https://github.com/githubuser1983/algorithmic_python_music
which allows the user to input a midi file and then chose a few numbers as parameters, and the ...
- 3,032
6
votes
1
answer
501
views
Why is this nonlinear transformation of an RKHS also an RKHS?
I came across this paper (beginning of page 6) where they stated that if $f,h\in \mathcal{H}$, where $\mathcal{H}$ is an RKHS, then $l_{h,f}=\left|f(x)-h(x)\right|^q$ where $q\geq 1$ also belongs to ...
- 383
1
vote
0
answers
132
views
Subspace of RKHS generated by kernel mean embeddings
Suppose $\mathcal{H_k}$ is a reproducing kernel Hilbert space (RKHS) with reproducing kernel $k: \mathcal{X} \times \mathcal{X} \rightarrow \mathbb{R}$. I am looking for results characterising the ...
- 93
4
votes
0
answers
111
views
What is the native Hilbert space associated with the kernel $\frac{\sum \min{(x_i,y_i)}}{\sum \max{(x_i,y_i)}}$?
In this answer on MSE it is shown that the function
$$ K:(\mathbb{R}^{>0})^n\times (\mathbb{R}^{>0})^n\rightarrow\mathbb{R}\,\quad K(x,y)=\frac{\sum_{i=1}^n\min{(x_i,y_i)}}{\sum_{i=1}^n\max{(x_i,...
- 316
2
votes
0
answers
65
views
Johnson filtration and lower central series
Let $G$ be a group and consider the lower central series:
$$G=\gamma_1 G \geq \gamma_2 G=[G,\gamma_1 G]\geq \gamma_3G=[G,\gamma_2G]\geq\cdots.$$
Let $S_g^1$ be a compact oriented genus $g$ surface ...
- 439
1
vote
1
answer
343
views
Simple example of Hammerstein integral equation
I'm currently reading this paper (and working on a similar one). The main goal is to study the Hammerstein integral equation (in $\mathcal{C}(I,E))$:
$$x(t) = \int_{0}^{t} K(t,s)f\big(s,x(s)\big)ds,\...
- 291
8
votes
0
answers
330
views
Monotonicity of log determinant of Gaussian kernel matrix
Let \begin{equation} k({x},{y}) = \sigma \exp\left(-\frac{(x-y)^2}{2\theta^2}\right)\end{equation}
be a squared-exponential (Gaussian) kernel, with $\sigma,\vartheta>0$. Consider, for a set of $N$ ...
- 55
3
votes
0
answers
461
views
Analytic formula for the eigenvalues of kernel integral operator induced by Laplace kernel $K(x,x') = e^{-c\|x-x'\|}$ on unit-sphere in $\mathbb R^d$
Let $d \ge 2$ be an integer and let $X=\mathcal S_{d-1}$ the unit-sphere in $\mathbb R^d$. Let $\tau_d$ be the uniform distribution on $X$. Define a function $K:X \times X \to \mathbb R$ by $K(x,y) := ...
- 6,853
1
vote
0
answers
233
views
Variance-based localized Rademacher complexity for RKHS unit-ball
Let $\mathscr X$ be a compact subset of $\mathbb R^d$ (e.g the unit-sphere). Let $K: \mathscr X \times \mathscr X \to \mathbb R$ be a positive kernel function and let $\mathscr H_K$ be the induced ...
- 6,853
1
vote
0
answers
105
views
Concentration of random Rayleigh quotients
Let $K$ be some large square matrix of height $N$, and $u$ a column vector of height $N$. Fixing $n$, take a random set of $n$ indices (with replacement) uniformly from $1,...,N$. Let $y$ be the ...
- 623
3
votes
1
answer
382
views
Is the solution to the Fredholm integral equation of the first kind a continuous analogue of Cramer's rule for matrix equations?
When we have a system of of $n$ linear equations represented by $$A \vec{x} = \vec{b} $$ with $\vec{x} = (x_{1}, x_{2}, \dots, x_{n})^{\intercal} $, we can solve for each component of this vector by ...
- 4,829
2
votes
0
answers
106
views
Kernels with finite dimensional feature spaces
Suppose $x,y \in \mathbb{R}^n$ for some given fixed n.
Consider a kernel $K(x,y) = f(\langle x, y \rangle)$, I'd like to know which functions $f$ admit a finite dimensional feature map. In other words,...
- 93
1
vote
0
answers
108
views
When do the kernels of module homomorphisms between rings whose kernels contain a given fixed ideal contain every prime ideal over it?
$\DeclareMathOperator{\Hom}{Hom}$All our rings are commutative with unity and, if necessary, we can suppose that they are actually polynomial rings over a field in finitely many variables where the ...
- 573
2
votes
0
answers
553
views
$\ell_\infty$-norm covering number of RKHS ball $\{f\in\mathcal{H}: \|f\|_\mathcal{H} \leq R\}$
For any $\epsilon \in (0,1)$, let $N_\infty(\epsilon, \mathcal{H}, R)$ denote the $\epsilon$-covering number of the RKHS norm ball $\{f\in\mathcal{H}: \|f\|_\mathcal{H} \leq R\}$ with respect to the $\...
- 121
3
votes
1
answer
688
views
Positive definite kernels involving the $\min$ function
I am interested in the positive kernels of the form $k(x,y) = \min\{a(x,y), b(x,y)\}$ (assuming $k(x,y) = k(y,x)$). Some examples including $\min\{x,y\}$ and $\min\{f(x)g(y), f(y)g(x)\}$, but are ...
- 41
1
vote
0
answers
120
views
Metric transforms that preserve $\ell^1$ embeddability
Consider a function $f$ from reals to reals such that $f$, when applied to pairwise Manhattan distances between $n$ points, always results in a set of Manhattan distances.
Work by Schoenberg and ...
- 93
0
votes
0
answers
30
views
Help for literature on entrywise invariant kernels
I am looking for literature on entrywise invariant kernels.
The specific example I have in mind is $K:R^{d}\times R^{d}\to R$ and locally compact groups acting on vector space $R^{d}$.
More precisely ...
- 329
1
vote
0
answers
64
views
When is inverse geodesic distance positive definite (in a compact manifold)?
We work on a closed smooth Riemannian manifold $(M,g)$ and let $K:M\times M\to \mathbb R\cup\{+\infty\}$ be a kernel, which we assume to be integrable and lower semicontinuous. We say it is positive ...
- 139
2
votes
1
answer
962
views
Defining measures through products of Markov kernels
I am quite puzzled by the expression given in equation 21 (page 10) in this paper,
https://arxiv.org/pdf/1802.09188.pdf
Its LHS seems to be a measure $\nu_n^N$ and hence I guess it takes as argument ...
- 2,246
0
votes
0
answers
93
views
How to introduce not-orthonormal base on Reproducing Kernel Hilbert Spaces?
I read some tutorial papers and slide，and find that the bases on Reproducing Kernel Hilbert Spaces always be orthonormal. For examples，you can refer to this link for the content about Reproducing ...
- 1