Trace Norm

A Trace Norm is a p-norm which is defined as the sum of all singular values of a matrix.

• AKA: Nuclear Norm, Trace-Class Norm.
• Context:
  • It can be defined as [math]\displaystyle{ \|A\|_{*} = \sum_{i=1}^{\min\{m,\,n\}} X_i }[/math], where [math]\displaystyle{ A }[/math] is [math]\displaystyle{ m \times n }[/math] matrix, and [math]\displaystyle{ X_i }[/math] are the matrix singular values
• Example(s):
  • A Schatten Norm with p=1
• Counter-Example(s):
  • L1-Norm.
  • Frobenius Norm.
  • Euclidean Norm.
  • Vector Norm.
• See: L1 Norm, Mathematical Norm, Matrix Trace, Matrix Norm.

---

---

References

2015

• (Wikipedia, 2015) ⇒ http://wikipedia.org/wiki/Matrix_norm#Schatten_norms
  • QUOTE: The Schatten p-norms arise when applying the p-norm to the vector of singular values of a matrix. If the singular values are denoted by σ_i, then the Schatten p-norm is defined by

[math]\displaystyle{ \|A\|_p = \left( \sum_{i=1}^{\min\{m,\,n\}} \sigma_i^p \right)^{1/p}. \, }[/math]

These norms again share the notation with the induced and entrywise p-norms, but they are different.

All Schatten norms are sub-multiplicative. They are also unitarily invariant, which means that ||A|| = ||UAV|| for all matrices A and all unitary matrices U and V.

The most familiar cases are p = 1, 2, ∞. The case p = 2 yields the Frobenius norm, introduced before. The case p = ∞ yields the spectral norm, which is the matrix norm induced by the vector 2-norm (see above). Finally, p = 1 yields the nuclear norm (also known as the trace norm, or the Ky Fan 'n'-norm), defined as

[math]\displaystyle{ \|A\|_{*} = \operatorname{trace} \left(\sqrt{A^*A}\right) = \sum_{i=1}^{\min\{m,\,n\}} \sigma_i. }[/math]

(Here [math]\displaystyle{ \sqrt{A^*A} }[/math] denotes a positive semidefinite matrix [math]\displaystyle{ B }[/math] such that [math]\displaystyle{ BB=A^*A }[/math]. More precisely, since [math]\displaystyle{ A^*A }[/math] is a positive semidefinite matrix, its square root is well-defined.)

2013

• (Sun et al., 2013) ⇒ Qian Sun, Shuo Xiang, and Jieping Ye. (2013). “Robust Principal Component Analysis via Capped Norms.” In: Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ISBN:978-1-4503-2174-7 doi:10.1145/2487575.2487604
  • QUOTE: (...)In particular, the authors approximate the original problem by minimizing the sum of trace norm of [math]\displaystyle{ X }[/math] and ℓ1-norm of [math]\displaystyle{ Y }[/math] with an equality constraint: :[math]\displaystyle{ \textrm{minimize}\;X,Y\qquad∥X∥_∗ + λ∥Y ∥_1 }[/math] :[math]\displaystyle{ \textrm{subject to} A = X + Y }[/math] where the trace norm [math]\displaystyle{ ∥X∥_∗ }[/math] is defined as the sum of all singular values of [math]\displaystyle{ X }[/math], and [math]\displaystyle{ ∥Y∥_1 = \sum_{ij} |Y_{ij}| }[/math] denotes the sum of absolute values of all entries in [math]\displaystyle{ Y }[/math] .

• http://en.wikipedia.org/wiki/Singular_value
  • … For example, the Ky Fan-k-norm is the sum of first k singular values, the trace norm is the sum of all singular values, and the Schatten norm is the pth root of the sum of the pth powers of the singular values. Note that each norm is defined only on a special class of operators, hence s-numbers are useful in classifying different operators.

---