2
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ If I am not mistaken, it is possible to simplify your objective function by normalizing columns to have norm 1. $\endgroup$ Dec 7, 2016 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, 2016 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$ Dec 7, 2016 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, 2016 at 23:18

1 Answer 1

3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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