Complexity Penalization in High Dimensional Matrix Estimation Problems

Georgia Tech Research Corporation, Atlanta GA

Investigators

Abstract

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.