Let $G\_{k,n}$ be the grassmannian of $k$-dimensional vector spaces of $\mathbb R^n$. By the Courant–Fisher characterization, the $k$th largest eigenvalue of an $n \times n$ psd matrix $A$ is given by


$$
\tag{1}\label{1}
\lambda\_k = \min\_{V \in G\_{n-k+1,n}} R(A,V),
$$
where $R(A,V):= \max\_{x \in V,\,\lVert x\rVert = 1} x^\top A x$.


Now, let $V$ be drawn according to the Haar distribution on $G\_{k,n}$, and replace the min in \eqref{1} by expectation over $V$.



> 
> **Question.** What does $\alpha\_k(A) := \mathbb E\_V [R(A,V)]$ correspond / evaluate to?
> 
> 
> 


**Note.** I'm really only interested in (good) lower-bounds.


Examples
--------


Let $P\_V$ be the orthogonal projector for $V$.


* If $k=1$, then $R(A,V) = v^\top A v$, where $v$ is uniform on the unit-sphere in $\mathbb R^n$, and so $\alpha\_1(A) = \operatorname{trace}(A)/n$.
* If $k=n$, then $P\_V = I\_n$ with probability $1$ and so $\alpha\_n(A) = \lambda\_\text{max}(A)$.
* If $A = I\_n$, then obviously $\alpha\_k(A) = 1$ for all $k \in [n]$.
* If $A = uu^\top$, a rank 1 matrix, then $\alpha\_k(A) = \mathbb E\_V R(A,V) = \mathbb E\_V\lVert P\_V u\rVert^2 = (k/n)\lVert u\rVert^2$.



What does $\mathbb E_V \max_{x \in V,\,\|x\|=1} x^T Ax$ evaluate to when $V$ is random $k$-dim suspace of $\mathbb R^n$ and $A$ is fixed psd matrix?
In another answer, @dohmatob establishes the lower bound
$$
\alpha\_k(A)\geq\frac{1}{n}\max\Big\{\operatorname{tr}(A),k\lambda\_{\max}(A) \Big\}.
$$
In what follows, we show that this bound is near-optimal for general $A$ in the regime where $k$ is at most a fraction of $n$.


Let $\Lambda$ denote the diagonal matrix of eigenvalues of $A$, and let $G$ denote an $n\times k$ matrix with iid $N(0,1)$ entries. Submultiplicativity gives
\begin{align\*}
\alpha\_k(A)
&=\alpha\_k(\Lambda)
=\mathbb{E}\|(G^\top G)^{-1/2}G^\top\Lambda G(G^\top G)^{-1/2}\|\_{2\to2}\\
&\leq\mathbb{E}\Big[\|(G^\top G)^{-1/2}\|\_{2\to2}\cdot\|G^\top\Lambda G\|\_{2\to2}\cdot\|(G^\top G)^{-1/2}\|\_{2\to2}\Big]
=\mathbb{E}\bigg[\frac{\|\Lambda^{1/2}G\|\_{2\to2}^2}{\sigma\_{\min}(G)^2}\bigg].
\end{align\*}
It is known that $\sigma\_{\min}(G)\sim\sqrt{n}-\sqrt{k}$ when $n$ and $k$ grow proportionately, and there are nonasymptotic results of this flavor, too; see [Vershynin's survey](https://arxiv.org/abs/1011.3027). Next, equation (4.6) from Tropp's paper on [User-friendly tail bounds](https://arxiv.org/abs/1004.4389) implies that (with $B := \lambda^{1/2} \otimes 1\_n$, where $\lambda \in \mathbb R^n$ is the vector of eigenvalues of $A$)
$$
\begin{split}
\|\Lambda^{1/2}G\|\_{2\to2}^2 = \|B \circ G\|\_{2 \to 2}^2
&\leq 2\log(\tfrac{n+k}{\epsilon})\cdot\max(\|\lambda^{1/2}\|^2\_2,k\|\lambda^{1/2}\|\_\infty^2)\\
&= 2\log(\tfrac{n+k}{\epsilon})\cdot\max(\operatorname{trace}(A),k\lambda\_\max(A))
\end{split}
$$
with probability $\geq1-\epsilon$. One may combine these estimates to show that @dohmatob's lower bound is tight up to log factors.


