tracenorm

The trace norm, also known as the nuclear norm or Schatten 1-norm, is a matrix norm defined as the sum of the singular values of a matrix. It is widely used in fields such as machine learning, signal processing, and convex optimization, particularly in problems involving low-rank matrix recovery and regularization.

Formally, for a real or complex matrix \(A\), with singular values \(\sigma_1, \sigma_2, ..., \sigma_r\), the trace norm is given by

\[

\|A\|_* = \sum_{i=1}^{r} \sigma_i,

\]

where \(r\) is the rank of \(A\). The singular values \(\sigma_i\) are obtained from the singular value decomposition (SVD) of \(A\), which expresses \(A\) as \(A = U \Sigma V^*\), with \(\Sigma\) being a diagonal matrix containing the singular values.

The trace norm is a convex function, making it useful as a regularizer for promoting low-rank solutions in various optimization problems. It is considered the convex envelope of the rank function on the unit ball of matrices with spectral norm less than or equal to one.

In comparison to other matrix norms, such as the Frobenius norm or spectral norm, the trace norm emphasizes low-rank structure by penalizing the sum of singular values. It plays a central role in convex relaxations of rank minimization problems, allowing for efficient algorithms to approximate solutions that are otherwise computationally intractable.

Overall, the trace norm serves as a fundamental tool in low-rank matrix approximation and convex optimization, aiding in tasks like matrix completion, robust principal component analysis, and collaborative filtering.