Volume Ratio, Sparsity, and Minimaxity under Unitarily Invariant Norms

Abstract

The current paper presents a novel machinery for studying non-asymptotic minimax estimation of high-dimensional matrices, which yields tight minimax rates for a large collection of loss functions in a variety of problems. Based on the convex geometry of finite-dimensional Banach spaces, we first develop a volume ratio approach for determining minimax estimation rates of unconstrained normal mean matrices under all squared unitarily invariant norm losses. In addition, we establish the minimax rates for estimating mean matrices with submatrix sparsity, where the sparsity constraint introduces an additional term in the rate whose dependence on the norm differs completely from the rate of the unconstrained problem. Moreover, the approach is applicable to the matrix completion problem under the low-rank constraint. The new method also extends beyond the normal mean model. In particular, it yields tight rates in covariance matrix estimation and Poisson rate matrix estimation problems for all unitarily invariant norms.

References in corpus (1)

• Finding large average submatrices in high dimensional data

Cited by in corpus (6)

• Computational barriers in minimax submatrix detection
• Distance-based and continuum Fano inequalities with applications to statistical estimation
• Geometric Inference for General High-Dimensional Linear Inverse Problems
• A General Framework for Bayes Structured Linear Models
• Robust Covariance and Scatter Matrix Estimation under Huber's Contamination Model
• Optimal Schatten-q and Ky-Fan-k Norm Rate of Low Rank Matrix Estimation