thgsp.filters

Kernels and Approximation

design_biorth_kernel(k)

Compute the coefficients of biorthogonal kernels \(h_0\) and \(g_0\), which are nearly the most orthogonal and maximally balanced pair among all possible factorizations of

\[p(\lambda) =(2-\lambda)^{K}[1+\sum_{m=1}^{K-1}r_{m}(\lambda-1)^{m}],\]

where \(K=2k\). The design scheme detailed in [1] satisfies \(k_0=k_1=k, K=2k, l_0=2k\), and \(l_1=2k-1\), implying that the residual polynomial \(R(\lambda)\) is \(2k-1\) degree, with exactly one real root and \((k-1)\) complex conjugate pairs of roots. If \(k\) is odd, assign the only real root and \((k-1)/2\) complex conjugate pairs of roots to \(h_{0}(\lambda)\). Thus we have a \(2k\)-degree \(h_{0}(\lambda)\) having \(k\) roots at \(\lambda=2\) and other \(k\) roots which are zeros of \(R(\lambda)\). The \(2k-1\) degree \(g_{0}(\lambda)\) has \(k\) roots at \(\lambda=2\) and other k-1 roots from \(R(\lambda)\). If \(k\) is even, assign \(k/2\) complex conjugate root pairs of \(R(\lambda)\) to \(h_{0}(\lambda)\); the remaining \(k/2-1\) pairs of roots and the only real root to \(g_{0}(\lambda)\).

Parameters:

k (int) – This integer determines the degree of all polynomial kernels.

Returns:

• h0_c (array) – The coefficients of \(h_0\).

• g0_c (array) – The coefficients of \(g_0\).

• theta_best (float) – A float within \([0,1]\). The closer it is to \(1\) , the more orthogonal the wavelet bases determined by \(h_0\) and \(g_0\) are.

Notes

Large \(k(k>14)\) may lead to a failed kernel design, possibly due to the accumulated computation error arising in the high order power operations. Empirically speaking, a smaller \(k(2<k<12)\) works well.

References

[1]

S. Narang and A. Ortega, “Compact support biorthogonal wavelet filterbanks for arbitrary undirected graphs,” IEEE TSP, 2013.

design_p(K)

Auxiliary to design the biorthgonal kernel \(h_0(\lambda)\) and \(g_0(\lambda)\) metioned in design_biorth_kernel().

\[p(\lambda) =(2-\lambda)^{K}[1+\sum_{m=1}^{K-1}r_{m}(\lambda-1)^{m} =(1-l)^{K}[1+\sum_{m=1}^{K-1}r_{m}l^{m}],\lambda=l+1.\]

has \(K\) roots at \(\lambda=2\), and other \(K-1\) roots which are also roots of the residual polynomial below.

\[R(\lambda)=1+\sum_{m=1}^{K-1}r_{m}(\lambda-1)^{m}\]

This function can figure out the roots of \(R(\lambda)\) by firstly finding the zeros(roots) of \(R(l)\).

Parameters:

K (int) – The order of \(p(\lambda)\) is \(2K-1\)

Returns:

• Rlam (array) – The roots of R(lam),

• r_high (float) – The coefficient of the highest degree term.

cheby_op(x: Tensor, L: SparseTensor, coeff: Tensor, lam_max: float = 2.0)

Chebyshev approximation of graph filtering

Parameters:

• x (Tensor) – The input graph signal. It’s shape can be either (N,) , (N,Ci) or (Co,N,Ci), wherein N, Ci and Co are the numbers of nodes, input channels, and output channels respectively.

• L (SparseTensor) – The (N,N) Laplacian matrix.

• coeff (Tensor) – The (Co,Ci,K+1) Chebyshev coefficients for Ci*Co kernels, wherein K is the order of approximation.

• lam_max (float,optional) – The maximal graph frequency, i.e., \(\lambda_{max}\)

Returns:

The filtered signals of shape (Co,N,Ci)

Return type:

Tensor

polyval(c, x)

Evaluate N-order polynomial at the points x with the given N+1 coefficients in descending order.

Parameters:

• c (Tensor, a list of Tensor) – The coefficients can be either a list of tensors which are broadcastable with the input x or an concatenated tensor of them.

• x (Tensor, scalar) – Arbitrary rank-D tensor(D=1,2,…) is valid due to the broadcasting semantics.

Returns:

A tensor with the same shape as x

Return type:

Tensor

MIMO Graph Filter

class Filter(G: GraphBase, kernels=None, in_channels=None, out_channels=None, order=20, lam_max=None, lap_type='sym', weight=None)

A graph filter(bank) class.

Parameters:

• G (GraphBase) – Any instance of GraphBase or its subclass.

• kernels (array, callable, None) – Case1: The (Co,Ci) array of Co*Ci filters; Co and Ci are the dimensions of input and output signals, respectively Case2: A callable python object; all Co*Ci filters employ this kernel. Case3: Set all Co*Ci filters as ideal low-pass ones.

• lam_max (float) – The supremum of graph frequencies.

N

The number of graph nodes.

Type:

int

order

The degree of Chebyshev approximation.

Type:

int

weight

Shape: (Co,Ci). The signal of every output channel is a weighted sum of Ci filtered signals. The i,j-th entry is the weight of filtered signal from j-th input channel to i-th output channel. All-one tensor in default.

Type:

Tensor

dtype

The data type of signals and graph adjacency.

Type:

torch.dtype

device

The device of graph.

Type:

torch.device

__call__(x, cheby=True)

Filter the input signal x.

Parameters:

• x (Tensor) – The signal to filter. Shape: (N,) or (N,Ci). Ci and N are the numbers of input channels and graph nodes, separately.

• cheby (bool) – If True, conduct filtering via Chebyshev approximation. Otherwise signals are filtered in a brute-force way - do a complete eigenvalue decomposition of Laplacian \(L\) to get the GFT and IGFT matrices.

Returns:

Filtered signals. Shape: (N,Co). Co is the output channels.

Return type:

Tensor

GraphQmf FilterBank

class ColorQmf(G: Graph, kernel: Tuple[Callable] | List[Callable] | _SupportsArray[dtype[Any]] | _NestedSequence[_SupportsArray[dtype[Any]]] | bool | int | float | complex | str | bytes | _NestedSequence[bool | int | float | complex | str | bytes] | None = None, in_channels: int = 1, order: int = 24, strategy: str = 'harary', vtx_color: Tensor | _SupportsArray[dtype[Any]] | _NestedSequence[_SupportsArray[dtype[Any]]] | bool | int | float | complex | str | bytes | _NestedSequence[bool | int | float | complex | str | bytes] | List[int] | Tuple[int] | None = None, lam_max: float = 2.0, zero_dc: bool = False, **kwargs)

class NumQmf(G: Graph, kernel: ndarray = None, in_channels: int = 1, order: int = 24, strategy: str = 'admm', level: int = 1, lam_max: float = 2.0, zero_dc: bool = False, **kwargs)

class ColorBiorth(G: Graph, k: int = 8, in_channels: int = 1, order: int = 16, strategy: str = 'harary', vtx_color: Tensor | _SupportsArray[dtype[Any]] | _NestedSequence[_SupportsArray[dtype[Any]]] | bool | int | float | complex | str | bytes | _NestedSequence[bool | int | float | complex | str | bytes] | List[int] | Tuple[int] = None, lam_max: float = 2.0, zero_dc: bool = False, **kwargs)

class NumBiorth(G: Graph, k: int = 8, in_channels: int = 1, order: int = 24, strategy: str = 'admm', level: int = 1, lam_max: float = 2.0, zero_dc: bool = False, **kwargs)

class QmfCore(bipartite_graphs: List[SparseTensor], beta: Tensor | ndarray, analyze_kernels: Tuple[Callable] | List[Callable] | _SupportsArray[dtype[Any]] | _NestedSequence[_SupportsArray[dtype[Any]]] | bool | int | float | complex | str | bytes | _NestedSequence[bool | int | float | complex | str | bytes] | None = None, synthesis_kernels: Tuple[Callable] | List[Callable] | _SupportsArray[dtype[Any]] | _NestedSequence[_SupportsArray[dtype[Any]]] | bool | int | float | complex | str | bytes | _NestedSequence[bool | int | float | complex | str | bytes] | None = None, in_channels: int = 1, order: int = 24, lam_max: float = 2.0, zero_dc: bool = False)

The core implementation of GraphQmf [2] and GraphBiorth [3] filterbanks.

Note

There is no need to change in_channels when the signals of all input channels share a same filterbank since QmfCore can automatically broadcast one filterbank among all input channels.

num_node

The number of nodes.

Type:

int

num_bgraph

The number of bipartite (sub)graphs.

Type:

int

beta

Each column of beta corresponds to one bipartite (sub)graph It has ones at the locations of nodes sampled by the lowpass filter, with zeros at that by the highpass filter.

Type:

(Bool)Tensor(N,M)

analyze_kernels

1. If None, use meyer kernels, following [2].

2. A tuple or list consisting of two kernel functions designed for low-pass and high-pass filtering, separately. Then the other kernels functions for all Co=2^M channels are derived.

3. An array of kernel functions with a shape of (M, Co, Ci). Ci and Co is the #s of input channels, i.e., in_channels and output channels, respectively. Note that Co is the channels of wavelet coefficients and hence is actually 2^M .

Type:

List[function], Tuple[function], np.ndarray[function], optional

synthesis_kernels

This arg is almost the same with analyze_kernels except that this is for synthesis stage.

Type:

List[function], Tuple[function], np.ndarray[function], optional

in_channels

The # of input channels. Default 1. Consider this only when you want to process (N,Ci) graph signals and for all Ci channels you want to build different graphQmf or graphBiorth wavelet filterbanks (via using different analysis and synthesis kernel functions).

Type:

int, optional

order

The order of Chebyshev approximation.

Type:

int, optional

lam_max

Compute the Chebyshev approximation within the interval [0, lam_max].

Type:

float, optional

zero_dc

If True, the zero_dc filter bank is employed.

Type:

bool, optional

References

[2] (1,2)

S K. Naran, et al, “Perfect Reconstruction Two-channel Wavelet Filter Banks for Graph Structured Data”, IEEE TSP, 2012.

[3]

S. Narang and A. Ortega, “Compact support biorthogonal wavelet filterbanks for arbitrary undirected graphs,” IEEE TSP, 2013.

analyze(x)

Conduct a wavelet transform on the input signal.

Note

Although the returned coefficients are a (2^M,N,Ci) tensor Z, there are only N non-zero entries in those coefficients corresponding to one input channel. For instance, Z[..., 0] has only N non-zero items.

Parameters:

x (Tensor) – The signal to transform. Shape: (N,) or (N,Ci). Ci and N are the numbers of input channels and graph nodes, separately.

Returns:

The wavelet coefficients with a shape of (Co,N,Ci) or equally (2^M,N,Ci). M is the # of output channels.

Return type:

Tensor