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

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

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.