Complexity Penalization in High Dimensional Matrix Estimation Problems

高维矩阵估计问题中的复杂度惩罚

• 批准号: 1207808
• 负责人: Vladimir Koltchinskii
• 金额: $ 30万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2012
• 资助国家: 美国
• 起止时间: 2012-07-01 至 2016-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1207808&HistoricalAwards=false
• 关键词: Complexity; Penalization; Dimensional; Matrix; Estimation

The investigator will study a variety of problems of estimation of large matrices based on noisy measurements of linear functionals of these matrices. The main focus is on the problems where the target matrix is either low rank, or it can be well approximated by low rank matrices. The proposed estimation methods are based on empirical risk minimization with complexity penalties that favor low rank solutions and the objective is to obtain sharp bounds on the estimation error (in particular, low rank oracle inequalities) that show how it depends on the important parameters of the problem such as the level of the noise, the sample size, the size and the rank of the target matrix. The problems to be studied include: (a) new low rank oracle inequalities for trace regression providing a bridge between known results in the noiseless case and in the noisy case for more complex models of design distribution; (b) estimation of density matrix in quantum state tomography with a goal of studying both the least squares method in matrix regression setting and the maximum likelihood method for more general measurement models with proper complexity penalization; (c) estimation (learning) of low rank kernels on graphs and manifolds with a goal of developing new methods of predicting similarities between vertices of a graph or points in an unknown manifold embedded in a Euclidean space.This project is in a very active interdisciplinary area of high-dimensional matrix estimation that is borderline between statistics, mathematics and computer science, and it will facilitate research collaborations between these areas. It will provide a better understanding of subtle aspects of high-dimensional problems of matrix estimation and of complexity regularization in these problems. The problem of estimation of large matrices is very basic in high-dimensional statistics and in a variety of its applications in such areas as signal and image processing, compressed sensing, bioinformatics, quantum information and quantum statistics, high-dimensional data visualization and visual analytics. In these problems, it is of importance to find low-dimensional structures in high-dimensional data that reflect basic relationships between the variables describing complex high-dimensional systems. In the case of matrix problems, finding such structures can be reduced to estimation of low rank matrices and the proposed project will result in a better understanding of the existing methods as well as in the development of new methods of low rank matrix recovery.

研究人员将根据这些矩阵的线性泛函的噪声测量来研究大型矩阵估计的各种问题。主要关注的是目标矩阵要么是低秩的，要么是可以通过低秩矩阵很好地近似的问题。所提出的估计方法基于经验风险最小化，具有有利于低秩解决方案的复杂性惩罚，目标是获得估计误差的尖锐界限（特别是低秩预言不等式），以显示它如何取决于重要参数诸如噪声水平、样本大小、目标矩阵的大小和秩等问题。要研究的问题包括： (a) 用于迹回归的新低阶预言不等式，为更复杂的设计分布模型在无噪声情况和噪声情况下的已知结果之间提供桥梁； (b) 量子态断层扫描中密度矩阵的估计，目的是研究矩阵回归设置中的最小二乘法和具有适当复杂性惩罚的更一般测量模型的最大似然法； (c) 估计（学习）图和流形上的低阶核，目标是开发预测图的顶点或嵌入欧几里德空间中的未知流形中的点之间的相似性的新方法。该项目是一个非常活跃的跨学科项目高维矩阵估计领域是统计学、数学和计算机科学的边界，它将促进这些领域之间的研究合作。它将提供对矩阵估计高维问题的微妙方面以及这些问题中的复杂性正则化的更好理解。大矩阵的估计问题是高维统计及其在信号和图像处理、压缩感知、生物信息学、量子信息和量子统计、高维数据可视化和可视化分析等领域的各种应用中非常基础的问题。在这些问题中，在高维数据中找到低维结构非常重要，这些结构反映了描述复杂高维系统的变量之间的基本关系。在矩阵问题的情况下，找到这样的结构可以简化为低秩矩阵的估计，并且所提出的项目将导致更好地理解现有方法以及开发低秩矩阵恢复的新方法。