Is there a faster way to compute the nuclear norm (trace norm, sum of singular values) of a matrix A than computing SVD(A) directly (or diagonalizing A^*A)?
I am particularly interested in the case where A is square. Assuming that A is real would be OK too. I am thinking in the limit of large matrices.