Optimal Estimation of Schatten Norms of a rectangular Matrix

Abstract

We consider the twin problems of estimating the effective rank and the Schatten norms $\Vert \mathbf{A}{\Vert }_s$ of a rectangular $p\times q$ matrix $\mathbf{A}$ from noisy observations. When $s$ is an even integer, we introduce a polynomial-time estimator of $\Vert \mathbf{A}{\Vert }_s$ that achieves the minimax rate $(pq{)}^{1/4}$. Interestingly, this optimal rate does not depend on the underlying rank of the matrix. When $s$ is not an even integer, the optimal rate is much slower. A simple thresholding estimator of the singular values achieves the rate $(q\wedge p)(pq{)}^{1/4}$, which turns out to be optimal up to a logarithmic multiplicative term. The tight minimax rate is achieved by a more involved polynomial approximation method. This allows us to build estimators for a class of effective rank indices. As a byproduct, we also characterize the minimax rate for estimating the sequence of singular values of a matrix.

67 pages

References in corpus (6)

• Testing composite hypotheses, Hermite polynomials and optimal estimation of a nonsmooth functional
• Minimax estimation of linear and quadratic functionals on sparsity classes
• Local moment matching: A unified methodology for symmetric functional estimation and distribution estimation under Wasserstein distance
• On Estimation of $L_r$-Norms in Gaussian White Noise Models
• Dualizing Le Cam's method for functional estimation, with applications to estimating the unseens
• Spectrum Estimation from a Few Entries