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.


**EDIT**


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



How to find the set of vectors which are as nearly orthogonal as possible?
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>.


