5
$\begingroup$

A spectraplex (special case of spectrahedron) is the set of all positive semi-definite matrices whose trace is equal to one. Formally, let $$ S=\{\textbf{W} \in \mathbb{R}^{d \times d} \mid \textbf{W} \succeq 0, \text{Tr}(\textbf{W})=1\} $$

On page 7, lemma 2 in On the Regret Minimization of Nonconvex Online Gradient Ascent for Online PCA, the papers says "it is well known that the projection of $\textbf{W}$ onto $S$ is given by" $$ \Pi_S[\textbf{W}]=(\lambda_1(\textbf{W})-\lambda)w'w'^T+ \sum_{i=2}^{d}\max\{0,\lambda_i(\textbf{W})-\lambda \}y_iy_i^T $$

where $(w',y_2,y_3,\cdots,y_d)$ are eigenvectors of $\textbf{W}$ corresponding to descending eigenvalues such that

$$ \lambda_1(\textbf{W})-\lambda+ \sum_{i=2}^{d}\max\{0,\lambda_i(\textbf{W})-\lambda \}=1 $$ for some $\lambda \geq 0$.

Where the above comes from? Is there any reference that explains such projections?

$\endgroup$
  • $\begingroup$ I believe that you can reduce this problem to the problem of projecting onto the unit simplex in $R^{n}_{+}$ by using the orthogonality of the $y_{i}y_{i}^{T}$ with respect to the trace inner product. The equation for $\lambda$ is the same equation that appears in the commonly used algorithm for computing the projection on the unit simplex in $R^{n}_{+}$. $\endgroup$ – Brian Borchers Jan 5 at 16:15
3
$\begingroup$

First, note that no such $\lambda$ exists if

$\sum_{i=1}^{d} \lambda_{i} < 1$.

For example, the method fails if $W=0$ or if $W=(1/(2d))I$. It appears that in the context where this is presented in the paper that you cited we can be sure that the sum of the $\lambda_{i}$ is large enough.

I believe that if you allow for negative values of $\lambda$ the method will actually produce correct results for matrices $W$ that have $\sum_{i=1}^{d} \lambda_{i}<1$.

In the following, we'll assume that

$\sum_{i=1}^{d} \lambda_{i} \geq 1$.

Since $W$ is symmetric, we can write it in terms of eigenvalues and normalized eigenvectors as

$W=\sum_{i=1}^{d} \lambda_{i} y^{(i)}{y^{(i)}}^{T}$

or

$W=\sum_{i=1}^{d} \lambda_{i} Y^{(i)}$

where

$Y^{(i)}=y^{(i)}{y^{(i)}}^{T}$.

We need to be specific about the matrix inner product and norm that we're projecting with respect to. Since $W$ lives in the space of symmetric matrices, The appropriate inner product is

$\langle A, B \rangle = \mbox{tr}(AB)$

and the norm is

$\| A \|_{F}=\sqrt{\langle A, A \rangle}$.

Note that with respect to this inner product, the $Y^{(i)}$ matrices are orthogonal because the $y_{i}$ eigenvectors are orthogonal.

$\langle Y^{(i)}, Y^{(j)} \rangle=\mbox{tr}(y^{(i)}{y^{(i)}}^{T}y^{(j)}{y^{(j)}}^{T})$

$\langle Y^({i)}, Y^{(j)} \rangle=\mbox{tr}(y^{(i)}0{y^{(j)}}^{T})=0$.

Also,

$\| Y^{(i)} \|_{F}^{2}=\mbox{tr}(Y^{(i)}Y^{(i)})= \mbox{tr} (y^{(i)}{y^{(i)}}^{T} y^{(i)}{y^{(i)}}^{T}) =\mbox{tr}(y^{(i)}{y^{(i)}}^{T}) =\mbox{tr}({y^{(i)}}^{T}y^{(i)}) =1$.

The desired projection is

$\Pi_{S}(W)=\mbox{arg} \mbox{min}_{Y} \| W-Y \|_{F}^{2}$

subject to the constraints

$\mbox{tr}(Y)=1$

$Y \succeq 0$.

Write $Y$ as a linear combination of the $Y^{(i)}$ matrices plus an additional component that is in the orthogonal complement of the span of the $Y^{(i)}$.

$Y=Y^{(0)}+\sum_{i=1}^{d} \alpha_{i} Y^{(i)}$

Now, by the Pythagorean theorem,

$\| W-Y \|_{F}^{2}=\left\| W-Y^{(0)} \right\|_{F}^{2}+\left\| \left( W- \sum_{i=1}^{d} \alpha_{i} Y^{(i)} \right) \right\|_{F}^{2}$.

$\| W-Y \|_{F}^{2}=\left\| W-Y^{(0)} \right\|_{F}^{2}+\left\| \sum_{i=1}^{d} (\lambda_{i}-\alpha_{i}) Y^{(i)} \right\|_{F}^{2}$.

Using the orthogonality of the $Y^{(i)}$ matrices, we get that

$\| W-Y \|_{F}^{2}=\left\| W-Y^{(0)} \right\|_{F}^{2}+\sum_{i=1}^{d} (\lambda_{i}-\alpha_{i})^{2}$.

Since $W \perp Y^{(0)}$,

$\| W-Y \|_{F}^{2}=\left\| W \right\|_{F}^{2}+\left\| Y^{(0)} \right\|_{F}^{2}+\sum_{i=1}^{d} (\lambda_{i}-\alpha_{i})^{2}$.

Since

$\mbox{tr}(Y)=\mbox{tr}(Y^{(0)})+\sum_{i=1}^{d} \alpha_{i}$,

and

$\sum_{i=1}^{d} \alpha_{i} \leq \sum_{i=1}^{d} \lambda_{i}$,

using a non-zero value of $Y^{(0)}$ can only increase this objective. Thus it's optimal to set $Y^{(0)}=0$.

We've now reduced the problem to

$\min \sum_{i=1}^{d} (\lambda_{i}-\alpha_{i})^{2}$

subject to

$\sum_{i=1}^{d} \alpha_{i}=1$

$\alpha \geq 0$.

It's easy to see that the equation given in the paper results from applying the KKT conditions to this problem.

If we let $\mu$ be the Lagrange multiplier for the constraint $\sum_{i=1}^{d}\alpha_{i}=1$ and $\nu_{i}$ be the Lagrange multiplier for the constraint $\alpha_{i} \geq 0$, then the ith component of the KKT conditions depends on whether $\alpha_{i}>0$, in which case $\nu_{i}=0$, or $\alpha_{i}=0$, in which case $\nu_{i}$ is free to be nonzero.

In the case $\alpha_{i}>0$ and $\nu_{i}=0$, we have

$-2(\lambda_{i}-\alpha_{i})=\mu$

or

$(\lambda_{i}-\alpha_{i})=\mu/2$.

In the case where $\alpha_{i}=0$ and $\nu_{i}$ is positive, the equation can satisfied by adjusting $\nu$. Next, we use the constraint

$\sum_{\alpha_{i}>0} \alpha_{i}=1$

to get

$\sum_{\alpha_{i}>0} (\lambda_{i}-\mu/2)=1$

Adding in the terms for $\alpha_{i}=0$, we get

$\sum_{i=1}^{d} \max(0,\lambda_{i}-\mu/2)=1$.

Once $\mu$ has been determined, let

$\alpha_{i}=\max(0,\lambda_{i}-\mu/2)$ for $i=1, 2, \ldots, d$.

$\endgroup$
  • $\begingroup$ Wow, it is a very rigorous proof. $\endgroup$ – Sepide Jan 7 at 19:01

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.