We have $X=[\mathbf{x}_1,\mathbf{x}_2...,\mathbf{x}_n]\in\mathbb{R}^{d\times n}$, $H=[\mathbf{h}_1,\mathbf{h}_2...,\mathbf{h}_n] \in\mathbb{R}^{d\times n}$, and $d<n$. $H$ has rank $r\leq d$ and $X$ has rank $d$.

Assume we have $\|H\|_F\leq C$ and $\|\mathbf{x}_i\|_2\leq R$, where $\|\cdot\|_F$ and $\|\cdot\|_2$ are the Frobenius norm and vectro 2-norm respectively.

What do we know about the upper bound of Frobenius inner product $\left<H,X\right>_F$ of $H$ and $X$?

Hint: I know by Cauchy-Schwarz inequality $\left<H,X\right>_F < \sqrt nCR$. The equality will not hold because we can not guarantee $\mathbf{x}_i = k\mathbf{h}_i, \forall i$. This is because $H$ is rank deficient. I think there is a tighter upper bound for $<H,X>_F$ in terms of singular values of $X$ and rank $r$ of $H$.

I have also posted the question here.


1 Answer 1


You can try the von Neuman trace inequality $$ \langle H,X\rangle\equiv\mathrm{trace}(H^{T}X)\le\sum_{i=1}^{d}\sigma_{i}(H)\sigma_{i}(X)\equiv\langle\sigma(H),\sigma(X)\rangle $$ where $\sigma_{i}(H)$ is the $i$-th largest singular value of $H$ and $\sigma(H)$ is the length-$d$ vector of singular values in decreasing order. From here, you can apply the Hölder inequality $$ \langle\sigma(H),\sigma(X)\rangle\le\|\sigma(H)\|_{1}\|\sigma(X)\|_{\infty}\equiv\sigma_{\max}(X)\;\sum_{i=1}^{d}\sigma_{i}(H). $$ If $H$ is rank-deficient, then we expect the Nuclear norm $\sum_{i=1}^{d}\sigma_{i}(H)$ to be small, and the bound to be relatively tight.

Note that the von Neuman inequality is one of the identities on the wiki page for trace inequalities. Also note that the nuclear norm is closely related to low-rank matrices. One can show that the nuclear norm is the convex envelope for the rank function over the Frobenius ball. See Recht, Fazel, Parrilo (2010).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.