CIF: Small: Learning Sparse Vector and Matrix Graphs from Time-Dependent Data
PI: J.K. Tugnait, 08/01/23 -- 7/31/26, $600,000.Supported by the National Science Foundation Grant CCF-2308473
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. Graphs, however, 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 choice of the objective function to be optimized, and 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 any 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 functional magnetic resonance imaging 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 where 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 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 where 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.
J.K. Tugnait, "Delay embedding for matrix graphical model learning from dependent data," to be presented at the 2024 IEEE Intern. Conf. Acoustics, Speech & Signal Processing (ICASSP 2024), Seoul, South Korea, April 14-19, 2024.
J.K. Tugnait, "Learning high-dimensional differential graphs from multi-attribute data," IEEE Trans. Signal Processing, vol. 72, pp. 415-431, 2024. [pdf]
J.K. Tugnait, "Estimation of differential graphs from time-dependent data" in 2023 Proc. IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP 2023), pp. 261-265, Los Suenos, Costa Rica, Dec. 10-13, 2023.
Date of latest revision: wed feb 28 2024