# discrete optimization problem with a matrix inverse


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

• 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? Nov 23 '21 at 10:40
• @nirshahar, $\Sigma$ is a covariance matrix, it has $1$ on the diagonal. Nov 23 '21 at 12:07
• 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. Nov 23 '21 at 19:20
• On second thought, you can absorb the scaling of $\Sigma$ into $x$ and so make $\Sigma$ a correlation matrix, if that's more convenient. Nov 23 '21 at 20:22