Optimized Update/Prediction Assignment for Lifting Transforms on Graphs
Transformations on graphs can provide compact representations of signals with many applications in denoising, feature extraction, or compression. In particular, lifting transforms have the advantage of being critically sampled and invertible by construction, but the efficiency of the transform depends on the choice of a good bipartition of the graph into update (<inline-formula><tex-math notation="LaTeX">$\mathcal{U}$</tex-math></inline-formula>) and prediction (<inline-formula><tex-math notation="LaTeX">$\mathcal{P}$</tex-math></inline-formula>) nodes. This is the update/prediction (<inline-formula><tex-math notation="LaTeX">$\mathcal{U}/\mathcal{P}$</tex-math></inline-formula>) assignment problem, which is the focus of this paper. We analyze this problem theoretically and derive an optimal <inline-formula><tex-math notation="LaTeX">$\mathcal{U}/\mathcal{P}$</tex-math></inline-formula> assignment under assumptions about signal model and filters. Furthermore, we prove that the best <inline-formula> <tex-math notation="LaTeX">$\mathcal{U}/\mathcal{P}$</tex-math></inline-formula> partition is related to the correlation between nodes on the graph and is not the one that minimizes the number of conflicts (connections between nodes of same label) or maximizes the weight of the cut. We also provide experimental results in randomly generated graph signals and real data from image and video signals that validate our theoretical conclusions, demonstrating improved performance over state-of-the-art solutions for this problem.