Singular Value Thresholding

Proximal of Nuclear Norm

Low-rank structure underpins many applications. But, direct rank minimization is hard. Nuclear norms offer us an efficient proxy.

What are rank and nuclear norm?

These are metrics used to measure a matrix.

🔹 rank = number of nonzero singular values
🔹 nuclear norm = sum of singular values

Rank is nonconvex, making it hard to use in optimization models. On the other hand, the nuclear norm is convex, and admits an elegant proximal formula. Thus, nuclear norms show up in many situations where low-rank structure is to be exploited.

As shared in prior posts, proximal and gradient descent operators power many modern optimization algorithms. So, this short lecture walks unpacks an explicit formula for the proximal formula of the nuclear norm.

Enjoy!