GVN computes graph equivalent of the Von Neummann variance estimator.
Usage
GVN(y, A, L)
Value
The Graph Von Neumann variance estimate for the given noisy data.
Arguments
y
Numeric vector that represents the noisy data.
A
Adjacency matrix of the graph.
L
Laplacian matrix of the graph.
Details
In many real-world scenarios, the noise level \(\sigma^2\) remains generally unknown. Given any function \(g : \mathbb R_+ \rightarrow \mathbb R_+\), a straightforward computation gives:
$$\mathbf E[\widetilde f^T g(L) \widetilde f] = f^T g(L) f + \mathbf E[\xi^T g(L) \xi] = f^T g(L) f + \sigma^2 \mathrm{Tr}(g(L))$$
A biased estimator of the variance \(\sigma^2\) can be given by:
$$\hat \sigma^2_1 = \frac{\widetilde f^T g(L) \widetilde f}{\mathrm{Tr}(g(L))}$$
Assuming the original graph signal is smooth enough that \(f^T g(L) f\) is negligible compared to \(\mathrm{Tr}(g(L))\), \(\hat \sigma^2\) provides a reasonably accurate estimate of \(\sigma^2\). For this function, a common choice is \(g(x) = x\). Thanks to Dirichlet's formula, it follows:
$$\hat \sigma^2_1 = \frac{\widetilde f^T L \widetilde f}{\mathrm{Tr}(L)} = \frac{\sum_{i,j \in V} w_{ij} |\widetilde f(i) - \widetilde f(j)|^2}{2 \mathrm{Tr}(L)}$$
This is the graph adaptation of the Von Neumann estimator, hence the term Graph Von Neumann estimator (GVN).
References
de Loynes, B., Navarro, F., Olivier, B. (2021). Data-driven thresholding in denoising with Spectral Graph Wavelet Transform. Journal of Computational and Applied Mathematics, Vol. 389.
von Neumann, J. (1941). Distribution of the ratio of the mean square successive difference to the variance. Ann. Math. Statistics, 35(3), 433--451.
if (FALSE) {
data(minnesota)
A <- minnesota$A
L <- laplacian_mat(A)
x <- minnesota$xy[ ,1]
n <- length(x)
f <- sin(x)
sigma <- 0.1
noise <- rnorm(n, sd = sigma)
y <- f + noise
sigma^2GVN(y, A, L)
}