TransWikia.com

Computing sparse eigenvectors of psd matrices

Mathematics Asked on December 8, 2021

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.

One Answer

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$.

Answered by dohmatob on December 8, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP