  We consider the twin problems of estimating the effective rank and the
Schatten norms $\|{\bf A}\|_{s}$ of a rectangular $p\times q$ matrix ${\bf A}$
from noisy observations. When $s$ is an even integer, we introduce a
polynomial-time estimator of $\|{\bf A}\|_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.
