5
$\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
    May 18 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 $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
    May 18 at 3:39
  • $\begingroup$ Does this also mean that $f(x) = \sum^{k}_{i} \lambda_{i}(g(x))$ is also convex $\endgroup$
    – Tigertron
    May 18 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$
    – B.Martin
    May 18 at 21:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.