3
$\begingroup$

Let us first define the variation diminishing property for the Gaussian kernel. Consider a function $f: \mathbb{R} \to \mathbb{R}$ that is sufficiently smooth and define \begin{align} F(x)= \int_{-\infty}^\infty f(t)\, \phi(x-t) {\rm d} t \end{align} where $\phi(t)=\exp(-t^2)$. Then, the variation diminishing property say that \begin{align} S(F) \le S(f) , \end{align} where the quantity $S(g)$ denotes the number of sign changes of a function $g$. Note: This property holds not just for Gaussian kernels but for a large class of kernels called Polya frequency functions.

Question: We are interested in what are some proper ways of generalizing this property to multivariate settings and counting number sign changes of $F$, and whether such generalizations are available in the literature?

More specifically, we are interested in a setting

\begin{align} F( u )= \iint_{\mathbb{R}^2}f({\bf t}) \, \phi({\bf r}(u)-{\bf t}) {\rm d} {\bf t} \end{align} where ${\bf r}(u)$ is path in $\mathbb{R}^2$ where now $\phi ({\bf t})=\exp(-\|{\bf t}\|^2)$. The goal is to provide a bound on the number of sign changes of $F$ using some properties of $f$ and ${\bf r}$. In the univariate case these properties correspond to sign changes of $f$.

Some Thoughts: I have searched the literature and was not able to find any multivariate generalizations. I did, for example, find a generalization to the case where instead of convolution we have more general transformation (ie., $\int_{-\infty}^\infty f(t) k(x,t) {\rm d} t$).

I suspected that the generalization to a full vector case, that is \begin{align} F( {\bf u} )= \iint_{\mathbb{R}^2}f({\bf t}) \phi({\bf u}-{\bf t}) {\rm d} {\bf t} \end{align} is difficult as we need to define a notion of sign changes in $\mathbb{R}^2$. However, in this problem the domain of $F( u )$ is one dimensional, so I think it is a bit easier, and the notion of sign changes is well defined for $F$. The difficulty, however, is how to generalize the notion of sign changes to $f$ or maybe some other property is needed.

$\endgroup$
4
  • $\begingroup$ Out of curiosity, if $F:\mathbb R^2\to R$, what is the wrong with the usual notion of sign change? Is it absurd/trivial to talk of variation diminishing property in this case? $\endgroup$
    – username
    Aug 28, 2021 at 16:21
  • $\begingroup$ @username Think of a function $f(x_1,x_2)= x_1^2 +x_2^2 -1$. The set of sign changes is $\{ (x_1,x_2): x_1^2 +x_2^2 =1 \}$ which is an uncountable set. So, sign changes can occur on curves instead of being isolated points. I think another property is necessary. $\endgroup$
    – Boby
    Aug 28, 2021 at 16:26
  • $\begingroup$ Yes, but the number of sign changes which is what you refered to can still be countable. It is the niumber of connected open sets where it is positive (or the number of connected open sets where it is negative depending how you see 0) In your example, it is 1. $\endgroup$
    – username
    Aug 28, 2021 at 17:16
  • $\begingroup$ @username I agree, it depends on how we define sign changes. This is exactly what I am curious about and the question is: what is the correct generalization? $\endgroup$
    – Boby
    Aug 28, 2021 at 23:42

1 Answer 1

2
+50
$\begingroup$

Angeloni, Costarelli, and Vinti, in arXiv:1906.03021, study a discrete multivariate convolution
for a class of averaged product kernels of the form $$\bar{\chi}_m(t_1,t_2,\ldots t_N)=\prod_{i=1}^N\left(\frac{1}{m}\int_{-m/2}^{m/2}\chi_i(t_i+v)\,dv\right).$$ The variation $V[f]$ of a function $f:\mathbb{R}^N\rightarrow \mathbb{R}$, defined by $$V[f]=\int_{\mathbb{R}^N}|\nabla f(\mathbf{x}|\,d\mathbf{x},$$ allows for the formulation of a variation diminishing property (proposition 1).


$\endgroup$
4
  • $\begingroup$ Thanks. I will try to read the paper you suggested. Can the right side of (5) be related to sign changes? $\endgroup$
    – Boby
    Aug 28, 2021 at 23:39
  • $\begingroup$ For $N=1$ the total variation $V[f]$ counts the oscillations weighted by their amplitude. The weight factor makes it possible to generalize the variation diminishing property to $N>1$, when sign changes can no longer be unambiguously defined. $\endgroup$ Aug 29, 2021 at 10:52
  • 1
    $\begingroup$ @CarloBeenakker Is $V[f]$ just the $L^1$ norm of the gradient? I don't see the link with sign change, since no sign change or oscillation is required for this property to hold. Seems a bit far from the target. $\endgroup$
    – username
    Aug 31, 2021 at 15:31
  • $\begingroup$ well, if the target is to construct a variation diminishing property that remains applicable for $N>1$, then I would argue that $\int|\nabla f|dx$ is the way to go. While for $N=1$ this is not the same as counting sign changes, it does provide a measure for how rapidly a function oscillates, which may or may not be sufficient for your purpose. $\endgroup$ Aug 31, 2021 at 15:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.