DIMACS Special Year on Massive Data Sets Seminar


Optimization algorithms for separable functions with tree-like conjugacy of variables and their application to the analysis of massive sets of seismic data


Vadim Mottl
Tula State University, Russia


DIMACS Seminar Room, 431, 4th Floor, CoRE Building, Rutgers University


3:00 p.m - TIME CHANGE
Thursday, April 10, 1997


A massive data set, in particular, that of seismic data, is considered as a set of experimentally acquired values of a number of variables each of which is associated with the respective node of an undirected conjugacy graph that presets the fixed structure of the data set. The class of data analysis problems under consideration is outlined by the assumption that the ultimate aim of processing can be represented as a transformation of the original data array into a secondary array of the same structure but with node variables of, generally speaking, different nature, i.e. different ranges. Such a generalized problem is set as the formal problem of optimization (minimization or maximization) of a real-valued objective function of all the node variables. The objective function is assumed to consist of additive constituents of one or two arguments, respectively, node and edge functions. The former of them carry the data-dependent information on the sought-for values of the secondary variables, whereas the latter ones are meant to express the a priori model constraints. For the case when the graph of the pair-wise conjugacy of the data set elements has the form of a tree, an effective global optimization procedure is proposed which is based on a recurrent decomposition of the initial optimization problem over all the node variables into a succession of partial problems each of which consists in optimization of a function of only one variable like Bellman functions in the classical dynamic programming. Two kinds of numerical realization of the basic optitimization procedure are considered on the basis of parametrical representation of Bellman functions, respectively, for discretely defined and quadratic node and edge functions. The proposed technique of the optimization of separable functions supported by trees underlies the algorithmic solution of a group of seismic data analysis problems which includes the problems of segmentation of explorative seismic sections through layered underground rock mass, texture analysis of plane and three-dimensional explorative seismic data arrays, and detection of seismic signals.

Joint work with Ilya Muchnik, DIMACS

Document last modified on April 7, 1997