2
$\begingroup$

Suppose we have access to samples of $x$ distributed according to unknown multivariate Gaussian in $\mathbb{R}^d$. Estimate the following quantity: $$\max_{\|u\|=1} \frac{ E\left[\langle u\cdot x\rangle ^4\right]}{E\left[\langle u\cdot x\rangle ^2\right]}$$

I'm inspired by stochastic power iteration which gives a good estimate of $\max_{\|u\|=1}E\left[\langle u\cdot x\rangle ^2\right]$ by iterating $u \leftarrow x x^T u; u \leftarrow u/\|u\|$ a small number of times, considerably less than $d$ when distribution has small effective rank. Is there a modification for the problem above?

Improve this question
$\endgroup$
3
  • $\begingroup$ any information on the law of $x$? Is it continuous? Tails? $\endgroup$
    – Thomas Kojar
    Commented Nov 9, 2023 at 19:46
  • $\begingroup$ I need to apply this in practice for unknown $x$, but for theory, it would be nice to see something that works for Gaussian $x$ $\endgroup$
    – Yaroslav Bulatov
    Commented Nov 9, 2023 at 19:52
  • $\begingroup$ Is $x$ centered? $\endgroup$
    – Iosif Pinelis
    Commented Nov 9, 2023 at 20:34

1 Answer 1

Reset to default
2
$\begingroup$

$\newcommand\si\sigma\newcommand\Si\Sigma$If $x$ is centered, then $u\cdot x\sim N(0,\si_u^2)$, where $\si_u^2:=u\cdot\Si u$ and $\Si$ is the covariance matrix of $x$. So, $$\frac{E(u\cdot x)^4}{E(u\cdot x)^2}=\frac{3\si_u^4}{\si_u^2}=3\si_u^2.$$ So, $$\max_{\|u\|=1}\frac{E(u\cdot x)^4}{E(u\cdot x)^2}=3\|\Si\|^2,$$ where $\|\Si\|$ is the spectral norm of $\Si$.

Generally, if $x\sim N(\mu,\Si)$, then $u\cdot x\sim N(\mu_u,\si_u^2)$, where $\mu_u:=u\cdot\mu$, so that $\mu_u^2\le\|\mu\|^2$ for any unit vector $u$. So, $$\frac{E(u\cdot x)^4}{E(u\cdot x)^2}=\frac{3\si_u^4+\mu_u^4+2\si_u^2\mu_u^2}{\si_u^2+\mu_u^2}\le3\si_u^2+\mu_u^2$$ and hence
$$\max_{\|u\|=1}\frac{E(u\cdot x)^4}{E(u\cdot x)^2}\le 3\|\Si\|^2+\|\mu\|^2.$$

Improve this answer
$\endgroup$
8
  • $\begingroup$ Thanks....I'm dealing with a non-centered case, and was looking for a computational approach to improve on the upper bound. As an intermediate step, I was looking for a iteration $v\leftarrow f_x(v)$ where $E[\ldots \circ f_x\circ f_x \circ f_x \circ 1] \to u$ where $u$ is the maximizer $\endgroup$
    – Yaroslav Bulatov
    Commented Nov 10, 2023 at 1:38
  • $\begingroup$ @YaroslavBulatov : I don't understand notations in your comment. What is $v$? What is $f_x$? What are the left and right arrows? $\endgroup$
    – Iosif Pinelis
    Commented Nov 10, 2023 at 3:12
  • $\begingroup$ $f_x(v)$ is a random function of arbitrary vector. The other arrow indicates that iterating $f_x$ on some starting point converges to $u$, the maximizer, in expectation as the number of iterations grow to infinity. An example of such iteration is $f_x(v)=(x x^T v)/\|x x^T v\|$ which appears to converge to $\operatorname{argmax}_uE[\langle u \cdot x\rangle^2]$ in this fashion $\endgroup$
    – Yaroslav Bulatov
    Commented Nov 10, 2023 at 3:53
  • $\begingroup$ @YaroslavBulatov : Your $f_x(v)$ and all its iterations will just be $\pm x/\|x\|$. I don't see how this could work and what your point here is. $\endgroup$
    – Iosif Pinelis
    Commented Nov 10, 2023 at 4:08
  • $\begingroup$ If $x_1,x_2,x_3,\ldots$ are copies of random variable $x$ then as $n\to \infty$ we have $E[f_{x_n}\circ \ldots \circ f_{x_1} \circ \mathbf{1}]$ converging to $\operatorname{argmax}_u E[\langle u\cdot x\rangle^2]$. I want to find analogous $g_x$ such that $E[g_{x_n}\circ \ldots \circ g_{x_1} \circ \mathbf{1}]$ converges to $\operatorname{argmax}_u \frac{E[\langle u\cdot x\rangle^4]}{E[\langle u\cdot x\rangle^2]}$ $\endgroup$
    – Yaroslav Bulatov
    Commented Nov 10, 2023 at 7:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .