Computing sparse eigenvectors of psd matrices

Disclaimer. Sorry for answering my own question. Should've thought about it a bit more before posting on math.SE...

---

So, let $B$ be any real matrix with $m$ rows such that $A=B^TB$ (such a $B$ exists because $A$ is psd). The main problem can be rewritten as

$$ sqrt{max_{v in mathscr C_s}v^TAv} = max_{v in mathscr C_s}|Bv|_2 = max_{v in mathscr C_s}max_{|x|_2 le 1}x^TBv = max_{|x|_2 le 1}max_{v in mathscr C_s}v^T(B^Tx). tag{1} $$

We consider the following subproblem.

Sub-problem. Given $u in mathbb R^m$, find $v in mathscr C_s$ which maximizes $v^Tu$.

One can easily show that

Lemma. The above sub-problem is solved by taking $v = varphi_s(u):= T_s(u)/max(|T_s(u)|_2, 1)$, where $T_s(u) in mathbb R^m$ is a vector obtained from $u$ by zero-ing out the $m-s$ entries with the smallest absolute values.

The operator $T_s$ is sometimes referred to as hard-thresholding. Problem (1) can then be solved via the following simple iterative scheme

• x-update: $x_{k} leftarrow Bv_k/|Bv_k|_2$
• v-update: $v_{k+1} leftarrow varphi_s(B^Tx_k)$

which can further be simplified to just one-line program involving the original matrix $A$:

• $v_{k+1/2} leftarrow Av_k$, $v_{k+1} leftarrow varphi_s(v_{k+1/2}/(v_k^Tv_{k+1/2})^{1/2})$

Convergence. I've not yet worked this out, but adapting the proof of of convergence of the standard "power iteration" algorithm, it shouldn't be too hard to show that $lim_{k to infty}v_k in argmax_{v in mathscr C_s}v^TAv$.