Graph Signal Processing: The 2D Companion Model

Many Graph Signal Processing (GSP) applications consider product graphs, the product of smaller graphs. For example, with time-varying graph data, the graph shift can be the (Cartesian) product of a space graph and the cyclic time shift. Instead of treating the product graph as a single entity and applying existing GSP techniques, there are computational and experimental advantages to considering the product graph as the product of its factors.Recently, in 1, we showed that GSP is DSP plus boundary conditions (b.c.) in the companion model that we introduced. Under certain conditions, any graph can be converted into a companion graph consisting of a 1D directed path graph augmented with appropriate b.c.. However, when applied to the product graph, the 1D companion model treats the graph as a single entity, producing a 1D path graph with b.c. that cannot be expressed as a product of two graphs, losing the computational and experimental advantages of product graphs.The paper develops a 2D companion model for the product graph in GSP. Our model shows that by considering the product graph in terms of its factors, the 2D companion shift is a 2D directed grid with b.c. in both directions. We show that, under this 2D companion model, GSP is DSP plus b.c. in the multiple dimension case.