The details of perfect reconstruction graph filter banks are provided in the next section.
While R can be arbitrary, one may need a symmetric structure: the synthesis transform represented by multiple filters and upsampling as a counterpart of the analysis transform. In classical signal processing, most filter banks are designed to be symmetric, which, in contrast, is difficult for the graph versions, mainly due to the sampling operations. Several design methods make it possible to design perfect reconstruction graph transforms with a symmetric structure (Narang and Ortega 2012; Narang and Ortega 2013; Shuman et al. 2015; Leonardi and Van De Ville 2013; Tanaka and Sakiyama 2014; Sakiyama and Tanaka 2014; Sakiyama et al. 2016; Sakiyama et al. 2019a; Teke and Vaidyanathan 2016; Sakiyama et al. 2019b).
1.5.2. Perfect reconstruction condition
Suppose that the redundancy is ρ ≥ 1 and the columns of E are linearly independent. The perfect reconstruction condition equation [1.38] is clearly rewritten as
[1.39]
The critically sampled system constrains that E is a square matrix; therefore, R must be E−1 for perfect reconstruction. For the oversampled system, we generally have an infinite number of R satisfying the condition in equation [1.39]. The most simple and well-known solution is the least squares solution, which is expressed as
[1.40]
This is nothing but the Moore–Penrose pseudo inverse of E4. This GSP system is generally asymmetric: while the analysis transform has graph filters and possible sampling, the synthesis transform does not have such a clear notion of filtering and upsampling. In general, the asymmetric structure requires a matrix inversion. Additionally, the N × N matrix ETE is usually dense, which leads to
Therefore, symmetric structures are often desired instead, and they are similar to those that are widely used in classical signal processing. The synthesis transform with a symmetric structure has the following form:
[1.41]
where gk(L) is the kth synthesis filter and
[1.42]
reconstruction, it must be x.The resulting output is therefore represented as
1.5.2.1. Design of perfect reconstruction transforms: undecimated case
There are various methods available for designing perfect reconstruction graph transforms. First, let us consider undecimated transforms that exhibit symmetrical structure.
An undecimated transform has no sampling, i.e. Sk = IN for all k. Therefore, the analysis and synthesis transforms, respectively, are represented in the following simple forms:
[1.43]
[1.44]
Accordingly, the perfect reconstruction condition can also be simple. The input–output relationship in equation [1.42] is reduced to
[1.45]
Assuming pk(L) := gk(L)hk(L) as the kth product filter, the output signal is thus given by
[1.46]
Therefore, the product filters must satisfy the following condition for perfect reconstruction:
[1.47]
where c is some constant.
Suppose that hk(L) and gk(L) are parameterized as
[1.48]
where
[1.49]
If c = 1, the frame is called a Parseval frame. In this case, it conserves the energy of the original signal in the transformed domain. Tight spectral graph filter banks can be constructed by employing the design methods of tight frames in classical signal processing. Examples can be found in Leonardi and Van De Ville (2013); Shuman et al. (2015); Sakiyama et al. (2016).
1.5.2.2. Design of perfect reconstruction transforms: decimated case
Constructing perfect reconstruction graph transforms with sampling is much more difficult than the undecimated version. However, it is required as the storage cost can be increased tremendously for the undecimated versions, especially for signals on a very large graph. Though the general
