Let $\mathbf{A}=[a_{ij}]$ be a matrix of real numbers $a_{ij}>0$ for all $i\in\{1,\ldots,k\}$ and $j\in\{1,\ldots,n\}$ and let $v$ be a nonnegative real number. The coefficient of the matrix are not all greater than $1$ nor all less than one.

The problem is to find a subset $S$ of the columns (of $\{1,\ldots,n\}$) where $S\neq \emptyset$ and $S$ is not a singleton such that $$\delta(S, \mathbf{S}) = \dfrac{\prod_{j\in S} ||b_j||}{\sqrt{\det(\mathbf{S}^\top \mathbf{S})}}\leqslant v.$$ Here $\mathbf{S}$ is a matrix whose columns are $b_j:=[a_{1j}, a_{2j}, \ldots, a_{kj}]^\top$ for $j\in S$.

In fact, in the optimization settings, I would like to find a subset $S$ of vectors which are as nearly orthogonal as possible. Or simply $$\underset{S\subseteq \{1,\ldots,n\}\\S\neq\emptyset}{\text{minimize }\;} \delta(S, \mathbf{S}).$$

Example: Take $v=0.17$ and $$\mathbf{A}=\begin{bmatrix} 0.1&2&3\\2&0.2&0.1\end{bmatrix}.$$ In $S=\{1, 2\}$, the matrix is $$\mathbf{S}=\begin{bmatrix} 0.1&2\\2&0.2\end{bmatrix}.$$

This example has the solution $S=\{1,3\}$. Its value $\delta(S, \mathbf{S})=0.1675$.

How to solve this problem? Is this problem known (or is there any similar problem in the literature)?

Besides enumerating all subsets of $\{1,\ldots,n\}$, I cannot find a good way to solve the problem.


According to Federico's comment, the problem seems to be equivalent to $$\underset{S\subseteq \{1,\ldots,n\}\\S\neq\emptyset}{\text{maximize }\;} \det(\mathbf{S}^\top\mathbf{S}),$$ where $\mathbf{S}$ is the matrix whose columns are $[a_{1j}, a_{2j}, \ldots, a_{kj}]^\top$ for $j\in S$.

  • $\begingroup$ If I am not mistaken, it is possible to simplify your objective function by normalizing columns to have norm 1. $\endgroup$ – Federico Poloni Dec 7 '16 at 22:48
  • $\begingroup$ So I will be left with maximizing $\sqrt{\det(\mathbf{S}^\top \mathbf{S})}$ over all subsets $S$? $\endgroup$ – drzbir Dec 7 '16 at 22:59
  • 1
    $\begingroup$ Yes. And of course you can also get rid of the square root. And since you can rescale the matrix, your other constraint on the matrix coefficients is probably not relevant. And, at this point, you can convert the problem into one on $A^\top A$. $\endgroup$ – Federico Poloni Dec 7 '16 at 23:05
  • $\begingroup$ If I understand you correctly, the problem becomes: given the matrix $\mathbf{A}\in\mathbb{R}_{>0}^{k\times n}$, find a submatrix $\mathbf{S}\in\mathbb{R}_{>0}^{k\times|S|}$ such that $\det(\mathbf{S}^\top\mathbf{S})$ is maximum? If so, is this easy to solve? $\endgroup$ – drzbir Dec 7 '16 at 23:18

Wanted to post it as a comment, but I realize it feels more like an answer.

If I am not mistaken, after some simplifications (column rescaling) the problem can be transformed into: given the semidefinite matrix $B=A^\top A$, find an index set $I$ such that $\det B(I,I)$ is maximum. I don't think it is easy to solve. If I recall correctly, for general matrices the "maximum volume submatrix" problem is NP-hard (see http://www.sciencedirect.com/science/article/pii/S0304397509004101). The version for SPD matrices may be easier, though.

There is some theory and algorithms on finding "large enough" subdeterminants, though. For instance, see the paper "How to Find a Good Submatrix", Goreinov et al., http://spring.inm.ras.ru/osel/wp-content/plugins/wp-publications-archive/openfile.php?action=open&file=15.

A more recent paper that deals with a problem very similar to yours, involving $S^\top S$, is in https://arxiv.org/abs/1502.07838.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.