Nonlinear Multilayered Representation of Graph-Signals

We propose a nonlinear multiscale decomposition of signals defined on the vertex set of a general weighted graph. This decomposition is inspired by the hierarchical multiscale (BV,L ²) decomposition of Tadmor, Nezzar, and Vese (Multiscale Model. Simul. 2(4):554–579, 2004). We find the decomposition by iterative regularization using a graph variant of the classical total variation regularization (Rudin et al, Physica D 60(1–4):259–268, 1992). Using tools from convex analysis, and in particular Moreau’s identity, we carry out the mathematical study of the proposed method, proving the convergence of the representation and providing an energy decomposition result. The choice of the sequence of scales is also addressed. Our study shows that the initial scale can be related to a discrete version of Meyer’s norm (Meyer, Oscillating Patterns in Image Processing and Nonlinear Evolution Equations, 2001) which we introduce in the present paper. We propose to use the recent primal-dual algorithm of Chambolle and Pock (J. Math. Imaging Vis. 40:120–145, 2011) in order to compute both the minimizer of the graph total variation and the corresponding dual norm. By applying the graph model to digital images, we investigate the use of nonlocal methods to the multiscale decomposition task. Since the only assumption needed to apply our method is that the input data is living on a graph, we are also able to tackle the task of adaptive multiscale decomposition of irregularly sampled data sets within the same framework. We provide in particular examples of 3-D irregular meshes and point clouds decompositions.