Online Dictionary Learning for Dependent and Multimodal Data Samples: Convergence, Complexity, and Applications

人类最显著的能力之一是从影响日常决策的不断发展的信息流中提取基本模式的能力。在线字典学习（ODL）是一种模拟人类实时提取模式能力的数学公式。ODL在文本分析、图像重建和去噪、医学成像和生物信息学等各个领域都有卓有成效的应用。然而，现有的ODL理论和算法在处理现代流数据时面临着巨大的挑战。该项目将促进现有ODL方法的理论理解和算法能力。更具体地说，该项目将解决处理具有多模态属性的流数据的挑战，用于进一步分类或推理任务的部分标签，以及网络形式的异构结构。该项目还将涉及跨学科合作，并为各级学生提供研究机会。本项目旨在从以下几个方面推进ODL的理论和算法：1)获得马尔可夫依赖下结构化信号流的广义ODL算法到平稳点的最坏收敛速度和迭代复杂度；2)设计有监督的ODL算法，从标记的流数据中学习分类字典，具有可证明的收敛保证和收敛速度；3)利用具有张量值信号的监督式ODL的理论和算法，发展监督式和时态式网络字典学习方法，前者从网络数据中学习判别基子图，用于网络分类和去噪，后者学习基子图及其时间演化，用于重构给定的时态或多层网络。一个关键因素是开发随机最大化最小化类型算法，该算法可以使用块最小化和正则化技术处理复杂的代理函数，这取决于数据类型。该项目还将为学生提供优化、机器学习和网络科学方面的研究经验。本科生研究经验的具体主题将包括为各种现实世界的网络生成最佳网络词典库，生物网络的网络级回归和推理实验，以及时间大脑网络分析。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

One of the remarkable human capabilities is the ability to extract essential patterns from a constantly evolving stream of information that shapes everyday decision-making. Online dictionary learning (ODL) is a mathematical formulation that emulates the human ability to extract patterns in real time. ODL has found fruitful applications in various domains such as text analysis, image reconstruction and denoising, medical imaging, and bioinformatics. However, existing theories and algorithms for ODL are facing significant challenges in coping with modern streaming data. This project will advance both the theoretical understanding and algorithmic capacities of existing ODL methods. More specifically, the project will address challenges in handling streaming data with multi-modal attributes, partial labels for further classification or inference tasks, and heterogeneous structure in the form of networks. This project will also involve interdisciplinary collaboration and provide research opportunities for students at all levels. The project aims to advance the theory and algorithms of ODL in the following aspects: 1) Obtain the worst-case rate of convergence and iteration complexity of generalized ODL algorithms to stationary points for a stream of structured signals under Markovian dependence; 2) Devise supervised ODL algorithms for learning class-discriminating dictionaries from labeled streaming data with provable convergence guarantees and rate of convergence; 3) Use the theory and algorithm for supervised ODL with tensor-valued signals to develop methods of supervised and temporal network dictionary learning, where the former will learn discriminative basis subgraphs from network data for network classification and denoising applications and the latter will learn basis subgraphs and their time-evolution for reconstructing given temporal or multilayer networks. A key element is the development of stochastic majorization-minimization type algorithms that can handle complex surrogate functions depending on data type using block-minimization and regularization techniques. This project will also provide students with research experiences in optimization, machine learning, and network science. Specific topics for undergraduate research experience will include generating a repository of optimal network dictionaries for various real-world networks, network-level regression and inference experiments with biological networks, and temporal brain network analysis.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.