Geometrizing Local Rates of Convergence for Statistical General Linear Inverse Problems

• Activity Number: 26
• Type: Contributed
• Date/Time: Sunday, August 3, 2014 : 2:00 PM to 3:50 PM
• Sponsor: IMS
• Author(s): Tengyuan Liang*+ and Tony Cai and Alexander Rakhlin
• Companies: Wharton School and University of Pennsylvania and Wharton School
• Keywords: inverse problem ; atomic norm ; Gaussian width ; convex geometry ; minimax lower bound ; local rate of convergence

Abstract

Ill-posed inverse problems including high dimensional regression, trace regression, sign vector recovery, orthogonal matrix recovery and permutation matrix recovery pose many challenges for engineers, applied mathematicians and statisticians in the past few years. In a recent paper, Chandrasekaran et al. introduced the atomic norm in convex geometry to address a wide class of linear inverse problem simultaneously in the noiseless setting. In our paper, we attack the general linear inverse problems in noisy setting following this line of research. Our research is two folded. Firstly, we show that the local upper bound on rate of convergence of the atomic norm constrained minimization procedure depends on three mathematical terms capturing local convex geometry. In addition, we prove the minimum sample size to ensure the statistical convergence and optimization feasibility of the procedure in terms of dimension, Gaussian width and atomic norm. Secondly, we provide global statistical minimax lower bound for general linear inverse problem, which depends on dimension, sample size and volume ratio driven by the geometry. This is a joint work with Tony Cai and Alexander Rakhlin.