I'm trying to solve this discrete optimization problem:$\newcommand{\I}{\mathcal{I}}\newcommand{\R}{\mathbb{R}}$ $$\max_{|\I| \le k} f(\I) \qquad\text{where}\; f(\I) :=x_{\I}^{\top} (\Sigma_{\I})^{-1} x_{\I}.$$ Here

  • $\I \subseteq [d] = \{1, 2, \dots, d\}$;
  • $x \in \R^d$ is a fixed vector;
  • $\Sigma \in \R^{d \times d}$ is a fixed positive-definite matrix;
  • $x_{\I} \in \R^{|\I|}$, $\Sigma_{\I} \in \mathbb R^{|\I| \times |\I|}$ are the subsets of $x$ and $\Sigma$ obtained by taking only the rows and columns corresponding to the indices in $\I$;
  • $d$ is potentially fairly large (between hundreds and maybe hundreds of thousands); $k$ is fairly small (up to maybe 20-50).

My first thought was a greedy algorithm – using the block matrix inverse formula, it's straightforward to work out $f(\I \cup \{ i \})$ in terms of $\Sigma_\I^{-1}$, and it all seems feasible computationally. Unfortunately, though, I found a counterexample showing $f(\I)$ isn't submodular, so the greedy approach may not work so well.

I'm interested in practical algorithms and/or algorithms with guarantees (ideally both). Is this problem studied in the literature already / what kinds of optimization algorithms should I be looking at other than just plain greedy?

P.S: If it helps, you can assume that $x$ is a sample from a normal distribution with mean 0 and covariance $\Sigma$; ideally, the algorithm would work well with high probability over the sample $x$.

  • $\begingroup$ Is $\Sigma_{\mathcal{I}}$ guaranteed to be invertible? Under the current conditions, if there is 0 on the diagonal of $\Sigma$, then this property may not hold. In that case, what do you define $f(\mathcal{I})$ to be? $\endgroup$
    – nir shahar
    Nov 23 '21 at 10:40
  • $\begingroup$ @nirshahar, $\Sigma$ is a covariance matrix, it has $1$ on the diagonal. $\endgroup$
    – Dmitry
    Nov 23 '21 at 12:07
  • 2
    $\begingroup$ co-author on the research here: It's a covariance, not a correlation, but $\Sigma$ is strictly positive definite and so $\Sigma_{\mathcal I}$ is guaranteed to be strictly positive definite as well. $\endgroup$
    – Danica
    Nov 23 '21 at 19:20
  • 2
    $\begingroup$ On second thought, you can absorb the scaling of $\Sigma$ into $x$ and so make $\Sigma$ a correlation matrix, if that's more convenient. $\endgroup$
    – Danica
    Nov 23 '21 at 20:22

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.