Fast computation/estimation of the nuclear norm of a matrix

Since you asked for an approximation as well, you might find the paper "Some simple estimates for singular values of a matrix" by Liqun Qi useful. There are some nice estimates there.

However, if these are not precise for you, you might consider computing SVD with a low precision, i.e., do one or two or three iterations and then use the above estimates. Depending on the size of your matrices, this might give a nice speedup.

Since the estimates are of the form $\sigma_i \in [ a_i, b_i ]$, you will also have an estimate of error, so you can do iterations of SVD computation until the absolute error $\sum_i (b_i - a_i)$, or some of its relative counterparts, is small enough.

Apart from that, I don't think there is much to be done. SVD exists to avoid the computation of $A^*A$ when you want these eigenvalues, so such tricks would not help, unless your matrices have some nice properties you didn't mention.

Estimates and approximations are really not my area of interest, so maybe there are results newer than the above paper.