3
$\begingroup$

I found the following statement from a google search. If $S_k(\mathbf{X})$ is the sum of the $k$ largest eigenvalues of a symmetric $m\times m$ matrix $\mathbf{X}$, then,$$S_k(\mathbf{X}) \leq t$$ is true iff

$$ t - k s - \mathrm{trace}(\mathbf{Z}) \geq 0 \\ \mathbf{Z} \geq 0 \\ \mathbf{Z} - \mathbf{X} + s\mathbf{I}_m \geq 0$$, where $s$ hasn't been described. I tried with $s$ as a positive variable in CVX and it worked and I could calculate the $k$ largest eigenvalues of $\mathbf{X}$.

I seem to be going around in circles trying to prove this one. I would like to prove it on my own. Can anyone provide a starting direction or the first few lines of the proof.

Thank you.

$\endgroup$
  • $\begingroup$ In fact, this is exactly what CVX uses to implement this function in lambda_sum_largest. I'm glad I didn't have to prove it. :-) $s$ is just a free variable (i.e., no need to require it to be non-negative; in fact I am not convinced it will always work if you do). $\endgroup$ – Michael Grant Nov 29 '14 at 20:24
  • $\begingroup$ @MichaelGrant I was going through the code of the lambda_sum_largest function and found that it was using the eig command in MATLAB. Does CVX alter the way MATLAB uses the eig command? Is there any place where the implementation you have mentioned is visible? Thanks :) $\endgroup$ – Karthik Upadhya Nov 29 '14 at 20:50
  • $\begingroup$ It only uses eig for constant inputs. Look in the @cvx subdirectories for the CVX-specific implementations. $\endgroup$ – Michael Grant Nov 29 '14 at 20:57
  • 1
    $\begingroup$ can we think like this? Say $s=0$, then $Z\geq X$ implies $trace(Z)\geq trace(X)$ (can't see a way to prove it though!!). Then $t\geq trace(Z)\geq trace(X) \geq S_k(X)$. $\endgroup$ – dineshdileep Dec 1 '14 at 4:00
  • 1
    $\begingroup$ btw, I guess $X$ should be non-negative definite for the above argument to work, if it works at all!! $\endgroup$ – dineshdileep Dec 1 '14 at 4:39
8
$\begingroup$

We'll start with the following expression for $S_k(\mathbf{X})$ as a maximum sum over $k$ orthonormal vectors: $$\begin{gathered} \max_{\mathbf{v}_1\ldots\mathbf{v}_k} \sum_{i=1}^k \mathbf{v}_i^T \mathbf{X}\mathbf{v}_i\\ \mathbf{v}_i^T \mathbf{v}_j = \begin{cases} 1 & i = j \\ 0 & i \ne j\end{cases} \end{gathered}$$ If we collect the vectors in the $k \times m$ matrix $\mathbf{V}$, in matrix notation this is: $$\begin{gathered} \max_{\mathbf{V}} \text{ trace}(\mathbf{V}^T \mathbf{X} \mathbf{V})\\ \mathbf{V}^T \mathbf{V} = \mathbf{I}_k \end{gathered}$$ Since this is a nonconvex problem, we'll consider a convex relaxation. Note that $\mathbf{V}^T \mathbf{V} = \mathbf{I}_k$ only if $\mathbf{0} \preceq \mathbf{V} \mathbf{V}^T \preceq \mathbf{I}$ and $\text{trace}(\mathbf{V} \mathbf{V}^T)=k$. So letting $\mathbf{A}=\mathbf{V} \mathbf{V}^T$, we consider the following SDP which is a convex relaxation of the above: $$ \begin{gathered} \max_\mathbf{A} \ \text{trace}(\mathbf{A}\mathbf{X})\\ \mathbf{0} \preceq \mathbf{A} \preceq \mathbf{I} \\ \text{trace}(\mathbf{A}) = k \end{gathered} $$ Then we take the dual (and reformulate slightly) to get: $$ \begin{gathered} \min_{\mathbf{Z},s} \ \text{trace}(\mathbf{Z})+ks\\ \mathbf{Z} \succeq \mathbf{0}\\ \mathbf{Z} + s \mathbf{I} \succeq \mathbf{X} \end{gathered} $$ Now that we have the above SDP primal-dual pair, we can prove that their optimal value is $S_k(\mathbf{X})$ just by constructing optimal points. Suppose $\mathbf{X}=\mathbf{U}\text{ diag}(\lambda)\mathbf{U}^T$, where $\mathbf{U}$ is an orthonormal matrix of eigenvectors and $\mathbf{\lambda}$ is the vector of eigenvalues sorted in decreasing order, that is $\lambda_i\ge\lambda_{i+1}$. Then let $$ \begin{aligned} \mathbf{A}^*&=\mathbf{U}\text{ diag}(\mathbf{1}_k,\mathbf{0}_{m-k})\mathbf{U}^T\\ \mathbf{Z}^*&=\mathbf{U}\text{ diag}((\lambda-\lambda_k \mathbf{1})_+)\mathbf{U}^T\\ s^*&=\lambda_k \end{aligned} $$ Here, $(\cdot)_+$ is the positive part of a vector (it sets the negative components to zero). One can check that these points are feasible for their respective problems. Also we check the values of the objectives: $$ \begin{aligned} \text{trace}(\mathbf{A}^*\mathbf{X})&=\text{trace}(\mathbf{U}\text{ diag}(\lambda)\mathbf{U}^T\mathbf{U} \text{ diag}(\mathbf{1}_k,\mathbf{0}_{m-k})\mathbf{U}^T)\\ &=\text{trace}(\text{diag}(\lambda)\text{ diag}(\mathbf{1}_k,\mathbf{0}_{m-k}))\\ &=\sum_{i=1}^k \lambda_i\\ &=S_k(\mathbf{X})\\ \text{trace}(\mathbf{Z}^*)+ks^* &= k\lambda_k +\sum_{i=1}^m(\lambda_i-\lambda_k)_+\\ &= \sum_{i=1}^k((\lambda_i-\lambda_k)_+ + \lambda_k)\\ &=S_k(\mathbf{X}) \end{aligned} $$ Recall that all dual feasible points give a bound for the primal and vice-versa. Since these points give the same value of the objective for their respective problems, they must be optimal. Therefore $S_k(\mathbf{X})$ is the optimal value for both SDPs.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ +1, Then $\mathbf{A}$ will be the sum of $k$ rank-one positive semi-definite matrices, where each matrix is the outer product of unit-norm eigenvectors corresponding to the $k$ largest eigenvalues, Is that the idea? $\endgroup$ – dineshdileep Dec 1 '14 at 3:56
  • $\begingroup$ Yes, that's the idea. (Though to be a complete proof you also need to consider the case of nonunique eigenvalues, but it's a straightforward generalization.) $\endgroup$ – p.s. Dec 1 '14 at 4:30
  • $\begingroup$ Can you please take a look at the comment I have posted on the OP's question? does it help? $\endgroup$ – dineshdileep Dec 1 '14 at 4:47

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.