Gabor-type frames for signal processing on graphs (Q2663266)

The authors propose a general framework for constructing Gabor-type frames for signals on graphs. A signal \(f\) on a graph \(\Gamma\) with \(N\) vertices is a complex-valued function defined on the vertex set of \(\Gamma\) and can be identified with a column vector on \(\mathbb{C}^N\). Let us fix an orthonormal basis \(\{\Phi_j\}_{j=1}^{N}\) of \(\mathbb{C}^N\), a set \(A_1,\ldots A_S\) of complex \(N\times N\) matrices and a window \(g\in \mathbb{C}^N\). The main result of the paper characterizes when the set of vectors \(\{g_{m,\ell}: m=1,\ldots,S; \ell = 1, \ldots, N\}\) forms a frame for \(\mathbb{C}^N\), where \[ g_{m,\ell} = \Phi_\ell \circ (A_m g) \] and \(\circ\) denotes the entrywise product. This generalizes several known frame constructions, for which also sharp frame bounds are obtained. Special emphasis is made in the case that the translations \(g\mapsto A_mg\) are defined using Fourier multipliers and/or \(\Gamma\) is a Cayley graph and the orthonormal basis \(\{\Phi_j\}_{j=1}^{N}\) is formed by appropriate eigenvectors of the adjacency or Laplacian matrix of \(\Gamma\).