Is there a "trick" to calculate the sum of singular values of a matrix $A$, without actually finding them?

For example, the sum of the squared singular values is $\operatorname{trace}(A^TA)$.

  • 3
    $\begingroup$ If $A$ is symmetric positive definite, then the sum of the singular values of $A$ is equal to the trace of $A$. $\endgroup$ – littleO May 15 '17 at 9:13
  • $\begingroup$ If you know or believe that $A$ is low-rank, use Arpack for the biggest $k$ eigenvalues of $A^T A$ (without expanding $A^T A$): see rapidly-determining-whether-or-not-a-dense-matrix-is-of-low-rank. $\endgroup$ – denis May 17 '18 at 16:12

This is a very important current research topic with wide applications in signal/image processing and other applied math areas. In most of this applications, one doesn't have the luxury of computing the full SVD or it is needless to compute the singular vectors. In literature, the value you asked is referred to as nuclear norm. Start looking at research related to low-rank approximations which is very much related to nuclear norm. I will try to give you some feel about it. Say that $A$ is a $M\times N$ matrix and its rank is $r$, such that $r << \min(M,N)$. To give you an example, consider the following non-linear optimization problem $$\min_{U,V}~~\mathop{trace}(U^TAV) \\s.t.~~U^TU=I,~V^TV=I$$ to find partially orthogonal matrices $U$ (of dimension $M\times r$) and $V$ (of dimension $N\times r$). Partially orthogonal here means the columns are orthonormal. In fact, the true solution to this would be the so-called thin-SVD (as opposed to full-SVD) and the objective value would be the nuclear norm. If you resort to fast sub-optimal approaches, you will start getting estimates of the nuclear norm which is what you are seeking. Also, see the webpage of popular convex package CVXOPT for their method on nuclear norm approximation (also see references therein)

  • $\begingroup$ @catch22 imho, you could wait for other answers as this is a very important and relevant question. Probably others can give more interesting insights. Feel free to unaccept mine!!. $\endgroup$ – dineshdileep May 17 '17 at 5:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.