conditions for finding a convolutional graph filter

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

Recall from above that

• $\hat{y}=h(\mathrm{\Lambda })\hat{x}$
• $\hat{y}=\sum _k^{K-1}{h}_k{\mathrm{\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{array}{rl}\left[\begin{array}{ccccc}{\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}\\ ⋮& ⋮& & & ⋮\\ {\hat{x}}_n& {\hat{x}}_n{\lambda }_n& {\hat{x}}_n{\lambda }_n^2& \dots & {\hat{x}}_n{\lambda }_n^{K-1}\end{array}\right]\left[\begin{array}{c}{h}_0\\ h_1\\ ⋮\\ h_{K-1}\end{array}\right]& =\\ \text{diag}(\hat{x})\left[\begin{array}{ccccc}1& {\lambda }_1& {\lambda }_1^2& \dots & {\lambda }_1^{K-1}\\ 1& {\lambda }_2& {\lambda }_2^2& \dots & {\lambda }_2^{K-1}\\ ⋮& ⋮& & & ⋮\\ 1& {\lambda }_n& {\lambda }_n^2& \dots & {\lambda }_n^{K-1}\end{array}\right]\left[\begin{array}{c}{h}_0\\ h_1\\ ⋮\\ h_{K-1}\end{array}\right]& =\left[\begin{array}{c}{\hat{y}}_1\\ {\hat{y}}_2\\ ⋮\\ {\hat{y}}_n\end{array}\right]\end{array}$$

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\mathrm{\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{array}{rl}\text{rank}\left(\left[\begin{array}{ccccc}1& {\lambda }_1& {\lambda }_1^2& \dots & {\lambda }_1^{K-1}\\ 1& {\lambda }_2& {\lambda }_2^2& \dots & {\lambda }_2^{K-1}\\ ⋮& ⋮& & & ⋮\\ 1& {\lambda }_n& {\lambda }_n^2& \dots & {\lambda }_n^{K-1}\end{array}\right]\right)& =\text{rank}\left(\left[\begin{array}{cccccc}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}\\ ⋮& ⋮& & & ⋮& ⋮\\ 1& {\lambda }_n& {\lambda }_n^2& \dots & {\lambda }_n^{K-1}& \frac{{\hat{y}}_n}{{\hat{x}}_n}\end{array}\right]\right)\\ ⟸{\lambda }_i\ne {\lambda }_j\mathrm{\forall }i\ne j\end{array}$$

^proof