conditions for finding a convolutional graph filter

Data

subject:: Data Science Methods for Large Scale Graphs parent:: Graph Signals and Graph Signal Processing theme:: math notes

Theorem

Let $S$ be a shift operator with eigenvalues ${\lambda }_1,{\lambda }_2,\dots ,{\lambda }_n$, and $x$ a graph signal. Let $\hat{x}$ be the GFT.

Suppose

• ${\hat{x}}_i\ne 0\forall i$
• ${\lambda }_i\ne {\lambda }_j\forall i\ne j$

Then there exist $K\le n$ coefficients $h_0,\dots ,h_{K-1}$ such that $y=H(S)x$, and $H$ is a graph convolution

Proof

Recall from above that

• $\hat{y}=h(\Lambda )\hat{x}$
• $\hat{y}={\sum }_k^{K-1}{h}_k{\Lambda }^k\hat{x}$
• ${\hat{y}}_i={\sum }_k^{K-1}{h}_k{\lambda }_i^k{\hat{x}}_i$

We can write this as a linear system:

\begin{bmatrix} \hat{x}{1} & \hat{x}{1} \lambda_{1} & \hat{x}{1}\lambda{1}^2 & \dots & \hat{x}{1}\lambda{1}^{K-1} \ \hat{x}{2} & \hat{x}{2}\lambda_{2} & \hat{x}{2} \lambda{2}^2 & \dots & \hat{x}{2}\lambda{2}^{K-1} \ \vdots & \vdots & & & \vdots \ \hat{x}{n} & \hat{x}{n}\lambda_{n} & \hat{x}{n}\lambda{n}^2 & \dots & \hat{x}{n}\lambda{n}^{K-1} \ \end{bmatrix}\begin{bmatrix} h_{0} \ h_{1} \ \vdots \ h_{K-1} \end{bmatrix}&= \ \text{diag}(\hat{x}) \begin{bmatrix} 1 & \lambda_{1} & \lambda_{1}^2 & \dots & \lambda_{1}^{K-1} \ 1 & \lambda_{2} & \lambda_{2}^2 & \dots & \lambda_{2}^{K-1} \ \vdots & \vdots & & & \vdots \ 1 & \lambda_{n} & \lambda_{n}^2 & \dots & \lambda_{n}^{K-1} \end{bmatrix}\begin{bmatrix} h_{0} \ h_{1} \ \vdots \ h_{K-1} \end{bmatrix} &= \begin{bmatrix} \hat{y}{1} \ \hat{y}{2} \ \vdots \ \hat{y}_{n} \end{bmatrix} \end{aligned}$$

Note that LHS $=\text{diag}(\hat{x})V$ where $V$ is a $n\times K$ Vandermonde matrix

In order to find a solution to the system (ie, in order for us to find coefficients $h_0,\dots ,h_{K-1}$), we need

1. $\text{diag}(\hat{x})$ invertible $⟺{\hat{x}}_i\ne 0\forall i$
2. $Vh=\text{diag}(\hat{x}{)}^{-1}\hat{y}$ to yield a solution

In the simplest case where $K=n$, we need the Vandermonde matrix to have an inverse. Since $\det (V)={\prod }_{i\ne j}({\lambda }_i-{\lambda }_j)$, $V$ is invertible if and only the ${\lambda }_i$ are distinct.

If $K\ne n$ or arbitrary $K$, the Rouché-Capelli Theorem states that a linear system with $n$ equations in $K$ unknowns is consistent (ie has a solution) if and only if the rank of the coefficient matrix and the augmented matrix are the same. In this case, this means

\begin{bmatrix}

1 & \lambda_{1} & \lambda_{1}^2 & \dots & \lambda_{1}^{K-1} \ 1 & \lambda_{2} & \lambda_{2}^2 & \dots & \lambda_{2}^{K-1} \ \vdots & \vdots & & & \vdots \ 1 & \lambda_{n} & \lambda_{n}^2 & \dots & \lambda_{n}^{K-1} \end{bmatrix}\right) &= \text{rank} \left( \left[\begin{array}{ccccc|c} 1 & \lambda_{1} & \lambda_{1}^2 & \dots & \lambda_{1}^{K-1} & \frac{\hat{y}{1}}{\hat{x}{1}} \ 1 & \lambda_{2} & \lambda_{2}^2 & \dots & \lambda_{2}^{K-1} & \frac{\hat{y}{2}}{\hat{x}{2}}\ \vdots & \vdots & & & \vdots & \vdots\ 1 & \lambda_{n} & \lambda_{n}^2 & \dots & \lambda_{n}^{K-1} & \frac{\hat{y}{n}}{\hat{x}{n}} \end{array} \right]\right) \

\impliedby \lambda_{i} \neq \lambda_{j} ;;; \forall i \neq j \end{aligned}$$

Mentions

TABLE
FROM [[]]
 
FLATTEN choice(contains(artist, this.file.link), 1, "") + choice(contains(author, this.file.link), 1, "") + choice(contains(director, this.file.link), 1, "") + choice(contains(source, this.file.link), 1, "") as direct_source
 
WHERE !direct_source