lilmoore11p8

2022-07-04

Upper bound for smallest eigenvalue of matrix $‖\varphi \left(x\right){‖}_{2}\le 1$
I am reading a paper which claims the following. But I am not sure how to show it rigorously. Any help is appreciated.
For all $x\in \mathcal{X}$, assume the d-dimensional feature map is bounded such that $‖\varphi \left(x\right){‖}_{2}\le 1$. For any data distribution $\mu$ consider the matrix
$A={\mathbb{E}}_{x\sim \mu }\left[\varphi \left(x\right)\varphi \left(x{\right)}^{\mathrm{\top }}\right]$
Prove that the largest possible minimum eigenvalue ${\sigma }_{\text{min}}$ min of matrix A satisfies
${\sigma }_{\text{min}}\left(A\right)\le \frac{1}{d}$

eurgylchnj

Expert

Since A is a $d×d$ positive semidefinite matrix, its eigenvalues are nonnegative and they coincide with the singular values of A. Therefore
$\begin{array}{rl}{\sigma }_{min}\left(A\right)={\lambda }_{min}\left(A\right)& \le \frac{1}{d}\sum _{i=1}^{d}{\lambda }_{i}\left(A\right)=\frac{1}{d}\mathrm{tr}\left(A\right)\\ & =\frac{1}{d}\mathrm{tr}\left(\mathbb{E}\left(\varphi {\varphi }^{\mathrm{\top }}\right)\right)=\frac{1}{d}\mathbb{E}\left(\mathrm{tr}\left(\varphi {\varphi }^{\mathrm{\top }}\right)\right)\\ & =\frac{1}{d}\mathbb{E}\left(‖\varphi {‖}_{2}^{2}\right)\le \frac{1}{d}\mathbb{E}\left(1\right)=\frac{1}{d}.\end{array}$

Do you have a similar question?