Nuclear Norm

• categories: Linear algebra, Norm

Definition

The nuclear norm of a matrix $A\in {\mathbb{R}}^{m\times n}$ (also called the trace norm) is the sum of its singular values:

$$\Vert A{\Vert }_{\ast }=\sum _{i=1}^r{\sigma }_i,$$

where:

• ${\sigma }_i$ are the singular values of $A$ from the Singular Value Decomposition (SVD), $A=U\Sigma V^T$,
• $r=\min (m,n)$.

The nuclear norm can be viewed as the matrix equivalent of the ${\ell }_1$ norm for vectors, promoting low-rank approximations and sparsity in singular values.

Key Properties

1. Non-Negativity:
   $\Vert A{\Vert }_{\ast }\ge 0$, with equality if and only if $A=0$.

2. Relation to Frobenius Norm:
   The nuclear norm is always less than or equal to the Frobenius norm:

   $$\Vert A{\Vert }_{\ast }\le \Vert A{\Vert }_F.$$

3. Dual Norm:
   The nuclear norm is the dual norm of the Spectral Norm :

   $$\Vert A{\Vert }_{\ast }=\underset{\Vert B{\Vert }_2\le 1}{\sup }|\text{tr}(A^{T}B)|,$$

   where $\Vert B{\Vert }_2$ is the spectral norm.

4. Unitary Invariance:
   The nuclear norm is invariant under orthogonal (or unitary) transformations:

   $$\Vert A{\Vert }_{\ast }=\Vert UA{V}^T{\Vert }_{\ast },$$

   for any orthogonal/unitary matrices $U$ and $V$.

5. Convexity:
   The nuclear norm is a Convex Function, making it useful for optimization problems.

---

Applications

1. Low-Rank Matrix Approximation:
   Minimizing the nuclear norm promotes low-rank solutions in problems like collaborative filtering and data compression.

2. Compressed Sensing:
   Nuclear norm minimization is used for matrix completion problems, such as recovering missing entries in a matrix.

3. Robust PCA:
   Separates a low-rank matrix from sparse noise in data analysis.

4. Control Systems:
   Appears in optimal control problems for minimizing system ranks.

---

Examples

Example 1: Full Rank Matrix

Let:

$$A=\left[\begin{array}{cc}3& 0\\ 0& 4\end{array}\right].$$

The singular values of $A$ are ${\sigma }_1=4$, ${\sigma }_2=3$.
The nuclear norm:

$$\Vert A{\Vert }_{\ast }={\sigma }_1+{\sigma }_2=4+3=7.$$

Example 2: Low-Rank Matrix

Let:

$$A=\left[\begin{array}{cc}1& 1\\ 1& 1\end{array}\right].$$

The SVD of $A$ gives singular values ${\sigma }_1=2,{\sigma }_2=0$ (rank 1).
The nuclear norm:

$$\Vert A{\Vert }_{\ast }={\sigma }_1+{\sigma }_2=2+0=2.$$

Example 3: Relation to Frobenius Norm

Let:

$$A=\left[\begin{array}{cc}3& 0\\ 0& 4\end{array}\right].$$

Frobenius norm:

$$\Vert A{\Vert }_F=\sqrt{3^2+4^2}=5.$$

Nuclear norm:

$$\Vert A{\Vert }_{\ast }={\sigma }_1+{\sigma }_2=7.$$

In this case, $\Vert A{\Vert }_F>\Vert A{\Vert }_{\ast }$, consistent with the properties.