Lifting transforms on graphs: theory and applications
Godwin Shen · 2015
There are many scenarios in which data can be organized onto a graph or tree. Data may also be similar across neighbors in the graph, e.g., data across neighboring sample points may be spatially correlated. It would therefore be useful to apply some form of transform across neighboring sample points in the graph to exploit this correlation in order to achieve more compact representations. To this end, we describe a general class of de-correlating lifting transforms that can be applied to any graph or tree, and propose a variety of transform optimizations. We mainly focus on the design of tree-based lifting transform designs. Extensions to graph-based lifting transforms are also discussed. As a first application, we develop distributed graph-based transforms for efficient data gathering in wireless sensor networks (WSNs), where the goal is to transmit data from every node in the network to a collection (or sink) node along a routing tree. In particular, we (i) propose a general class of unidirectional transforms that can be computed in a distributed manner as data is routed toward the sink, and (ii) provide conditions for their invertibility. Moreover, we show that any unidirectional lifting transform is invertible, and propose a variety of tree-based lifting transform designs. By using these transforms to de-correlate data in the network, the total communication cost for data gathering is significantly reduced. We also extend these tree-based lifting transforms to incorporate broadcast communication links. This leads to a set of graph-based lifting transforms for WSNs. In particular, nodes incorporate data received from their broadcast neighbors together with data received from their neighbors in the routing tree. By doing so, they are able to achieve more data de-correlation. By exploiting the additional broadcast communication links in this way, these graph-based lifting transforms reduce the total communication cost even further.