What is the fastest way to compute the sum of the singular values of a matrix?

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.

• This was posted to Mathematics SE here Sep 27, 2016 at 14:33
• Are you really just interested in computing this norm, or are you interested in finding a matrix that minimizes the norm perhaps subject to some constraints? Do you have reason to believe that your matrix is of low rank? Sep 27, 2016 at 21:05
• For my problem I already know the minimum, or I'm not interested in it anyway. I expect it to be nearly full-rank. Thanks Sep 28, 2016 at 20:42
• The intuition here is that computing this one number from a matrix should be easier than iteratively computing the whole singular value spectrum to great accuracy. However, I haven't come up with anything. Oct 4, 2016 at 13:23

If the matrix $X$ has rank upper-bounded by $r$, then:
$$\left \Vert X \right\Vert_* = \mathrm{inf}_{L,R} \left[\frac{1}{2}\left \Vert L \right\Vert_F^2 + \frac{1}{2}\left \Vert R \right\Vert_F^2 : X = LR^{T}\right ]$$