Novel Matrix Problems in Modern Applications

现代应用中的新矩阵问题

• 批准号: 0431257
• 负责人: Inderjit Dhillon
• 金额: --
• 依托单位: University of Texas at Austin
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2004
• 资助国家: 美国
• 起止时间: 2004-08-15 至 2009-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0431257&HistoricalAwards=false
• 关键词: Novel; Matrix; Problems; Modern; Applications

Matrix computations are ubiquitous in scientific and engineering applications.The existence of high-quality algorithms and resulting software packages, such asLAPACK and MATLAB, greatly alleviates the burden on scientists and engineers, allowingthem to devote their energy to the particular application at hand.This proposal is addressed towards identifying and solving some novel and fundamental matrixproblems that arise in modern applications. The last decade hasseen significant advances in communications technology and infrastructure;prime examples are the world-wide web, wireless computing and sensor networks.These modern applications lead to a vast variety of interesting problems --- these rangefrom complex design constructions, data warehousing and retrieval problems, to the need for intelligent analysis of huge amounts of data. As a response to these needs,many new matrix problems arise that need to be solved robustly and efficiently.Some of the most challenging problems in the analyses of large data matrices are therelated problems of clustering, co-clustering (simultaneous clusteringof rows and columns), and matrix approximations. In many applications, the datais not Gaussian, and hence traditional techniques, such as singular valuedecomposition (SVD) and classical Euclidean k-means are often inadequate.The proposed project formulates new matrix approximation problems related toco-clustering: these formulations appeal to a generalized maximum entropy principleto search for structured matrix approximations that arise naturally for an importantclass of statistical distributions, known as exponential families. The aim of theproject is to develop the theory as well as robust, numerical software for thesematrix computations.Another important class of problems contains varied inverse problems: givena set of desirable properties, construct a data matrix that satisfies these properties.Such inverse problems arise in diverse applications, such as the design ofkernel similarity matrices for statistical learning and the design of Gram matriceswith low cross-correlations for wireless communications. The plan is touse alternate projection schemes, and numerical optimization to solve such designproblems. The outcome of the project would be a unified framework for these inverseproblems, including modeling, algorithms and software.It is anticipated that there will be two broad research impacts of the proposed project.The first contribution would be to applied mathematics and computer science--- the formulation and proposed solutions of the novel matrix problems thatarise naturally in applications. It is hoped that the proposed work will vitalize thesearch for better algorithms, and further deepen the connections between applied mathematicsand engineering. The second contribution would be to the applications themselves. Posing particularapplication tasks in terms of well-defined matrix problems should lead to fasterand more reliable methods.The project will support the graduate education of 2 or 3 students. These students will be trained in themultidisciplinary areas of computational linear algebra, data mining, statistical pattern recognition and wireless computing. Specialized courses in all these areas are available in the Computer Science,Applied Mathematics and Electrical & Computer Engineering departments at UT Austin.Such a broad education will fill the need for substantial academic and industrial demand in thesemultidisciplinary areas for educated personnel.The project will also support research experience for one undergraduate, and a conscious effortwill be made to recruit women and minority students.Results of the project will be published in the linear algebra, data-mining, and information theoryliteratures, contributing to each of these areas as well as their cross-fertilization.Data and software developed under the project will be shared with the scientific communityvia a public web site.

矩阵计算在科学和工程应用中无处不在.高质量的算法和软件包的存在，如LAPACK和MATLAB，大大减轻了科学家和工程师的负担，使他们能够将精力投入到手头的特定应用中.本文提出了识别和解决现代应用中出现的一些新的和基本的矩阵问题.在过去的十年里，通信技术和基础设施取得了显著的进步，主要的例子是万维网、无线计算和传感器网络。这些现代应用导致了各种各样有趣的问题---从复杂的设计结构、数据仓库和检索问题，到对大量数据进行智能分析的需求。作为对这些需求的响应，出现了许多新的矩阵问题，需要鲁棒和有效地解决。在大型数据矩阵分析中，一些最具挑战性的问题是聚类，共聚类（行和列的同时聚类）和矩阵近似的相关问题。在许多应用中，数据不是高斯的，因此传统的技术，如奇异值分解（SVD）和经典的欧几里得k均值往往是不够的。拟议的项目制定了新的矩阵近似问题相关的共同聚类：这些公式诉诸于广义最大熵原理来搜索对于一类重要的统计分布自然出现的结构化矩阵近似，称为指数族。该项目的目的是为这些矩阵计算开发理论和强大的数值软件。另一类重要的问题包括各种逆问题：给定一组期望的属性，构造满足这些属性的数据矩阵。这样的逆问题出现在各种应用中，例如用于统计学习的核相似性矩阵的设计和用于无线通信的具有低互相关的Gram矩阵的设计。该计划是使用交替投影格式，数值优化来解决这样的设计问题。该项目的成果将是这些反问题的统一框架，包括建模、算法和软件。预计该项目将产生两个广泛的研究影响。第一个贡献将是应用数学和计算机科学-在应用中自然出现的新矩阵问题的公式化和提出的解决方案。希望本文的工作能为算法的研究注入新的活力，并进一步加深应用理论与工程的联系。 第二个贡献是应用程序本身。根据定义明确的矩阵问题提出特定的应用任务，应该会导致更快和更可靠的方法。该项目将支持2或3名学生的研究生教育。这些学生将接受计算线性代数、数据挖掘、统计模式识别和无线计算等多学科领域的培训。所有这些领域的专业课程都可以在UT Austin的计算机科学，应用数学和电子&计算机工程系中获得。这样一个广泛的教育将满足这些多学科领域对受过教育的人员的大量学术和工业需求。该项目还将支持一个本科生的研究经验，并有意识地努力招募女性和少数民族学生。该项目的结果将发表在线性代数，数据挖掘和信息理论文献，在该项目下开发的数据和软件将通过一个公共网站与科学界分享。