CIF: Medium: Collaborative Research: Estimating simultaneously structured models: from phase retrieval to network coding

在现代数据密集型科学和工程中，研究人员面临着可用观测值远远小于待估计模型维度的估计模型。压缩感知、矩阵补全以及其他这类问题成功的关键是适当地利用关于模型“结构”的知识。虽然像稀疏性这样的结构已经被单独研究，但“同时结构”的问题却被忽视了，因为从业者隐含地假设，简单地将每个结构的已知结果结合起来就可以解决联合问题。有趣的是，pi最近证明，这种方法可能导致巨大的差距。本提案将发展理论和计算上易于处理的方法来估计同时具有最小观测值的结构模型。它结合了(1)一种自上而下的方法来理解基于结构如何相互作用的几何结构的基本限制，以及(2)一种特定于问题的、自下而上的方法来利用领域知识来构建适当的惩罚。这项工作涉及各种应用，包括(1)稀疏主成分分析，这是统计中寻求近似但稀疏特征向量的中心问题，(2)信号处理中的稀疏相位检索和二次压缩感知，以及(3)通信和网络编码的代码设计。从数据中系统地导出结构化模型的能力将对大数据和普适计算时代的工程挑战产生深远的影响。处理具有多个结构的模型提出了深刻的理论和计算挑战，这是本提案的重点。讨论了在机器学习、信号处理和网络编码中的应用。pi将把研究成果纳入他们的教学，组织技术研讨会，将数学家和工程师聚集在一起，并通过暑期研究项目寻求本科生参与这项工作。

In modern data-intensive science and engineering, researchers are faced with estimating models where available observations are far fewer than the dimension of the model to be estimated. The key to the success of compressed sensing, matrix completion, and other problems of this type, is to properly exploit knowledge about the "structure" of the model. While structures such as sparsity have been separately studied, the problem of "simultaneous structures" has been neglected, since it is implicitly assumed by practitioners that simply combining known results for each structure would solve the joint problem. Interestingly, the PIs recently proved that this approach can result in a significant gap.This proposal will develop theory and computationally tractable methods for estimating simultaneously structured models with minimal observations. It combines (1) a top-down approach to understand the fundamental limitations based on the geometry of how structures interact, and (2) a problem-specific, bottom-up approach to exploit domain knowledge in constructing appropriate penalties. This work addresses a variety of applications including (1) sparse principal component analysis, a central problem in statistics seeking approximate but sparse eigenvectors, (2) sparse phase retrieval and quadratic compressed sensing in signal processing, and (3) code design for communications and network coding.The ability to systematically derive structured models from data will have far-reaching impact on engineering challenges in the era of Big Data and ubiquitous computing. Handling models with multiple structures poses deep theoretical and computational challenges that this proposal focuses on. Applications in machine learning, signal processing, and network coding are discussed. The PIs will incorporate research results in their teaching, organize technical workshops to bring together mathematicians and engineers, and seek the involvement of undergraduate students in this work through summer research programs.