In my case, $X_{\boldsymbol{\delta}}\in\mathbb{R}^{d\times M}$ is a function of Rademacher variables $\boldsymbol{\delta}\in\{1,-1\}^M$ with $\delta_i$ independent uniform random variables taking values in $\{−1, +1\}$. $X_{\boldsymbol{\delta}}=[\sum_{i=1}^{I_1}\delta_{i}\mathbf{x}_{i},\sum_{i=I_1+1}^{I_2}\delta_{i}\mathbf{x}_{i},...,\sum_{i=I_{M-1}+1}^{I_M}\delta_i\mathbf{x}_{i}]$ is a group-wise sum with known $I_1,I_2,...,I_M$ and non-singular $X=(\mathbf{x}_1,\mathbf{x}_2,...,\mathbf{x}_N)\in\mathbb{R}^{d\times N}$ where $N>M\gg d$.

Given that $\sigma_i(X_{\boldsymbol{\delta}})$ denotes $i$-th smallest singular value, how can I find the lower bound of the expectation $\underset{\boldsymbol{\delta}}E\left[\sum_{i=1}^{k} \sigma_{i}^{2}\left(X_{\boldsymbol{\delta}}\right)\right]$ assuming $k<d$?

Note: I can find an upper bound by Jensen’s inequality and concavity of sum of $k$ smallest eigenvalue, but I am curious about whether it is possible to get a lower bound.

I have also posted the question here.



Your Answer

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