The nuclear norm of a matrix is defined as the sum of its singular values, as given by the singular value decomposition (SVD) of the matrix itself. It is of central importance in Signal Processing and Statistics, where it is used for matrix completion and dimensionality reduction.
A question I have is whether it's possible to compute the nuclear norm of a given matrix faster than the time needed to compute the SVD. Since we don't need all the singular values but only their sum, this seem possible. Alternatively, perhaps it could be possible to approximate it with simulation methods and/or random projections.