I have an $N$-dimensional vector of data, say $X_{t}$, with $1 \leq t \leq T$.

Of this vector $X_{t}$, I want to consider sub-vectors, say $X_{t}^{b}$, which are $m$-dimensional combinations of elements of the original vector $X_{t}$. In total, I have ${N}\choose{m}$ of such combinations.

Note that $N$ can be a large number; I need to allow for $N \rightarrow \infty$. Also, I will choose $m$ in such a way that $m$ is "smaller" than $N$, e.g. $m=O(N^{1/2})$.

I want to compute the $k$-th eigenvalue ($k$ is user-defined) of the second moment matrix of each of these $X_{t}^{b}$s, i.e.

$$\lambda_{k}^{b} \left( \frac{1}{T} \sum_{t=1}^{T} X_{t}^{b} (X_{t}^{b})' \right).$$

Then, finally, I want to compute

$$\max_{1 \leq b \leq B} \lambda_{k}^{b},$$

where $B$ is defined as ${N}\choose{m}$. In principle, I may need to compute also other measures such as the average of $\lambda_{k}^{b}$.

I have two questions:

  1. Is this problem NP-hard? Is there a reference to back up either statement (i.e. "it is" or "it is not")?
  2. Is there some heuristic to make the problem less computationally burdensome? Is there any way to prove, for a given heuristic, that the solution found by the heuristic is "very close" to $ \max\limits_{1 \leq b \leq B} \lambda_{k}^{b}$ - e.g. by showing that the solution found by the heuristic and $ \max\limits_{1 \leq b \leq B} \lambda_{k}^{b}$ are equal almost surely, or something similar?

Many thanks for your help.

  • 1
    $\begingroup$ I'll just say this, your problem is non-convex as hell ..., and not so easy. $\endgroup$ – Mark L. Stone Jun 25 '19 at 10:40
  • 3
    $\begingroup$ And it's not any more convex or easier on scicomp.stackexchange.com/questions/32950/… where you cross-posted this without even mentioning the cross-linking on either post. $\endgroup$ – Mark L. Stone Jun 25 '19 at 19:01
  • 1
    $\begingroup$ sadly true about the cross-linking, it is another one of the many things on which I cannot claim I know much (actually I did not know anything, not even the possibility of it) about. thank you for bringing it to my attention, somewhat less than respectfully but entirely understandable $\endgroup$ – Lorenzo Trapani Jun 26 '19 at 11:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.