Volume Ratio, Sparsity, and Minimaxity Under Unitarily Invariant Norms

Zongming Ma, Yihong Wu

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Article number7293186
Pages (from-to)6939-6956
Number of pages18
JournalIEEE Transactions on Information Theory
Volume61
Issue number12
DOIs
StatePublished - Dec 2015

Keywords

  • Convex geometry
  • Matrix completion
  • Matrix estimation
  • Minimax risk
  • Poisson rate matrix
  • Sparsity
  • Unitarily invariant norm

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences

Fingerprint Dive into the research topics of 'Volume Ratio, Sparsity, and Minimaxity Under Unitarily Invariant Norms'. Together they form a unique fingerprint.

Cite this