CIF:Small:Learning Sparse Vector and Matrix Graphs from Time-Dependent Data

图是经常用于表示数据变量之间的依赖关系或相似性的数学结构。它们可以捕获看似不规则的高维数据中固有的复杂结构，使其成为信号处理、机器学习和数据科学中的宝贵工具。图形模型的应用包括金融、社会网络、环境网络、基因调控网络和功能磁共振成像(FMRI)中的分类和探索性数据分析。然而，图表并不总是显式可用。因此，在给定数据的情况下，学习底层的图形结构对于机器学习和信号处理中的应用是至关重要的。在文献中，在选择要优化的目标函数以及在算法设计和分析中，通常假设时间数据由随机向量或随机矩阵的多个独立实现组成。这一假设在实践中经常被违反。该项目明确考虑与时间相关的数据，不需要任何详细的参数建模来捕获时间依赖关系。预计包含短记忆和长记忆时间相关性的更好的模型将产生更准确的图形拓扑，从而显著改善数据分析和学习任务。在这个框架中也讨论了差图估计的问题，例如，在生物统计应用中，人们可能对给定基因表达数据或功能磁共振信号的健康和受损对象的图形模型或不同疾病状态下的模型的差异感兴趣。在这个项目中，考虑了三个主要的研究主题：短期和长期相关下的多变量依赖时间序列图学习，矩阵值依赖的时间序列图学习，以及差异图学习。在所有三个推进中的焦点都是稀疏图或稀疏差分图，在高维设置下，其中图的大小大于数据样本大小或数据样本大小的数量级。在计算效率和准确性方面，我们将研究从依赖时间的多变量时间序列和矩阵时间序列估计无向赋权图的一般方法。将考虑两类方法：基于数据的离散傅里叶变换的频域方法，该方法在频域中产生近似独立的数据，从而允许利用基于复值信号处理的一系列分析工具；以及基于时间延迟嵌入的时间域方法，将问题归结为多属性图估计问题之一，其中与每个图节点相关联的是随机向量而不是标量。这个问题的所有方面都将被考虑：算法设计和分析，稀疏参数估计的凸正则函数和非凸正则函数下的优化，模型选择(惩罚参数的选择)，理论属性的分析(如一致性和模型恢复)，以及使用公开可用的数据集对真实数据的应用。该项目由通信与信息基金会(CIF)和已建立的激励竞争研究计划(EPSCoR)共同资助。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.