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?

Question

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$.

Answer 1

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. Next, equation (4.6) from Tropp's paper on User-friendly tail bounds 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.

Answer 2

Disclaimer. Here, I establish a somewhat trivial (and perhaps bad ?) lower-bound for $\alpha_k(A)$.

---

Note that $\alpha_k(A)$ is a nondecreasing function of $A$ (w.r.t the order: $X \ge Y \iff X - Y$ is psd). If $a$ is a principal unit eigenvector of $a$, then

$\alpha_k(A) \ge \lambda_\max(A)\alpha_k (aa^\top) = \lambda_\max(A)\cdot \mathbb E_V\|P_Va\|^2 = (k/n)\lambda_\max(A)$.

Likewise, since $\alpha_k(A)$ is a nondecreasing function of $k$, we have $$ \alpha_k(A) \ge \alpha_1(A) = \mathbb E_{v \sim N(0,I_d)}[v^\top A v/\|v\|^2] = \mbox{trace}(A)/n. $$

We conclude that

$\alpha_k(A) \ge \max(\mbox{trace}(A)/n,(k/n)\lambda_\max(A))$, with equality if $A$ is rank-1 or $k=1$.

I don't know if this lower-bound can be improved much for general $A$.

Answer 3

Short story: if $\log n \ll k < c n$ for some constant $c<1$ then $$ \|P_V A P_V\|_\mathrm{op} \asymp \operatorname{trace}[A]/n + \|A\|_\mathrm{op}k/n $$ up to multiplicative constants dependent on $c$.

---

By rotational invariance, assume without loss of generality that $A=\operatorname{diag}(a_1,\ldots,a_n)$ with $a_1\ge a_2 \ge \ldots \ge a_n$. The object of study is the operator norm $\|P_V A P_V\|_\mathrm{op}$ where $P_V$ is an orthogonal projector on the Grassmannian. Equivalently, the goal is to study $\|\sqrt{A} P_V\|_\mathrm{op}$.

It is easier to work with Gaussian matrices as more random matrix theory results are available. Realize $P_V$ as $X(X^TX)^{-1}X^T$ where $X\in R^{n\times k}$ has iid $N(0,1/n)$ entries.

I will focus on the situation $k\le c n$ for constant $c<1$. Then $(X^TX)^{-1}X^T$ has bounded singular values with overwhelming probability in the sense $(c_*\le \text{singular values} \le c^*$ for constants $c_*,c^*$ depending on $c$ only), see for instance Theorem II.13 in Davidson and Szarek (2000), although that reference has a missing $\sqrt n$ in the statement of the theorem. This means that up to multiplicative constants depending on $c$, we may as well characterize $\|\sqrt AX\|_\mathrm{op}$. This does not lose much for the approach below, which characterizes $\|\sqrt AX\|_\mathrm{op}$ up to multiplicative constants anyway.

The expected operator norm of inhomogeneous Gaussian matrices with independent entries has been fully characterized in [1]. In the symmetric case [1, Theorem 1.1], if $b_{ij}\ge 0$ and the matrix has entries $M_{ij} = b_{ij} g_{ij}$ for $g_{ij} \sim N(0,1)$ then $$E\|M\|_\mathrm{op}\asymp\max_i \sqrt{\sum_j b_{ij}^2} + \max_{ij} b_{ij}^*\sqrt{\log i}$$ up to multiplicative universal constants independent of the dimensions and the $\{b_{ij}\}$; above $b_{ij}^*$ are the entries of the matrix $(b_{ij})$ obtained by reordering the rows/columns such that $\max_i b_{1i}^* \ge \max_i b_{2i}^* \ge ...$.

In our case, $\sqrt A X$ has independent normal entries but is not symmetric, so we look instead at $$ \begin{pmatrix} 0 & \sqrt{A}X \\ X^T \sqrt{A} & 0 \end{pmatrix} $$ which is symmetric and has the same operator norm as $\sqrt{A} X$ up to multiplicative constants (this symmetrization device is explained in the later sections of [1]). Then $$\max_i \sqrt{\sum_j b_{ij}^2} \asymp \sqrt{\operatorname{trace}[A]/n} + \sqrt{\|A\|_\mathrm{op} k/n}, $$ and the term $\max_{ij} b_{ij}^* \sqrt{\log i}$ is dominated by $\sqrt{\|A\|_\mathrm{op} k/n}$ if $k\gg\log n$.

Conclusion: $\|P_V A P_V\|_\mathrm{op}$ is of order $\operatorname{trace}[A]/n + \|A\|_\mathrm{op} k/n$ up to multiplicative constants depending on the constant $c<1$ whenever $\log n \ll k \le c n$. I left under the rug the issue of concentration of $\|\sqrt{A} X\|_\mathrm{op}$ around its expectation which should be easy to obtain using the standard concentration of Lipschitz functions of independent normals (see for instance Theorem 5.6 in the book by Boucheron, Lugosi and Massart).

[1]: The dimension-free structure of nonhomogeneous random matrices (with Rafał Latała and Pierre Youssef) Invent. Math. 214, 1031-1080 (2018).

Answer 4

As explained in the other answers, it is enough to study $\|\sqrt AX\|_{op}$ if $k<c n$ where $X$ has iid $N(0,1/n)$ entries.

I am adding an extra answer regarding the upper bounds, that is mostly self-contained using only elementary $\epsilon$-net and concentration arguments. It also explains how to get the exact constant 1 for the term $\sqrt{trace[A]/n}$ for $\|\sqrt AX\|_{op}$.

By a classical exercise on $\epsilon$-net, e.g., Exercise 4.4 in the HDP book by Vershynin, if $N$ is an $\epsilon$-net of the sphere $S^{k-1}$ then $$ \sup_{x\in S^{k-1}} | \|Mx\| - \mu| \le \frac{C}{1-2\epsilon} \sup_{x\in N} | \|Mx\| - \mu|. $$ and there exists a net $N$ of size $|N|\le 9^k$ for $\epsilon = 1/4$ (Corollary 4.2.13 in the HDP book by Vershynin). Now let $\mu= \sqrt{trace[A]/n}$ and $M=\sqrt{A}X$ in the previous display; for a fixed $x$ in the sphere we have $|\|Mx\| - \sqrt{trace[A]/n}| \le \|\sqrt A / \sqrt n\|_{op} t$ with probability $1-2e^{-t^2}$ for all $t$ by the concentration inequality in Theorem 6.3.2 again in the HDP book. The union bound over $N$ completes the proof.