In Weighted Nuclear Norm Minimization with Application to Image Denoising, it is stated that nuclear norm of a matrix $\mathbf{X}$, given by

$$\|\mathbf{X}\|_{*}=\sum_{i} \sigma_{i}(\mathbf{X})$$

where $\sigma_{i}(\mathbf{X})$ are the singular values, is convex. In the same paper, the weighted nuclear norm, given by

$$\|\mathbf{X}\|_{*,\mathbf{W}}=\sum_{i} w_{(i,i)}\sigma_{i}(\mathbf{X})$$

is non-convex. I am unable to prove this argument with Jensen's inequality. Kindly, help.

  • 1
    $\begingroup$ I actually believe it is convex if the weights are nonincreasing. That is, $w_i\geq w_j$ whenever $\sigma_i\geq\sigma_j$. $\endgroup$ Dec 26, 2014 at 15:40
  • $\begingroup$ A simple case: let $w_n=1$ for $n>1$ and all other weights are zero. That is certainly nonconvex. $\endgroup$ Dec 26, 2014 at 15:43
  • $\begingroup$ The singular values are ordered by definition. That's the key... $\endgroup$
    – Dirk
    Dec 26, 2014 at 16:47
  • $\begingroup$ Right. So consider a 2x2 case, with 2 diagonal matrices. Let the largest singular value be in the (1,1) position for one, and the (2,2) position for the other. Shouldn't be difficult to find a counterexample by choosing the values and weights judiciously. $\endgroup$ Dec 27, 2014 at 13:29
  • 2
    $\begingroup$ And in case it is not clear: you don't "prove nonconvexity" per se; rather you disprove convexity. And you typically do that with a single counterexample: two points that violate the secant inequality at at least one point along the segment. $\endgroup$ Dec 27, 2014 at 13:32


You must log in to answer this question.