Learning structured models on weighted graphs, with applications to spatial data analysis.

Summary The modeling of complex processes may involve a large number of variables with a complicated correlation structure between them. For example, spatial phenomena often have a strong spatial regularity, resulting in a correlation between variables that is stronger the closer the corresponding regions are. The formalism of weighted graphs allows to capture in a compact way these relations between variables, allowing the mathematical formalization of many spatial data analysis problems. The first part of the manuscript focuses on the efficient solution of spatial regularization problems, involving penalties such as total variation or total contour length. We present a preconditioning strategy for the generalized forward-backward algorithm, specifically adapted to solve problems structured by weighted graphs with high variability of configurations and weights. We then present a new algorithm called cut pursuit, which exploits the relationships between the flow algorithms and the total variation through a working set strategy. These algorithms show superior performance to the state of the art for geostatistical data aggregation tasks. The second part of this paper focuses on the development of a new model that extends continuous time Markov chains to the case of general undirected weighted graphs. This model allows a finer consideration of interactions between neighboring nodes for structured prediction, as illustrated for supervised classification of urban fabrics.