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 \Omega=[a,b] \subset\mathbb{R} be an interval and let {\cal X}_{n+1} = \{ x_i\}_{i = 0, \ldots , n} \subset \Omega be a set of distinct nodes (also called data sites). The interpolation problem consists in reconstructing a function f: \Omega \longrightarrow \mathbb{R} given its values at the nodes {\cal F}_{n+1}= \{ f_i = f(x_i)\}_{i=0, \ldots, n}, by imposing interpolating conditions. More precisely, in the polynomial setting, we look for the polynomial P_{n,f} of degree n such that
: P_{n,f}(x_i)= f_i, \quad i=0,\ldots,n.
The resulting interpolant can be expressed in the monomial basis
: P_{n,f}(x)=\sum_{i=0}^n{c_ix^i},
where the coefficients c_i are uniquely determined.
In the fake nodes approach, an injective map S:\Omega\longrightarrow\mathbb{R} is considered. Then, letting \tilde{x} \in S(\Omega), it is possible to compute the polynomial P_{n,g}: S(\Omega) \longrightarrow \mathbb{R} interpolating the function values {\cal F}_{n+1} at the fake nodes S({\cal X}_{n+1})=\{S(x_i)=\tilde{x}_i\}_{i = 0, \ldots , n}\subset S(\Omega). We can write
: P_{n,g}(\tilde{x} )=\sum_{i=0}^n{c_i\tilde{x} ^i},
for some g:S(\Omega)\longrightarrow\mathbb{R} so that g_{|_{S({\cal X}_{n+1})}}= f_{|_{{\cal X}_{n+1}}}.
Finally, for x \in \Omega we define the fake nodes interpolant as
: R^s_{n,f}(x):= P_{n,g}(S(x))=\sum_{i=0}^n{c_iS(x)^i},
which indeed interpolates the function f at the original set of nodes {\cal X}_{n+1}.
As presented in the seminal paper, by properly choosing the map S 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.
== References ==
== 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
Category:Polynomial interpolation
Category:Polynomial functions
Category:Lagrange polynomial
Category:Gibbs phenomenon
Category:Rational numbers
Category:Multivariate statistics