What is the intuition for the trace norm (nuclear norm)?

Question

I will word this question in terms of linear operators acting on $\mathbb{C}^n$ for simplicity. Feel free to provide an answer in terms of more general Hilbert spaces if you think it makes more sense that way.

The standard norm induced by the inner product on $\mathbb{C}^n$ is the Euclidean norm $ \sqrt{\langle x, x\rangle} = \| x \|_2 = \sqrt{\sum_i |x_i|^2}$. Similarly, endowed with the inner product $\langle A, B\rangle = \text{trace}(A^* B)$, the space of $n \times n$ complex matrices forms an inner product space with the induced Frobenius norm $ \|A\|_2 = \sqrt{\text{trace}(A^* A)}$.

However, there is a different norm that frequently comes up: it is the trace norm $\|A\|_1 = \text{trace}\left(\sqrt{A^* A}\right)$. There is a sense in which this norm is induced by the inner product on $\mathbb{C}^n$, since if $A = xx^*$, then $\|A\|_1 = \|x\|_2^2$.

However, what is the "meaning" of the trace norm? The Euclidean and Frobenius norms have an intuitive meaning in a geometric sense, as the length of a vector. Why do we care about the trace norm? Is it precisely because it is induced by the "natural" Euclidean norm on $\mathbb{C}^n$?

Additionally, if we express the trace norm in terms of the singular values of $A$, it corresponds to the L1 norm (i.e. sum of absolute values) of the singular values. Does the L1 norm on $\mathbb{C}^n$, i.e. $\|x\|_1 = \sum_i |x_i|$, have any interpretation, and does it share any similarity with the trace norm on $\mathbb{C}^{n\times n}$?

(I apologise if these questions are basic, I have asked this question on Math StackExchange and received no responses, and I could not find any information about the intuition for these norms and their interrelations.)

Answer 1

Another answer is that $M_n$, the space of $n\times n$ complex matrices, carries an operator norm where the norm of a matrix is its norm as a linear operator from $\mathbb{C}^n$ to itself (giving $\mathbb{C}^n$ euclidean norm). For some of us, this is the most natural and useful norm on $M_n$.

With operator norm, $M_n$ is a finite dimensional Banach space, so it has a dual space, which is just $M_n$ equipped with trace norm. In infinite dimensions the trace class operators on $H$, with trace norm, form the (unique) predual of $B(H)$.

Edit: I should add something about how this relates to the $\ell^1$ norm. The operator norm of a diagonal matrix is the $\ell^\infty$ norm of its entries, so operator norm can be seen as a sort of generalization of $\ell^\infty$ norm. Indeed, $M_n$ with operator norm contains an isometric copy of $\ell^\infty_n$ as the diagonal matrices. So it is natural that the dual norm should be the $\ell^1$ norm on the diagonal matrices.

Answer 2

One potential intuition for the trace norm is as a way of turning the rank of a matrix (which is very discontinuous) into a norm (which is continuous). Specifically, the trace norm is the unique norm with the property that $\|P\|_{\mathrm{tr}} = \mathrm{rank}(P)$ for every orthogonal projection $P \in M_n(\mathbb{C})$.

Closely-related to this is the following characterization of the trace norm, which basically says that $\|X\|_{\mathrm{tr}}$ measures the "amount of rank-1 matrices" needed to construct $X$: $$ \|X\|_{\mathrm{tr}} = \inf\big\{ \sum_j \|X_j\| : X = \sum_j X_j, \ \ \mathrm{rank}(X_j) = 1 \ \ \forall j \big\}. $$

Alternatively, just like the $\ell_1$-norm is typically the "right" norm to use when dealing with probability distributions (after all, we want probabilities to add up to $1$, not their squares to add up to $1$), the trace norm is typically the "right" norm to use when dealing with their non-commutative analog (density matrices/quantum states).

Answer 3

If you are interesting in geometrical intuition, here is the possible one:

Any matrix (operator) $A$ transforms a unit ball to an ellipsoid. Singular values of $A$ correspond to the lengths of ellipsoid's axis, which orientation is defined by singular vectors. So the nuclear norm represents the sum of the lengths of ellipsoid's axis.

You can also play with link between $l_1$ norm and sparsity. Having genetal approximation problem : $$ \beta^* = argmin_{\beta}\|E(\beta)\|_1 = argmin_{\beta}\|A-M(\beta)\|_1 $$ the error matrix $E(\beta^*)$ will probably have some singular values equal to 0, which is not the case with $l_2$ norm.

I don't know if all these facts can be useful for you, but at least it gives some intuition about this norm.

Answer 4

The trace-class norm of $A$ is about putting the $\ell^1$ norm on the singular values of $A$, whereas the Hilbert-Schmidt norm uses $\ell^2$ instead. So your question is basically: why should we care about $\ell^1$ and not only $\ell^2$? Things become only interesting in infinite dimensional spaces, where these norm are not equivalent anymore. This is why the trace-class norm usually arises when considering compact operators acting on infinite dimensional spaces. Books like "Trace ideals and their applications" by B. Simon will tell you more about these objects, depending on what you're looking for.