ABSTRACT

Graphs are mathematical structures that are frequently used to express dependencies or similarities among data variables. They can capture complex structures inherent in seemingly irregular high-dimensional data, making them an invaluable tool in signal processing, machine learning, and data science. Applications of graphical models include classification and exploratory data analysis in finance, social networks, environmental networks, gene regulatory networks, and functional magnetic resonance imaging (fMRI). However, graphs are not always explicitly available. Therefore, given data, learning the underlying graph structure is central to applications in machine learning and signal processing. In the literature, it is typically assumed that the temporal data consists of multiple independent realizations of a random vector or matrix in the choice of the objective function to be optimized as well as in algorithm design and analysis. This assumption is often violated in practice. This project explicitly considers time-dependent data, without requiring any detailed parametric modeling to capture time dependencies. It is anticipated that better models incorporating short- and long-memory time dependence will yield more accurate graph topology, hence, significant improvements in data analysis and learning tasks. The problem of differential graph estimation is also addressed in this framework where, for example, in a bio-statistical application, one may be interested in the differences in the graphical models of healthy and impaired subjects, or models under different disease states, given gene-expression data or fMRI signals.

In this project, three main research thrusts are considered: multivariate dependent time-series graph learning under both short- and long-range dependence, matrix-valued dependent time-series graph learning, and differential graph learning. The focus in all three thrusts is on sparse graphs or sparse differential graphs, under high-dimensional settings wherein the graph size is greater than, or of the order of, the data sample size. Computationally efficient and accurate, general approaches for estimation of undirected weighted graphs from time-dependent multivariate as well as matrix-valued time series will be investigated. Two classes of approaches will be considered: frequency-domain approaches based on the discrete Fourier transform of data which yields approximately independent data in the frequency domain, allowing a broad set of analysis tools based on complex-valued signal processing to be exploited; and time-domain approaches based on time-delay embedding, casting the problem as one of multi-attribute graph estimation wherein a random vector, instead of a scalar, is associated with each graph node. All aspects of the problem will be considered: algorithm design and analysis, optimization under both convex and non-convex regularizing functions for sparse parameter estimation, model selection (choice of penalty parameters), analysis of theoretical properties (such as consistency and model recovery), and application to real data using publicly available data sets.

This project is jointly funded by the Communications & Information Foundations (CIF) and the Established Program to Stimulate Competitive Research (EPSCoR) programs.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

Please report errors in award information by writing to: awardsearch@nsf.gov.