4
$\begingroup$

I saw a post https://mathoverflow.net/questions/98367/a-sum-of-eigenvalues that said

It is well-known that $\sum^{r}_{i = 1} \lambda_{i}(X)$ is convex.

and I saw an explanation in Boyd and Vandenberghe - "Convex Optimization", question 3.26(a) that said

$$\sum^{k}_{i = 1} \lambda_{i}(X) = \sup\{\operatorname{tr}(V^{T}XV) \mid V^{T}V = I\}.$$

The variational characterization shows that $f$ is the pointwise supremum of a family of linear functions $\operatorname{tr}(V^{T}XV )$

is an explanation for why it is convex.

But I don't really understand how the sup is the sum of the first $k$ eigenvalues and how that makes it convex.

$\endgroup$
1
  • 1
    $\begingroup$ What is, perhaps, missing is that $V$ is a $n\times k$ matrix. $\endgroup$
    – lcv
    Commented May 18, 2022 at 5:35

1 Answer 1

4
$\begingroup$

The supremum of any family of convex functions is convex. (proof)

Every linear function is convex.

Hence the supremum of a family of linear functions is convex.

Edit: To prove the supremum identity first note that for $V \in \mathbb R^{n \times k}$ with $V^TV=I$ \begin{align} \textrm{tr}(V^TXV) &= \textrm{tr}(XVV^T)\\ &\le \lambda(X)^T \lambda(V V^T) \end{align} Now since $(VV^T)^2 = VV^T$ the only eigenvalues are $0$ and $1$. Also note that $$\textrm{tr}(VV^T) = \textrm{tr}(V^TV) = k$$ Hence $VV^T$ has $k$ eigenvalues that are 1 and the rest are zero. Combining this with the previous inequality yields, and noting that any sum of $k$ eigenvalues is less than the sum of the $k$ largest eigenvalues yields $$\textrm{tr}(V^TXV) \le \sum_{i=1}^k \lambda_i(X)$$.

Taking $$V = [v_1, \ldots v_k]$$ where $v_j$ is the normalised eigenvector corresponding to $\lambda_j(X)$ achieves the supremum.

$\endgroup$
3
  • $\begingroup$ Yes, I understand that the sup of any family of convex functions is convex, I just don't understand by the sup is the first k eigenvalues $\endgroup$
    – Tigertron
    Commented May 18, 2022 at 3:39
  • $\begingroup$ Does this also mean that $f(x) = \sum^{k}_{i} \lambda_{i}(g(x))$ is also convex $\endgroup$
    – Tigertron
    Commented May 18, 2022 at 14:35
  • $\begingroup$ No, take $g(x) = -x^2$ and $n=1$. The sup identity still holds but the family of functions need not be convex. $\endgroup$
    – Ben Martin
    Commented May 18, 2022 at 21:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .