Fake nodes

Fake nodes have been introduced in 2020 in the context of univariate polynomial interpolation.

The underlying idea in this approach is to map the original set of nodes into a new set of node points, which are the so-called fake nodes, while preserving the original function values. The resulting interpolation strategy, which is described below, provides the advantage of solving the original interpolation problem while interpolating at a different set of node points, possibly "well-behaved" with respect to the original one, without actually resampling the underlying function.

The fake nodes approach has been successfully applied to substantially reduce both the Runge's phenomenon and the Gibbs phenomenon.

Approximating via the fake nodes approach

Univariate polynomial interpolation at fake nodes

Let <math>\Omega=[a,b] \subset\mathbb{R}</math> be an interval and let <math>{\cal X}_{n+1} = \{ x_i\}_{i = 0, \ldots , n} \subset \Omega</math> be a set of distinct nodes (also called data sites). The interpolation problem consists in reconstructing a function <math>f: \Omega \longrightarrow \mathbb{R}</math> given its values at the nodes <math> {\cal F}_{n+1}= \{ f_i = f(x_i)\}_{i=0, \ldots, n}</math>, by imposing interpolating conditions. More precisely, in the polynomial setting, we look for the polynomial <math>P_{n,f}</math> of degree <math>n</math> such that

<math>P_{n,f}(x_i)= f_i, \quad i=0,\ldots,n.</math>

The resulting interpolant can be expressed in the monomial basis

<math>P_{n,f}(x)=\sum_{i=0}^n{c_ix^i},</math>

where the coefficients <math>c_i</math> are uniquely determined.

In the fake nodes approach, an injective map <math>S:\Omega\longrightarrow\mathbb{R}</math> is considered. Then, letting <math>\tilde{x} \in S(\Omega)</math>, it is possible to compute the polynomial <math>P_{n,g}: S(\Omega) \longrightarrow \mathbb{R}</math> interpolating the function values <math>{\cal F}_{n+1}</math> at the fake nodes <math>S({\cal X}_{n+1})=\{S(x_i)=\tilde{x}_i\}_{i = 0, \ldots , n}\subset S(\Omega)</math>. We can write

<math>P_{n,g}(\tilde{x} )=\sum_{i=0}^n{c_i\tilde{x} ^i},</math>

for some <math>g:S(\Omega)\longrightarrow\mathbb{R}</math> so that <math>g_{|_{S({\cal X}_{n+1})}}= f_{|_{{\cal X}_{n+1}}}.</math>

Finally, for <math>x \in \Omega</math> we define the fake nodes interpolant as

<math>R^s_{n,f}(x):= P_{n,g}(S(x))=\sum_{i=0}^n{c_iS(x)^i},</math>

which indeed interpolates the function <math>f</math> at the original set of nodes <math>{\cal X}_{n+1}</math>.

As presented in the seminal paper, by properly choosing the map <math>S</math> the original set of nodes can be mapped on the set of Chebyshev nodes, providing a stable polynomial reconstruction which is not affected by the Runge's phenomenon. Moreover, it is also possible to treat the Gibbs phenomenon that arises when reconstructing discontinuous functions.

Extensions to different approximation settings

The strategy introduced in the polynomial interpolation context can be easily generalized to other approximation settings. In particular, the fake nodes approach has been applied in mitigating the Gibbs phenomenon in univariate barycentric rational interpolation and in multivariate reconstruction in the framework of MPI.

External links

• Python software for univariate polynomial interpolation
• Python software for bivariate polynomial interpolation
• (PDF) Quadrature at fake nodes - ResearchGate
• Attack Graph Convolutional Networks by Adding Fake Nodes
• Fake Node Attacks on Graph Convolutional Networks - arXiv
• Fake nodes - Unipd
• Fake Nodes approximation for Magnetic Particle Imaging
• Non-target-specific Node Injection Attacks on Graph Neural
• Aiding the Detection of Fake Accounts in Large Scale ... - Usenix

This article "Fake nodes" is from Wikipedia. The list of its authors can be seen in its historical. Articles taken from Draft Namespace on Wikipedia could be accessed on Wikipedia's Draft Namespace.