# How is the nuclear norm convex whereas the weighted nuclear norm is not?

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.

• I actually believe it is convex if the weights are nonincreasing. That is, $w_i\geq w_j$ whenever $\sigma_i\geq\sigma_j$. Dec 26, 2014 at 15:40
• A simple case: let $w_n=1$ for $n>1$ and all other weights are zero. That is certainly nonconvex. Dec 26, 2014 at 15:43
• The singular values are ordered by definition. That's the key...
– Dirk
Dec 26, 2014 at 16:47
• 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. Dec 27, 2014 at 13:29
• 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. Dec 27, 2014 at 13:32