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.
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
which can further be simplified to just one-line program involving the original matrix $A$:
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
Get help from others!
Recent Questions
Recent Answers
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP