The relation is the following:
Let $\Vert A \Vert$ be the Ky-Fan $N$ norm of $A$. Then,
$\Vert A \Vert = trace((A^*A)^{\frac{1}{2}})$
btw, The Ky-Fan $N$ norm is equal to the Schatten norm with $p=1$. The Schatten norm is defined as the regular $l_p$ norm of the singular values:
$\Vert A \Vert_p=(\sum_{i=1}^N \sigma_i^p)^{\frac{1}{p}}$
And it is related to the trace by:
$\Vert A \Vert_p = trace((A^*A)^{\frac{p}{2}})$
If you are looking for a good reference about advanced material like that, I would highly recommend "Matrix Analysis" by R. Bhatia
Suppose that $A$ is a real $n \times n$ matrix.
Then the $2$-norm or the spectral norm of $A$ is defined as
$$
\Vert A \Vert_2 = + \sqrt{\lambda_{\max}(A^T A)} \tag{1}
$$
where $\lambda_{\max}(A^T A)$ denotes the largest eigenvalue of the non-negative definite matrix $A^T A$ which has real and non-negative eigenvalues.
It is easy to show that
$$
\Vert A \Vert_2 = \sup_{\Vert x \Vert_2 = 1} \ \Vert A x \Vert_2 \tag{2}
$$
so that $\Vert A \Vert_2$ is a subordinate matrix norm.
Proof 1 for Triangle Inequality for $2$-norm:
The triangle inequality for the $2$-norm of matrices can be easily established using (2).
Suppose that $A$ and $B$ are real $n \times n$ matrices.
Then for any vector $x$ satisfying $\Vert x \Vert_2 = 1$, we have
$$
\Vert (A + B) x \Vert_2 = \Vert A x + B x \Vert_2 \leq \Vert A x \Vert_2 + \Vert B x \Vert_2 \tag{3}
$$
From (3), it is immediate that
$$
\sup_{\Vert x \Vert_2 = 1} \ \Vert (A + B) x \Vert_2 \leq
\sup_{\Vert x \Vert_2 = 1} \Vert A x \Vert_2 + \sup_{\Vert x \Vert_2 = 1}
\Vert B x \Vert_2 \tag{4}
$$
which shows that
$$
\Vert A + B \Vert_2 \leq \Vert A \Vert_2 + \Vert B \Vert_2
$$
Proof 2 for Triangle Inequality for $2$-norm:
We can rewrite (1) using the SVD of $A$ as
$$
\Vert A \Vert_2 = \sigma_{\max}(A) \tag{5}
$$
where $\sigma_{\max}(A)$ denotes the largest singular value of $A$.
An important identity for the singular values of $A$, $B$, $A+B$ is established in Theorem 3.3.16 (Horn and Johnson, Matrix Analysis):
$$
\sigma_{\max}(A + B) \leq \sigma_{\max}(A) + \sigma_{\max}(B) \tag{6}
$$
From (6), it is immediate that
$$
\Vert A + B \Vert_2 \leq \Vert A \Vert_2 + \Vert B \Vert_2
$$
which is the triangle inequality for square matrices in $2$-norm.
(The proof given in Horn & Johnson's book also makes uses of the property (2) for the $2$-norm of matrices.)
Best Answer
For any $k$-plane $U$ in $\mathbb{C}^n$, let $i_U$ be the inclusion of $U$ into $\mathbb{C}^n$ and let $p_U$ be the orthogonal projection of $\mathbb{C}^n$ onto $U$.
Lemma: Let the singular values of $A$ be $\sigma_1 \geq \sigma_2 \geq \cdots \geq \sigma_n$. Then $\max_{U, V} \ \mathrm{Tr} \left( p_V \circ A \circ i_U \right)= \sigma_1+ \cdots +\sigma_k$, where the max is over all pairs of $k$-planes in $\mathbb{C}^n$.
Proof is left for the reader, using his or her favorite definition of singular values.
Then $\max_{U, V} \ \mathrm{Tr} \left(p_V \circ (A+B) \circ i_U\right) \leq \max_{U, V} \ \mathrm{Tr} \left( p_V \circ A \circ i_U \right) + \max_{U, V} \ \mathrm{Tr} \left( p_V \circ B \circ i_U \right)$.