Volume Ratio, Sparsity, and Minimaxity Under Unitarily Invariant Norms

This paper studies non-asymptotic minimax estimation of high-dimensional matrices and provides tight minimax rates for a large collection of loss functions in a variety of problems via information-theoretic methods. Based on the convex geometry of finite-dimensional Banach spaces, we first develop a volume ratio approach for determining minimax estimation rates of unconstrained mean matrices under all unitarily invariant norm losses, which turn out to only depend on the norm of identity matrix. In addition, we establish the minimax rates for estimating normal mean matrices with submatrix sparsity, where the sparsity constraint introduces an additional term in the rate which, in contrast to the unconstrained case, is determined by the smoothness (Lipschitz constant) of the norm. This method is also applicable to the low-rank matrix completion problem and extends well beyond the additive noise model. In particular, it yields tight rates in covariance matrix estimation and Poisson rate matrix estimation problems for all unitarily invariant norms.