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.