Estimation of High-Dimensional Matrices: Nuclear Norm Regularization and Restricted Strong Convexity

• Activity Number: 219
• Type: Invited
• Date/Time: Monday, August 1, 2011 : 2:00 PM to 3:50 PM
• Sponsor: IMS
• Author(s): Martin Wainwright*+ and Sahand Negahban and Alekh Agarwal
• Companies: University of California at Berkeley and University of California at Berkeley and University of California at Berkeley

Abstract

Problems that involve estimating a high-dimensional matrix that is low-rank, or well-approximated by a low rank matrix, arise in various applications. Examples include multi-task regression, identification of vector autogressive processes, compressed sensing, and matrix completion. A natural M-estimator is based on minimizing a loss function combined with a nuclear norm regularizer, corresponding to the sum of the singular values. For such estimators, we provide non-asymptotic bounds on the Frobenius norm error that hold for a general class of noisy observation models. These results are based on the loss function satisfying a form of restricted strong convexity (RSC). We show that suitable forms of this RSC condition are satisfied for many statistical models under high-dimensional scaling, including the problem of weighted matrix completion, for which restricted isometry conditions are violated. We also discuss how this same condition can be used to prove globally geometric convergence of simple iterative algorithms for solving the convex program.

Based on joint works with Alekh Agarwal and Sahand Negahban.