Computing sparse eigenvectors of psd matrices

Question

Let $A$ be an $m \times m$ psd matrix (with $m$ large) and let $s \in \{0,1,\ldots,m\}$. Let $\mathscr C_s := \{v \in \mathbb R^m \mid \|v\|_2 = 1,\;\|v\|_0 \le s\}$ be the set of all $s$-sparse unit-vectors in $\mathbb R^m$.

Question. What is an efficient (and correct!) way to compute a vector $v \in \mathscr C_s$ which maximizes $v^TAv$ ?

The case $s = m$ corresponds to computing a leading eigenvetor of $A$ and can by accomplished via the power iteration.

Answer 1

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 \arg\max_{v \in \mathscr C_s}v^TAv$.