I have trouble proving the following inequality.
Let a matrix $A \in \mathbb{R}^{M \times N}$, and $\sigma_i(A)$ be the i-largest singular value of A. Define the operator norm and the trace norm as follow:
$$
\|A\|_2 := \sigma_1(A),\ \|A\|_{tr} = \sum_{i = 1}^{min\{M, N\}} \sigma_i(A)
$$
Could anyone provide me how to prove the below statement?
$$
\langle X,Y\rangle \le \|X\|_{tr}\,\|Y\|_2
$$
Note that $\langle X,Y\rangle $ is the matrix inner product.
Best Answer
This follows from the Singular Value Decomposition. We have $X=VDW$ with $V,W$ unitaries and $D$ "diagonal" (i.e. it is rectangular in general, but the singular values of $X$ lie in the entries with the same row and column number).
I will use the elementary facts that, for any matrix $A$, $|A_{kj}|\leq\|A\|_2$ for all $k,j$; and that the operator norm $\|\cdot\|_2$ is unitarily invariant. So $$ \langle X,Y\rangle=\text{Tr}(Y^TX)=\text{Tr}(Y^TVDW)=\text{Tr}(WY^TV\,D)=\text{Tr}((VYW)^T\,D)\\=\sum_{k=1}^M\sum_{j=1}^N(VYW)^T_{kj}D_{jk}=\sum_{k=1}^{\min{M,N}}(VYW)^T_{kk}\,\sigma_k(X)\leq\|VYW\|_2\,\sum_{k=1}^{\min{M,N}}\sigma_k(X)\\ =\|VYW\|_2\,\|X\|_{tr}=\|Y\|_2\,\|X\|_{\rm tr}. $$
Remark: We can get a tighter (and sharp) inequality if instead we use the estimate $|A_{kj}|\leq\|A\|$, where $\|\cdot\|$ is the operator norm. That way we get $$ |\langle X,Y\rangle|\leq \|Y\|\,\|X\|_{\rm tr}. $$