5
$\begingroup$

I have a set of $n$-dimensional vectors, and would like to choose $m$ of them to become the columns of an $n\times m$ matrix. I would like to choose the subset that maximizes $|A^T A|$, where $A^T$ is the transpose of $A$ and $||$ is notation for the determinant.

Can this be done faster than trying out each of $n \choose m$ possible combinations?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
5
$\begingroup$

A related task to this is to find a subset of column vectors that are maximally linearly independent. Linear independence isn't exactly the same thing as asking for a large determinant, but if we can use one as a proxy for the other then this heuristic may help you.

Rank revealing QR factorization (RRQR) is a good way to achieve this related task. One of the outputs of rank-revealing QR is a permutation of the input vectors that results in an approximate maximal linear independence. In Python for example I can do the following:

import numpy as np
import scipy.linalg as la

n=10  # Size of column vectors
nvectors=500  #Number of vectors to generate
np.random.seed(3244) #Seed RNG to make result reproducible
A=np.random.rand(n,nvectors) 

(Q,R,P)=la.qr(A,pivoting=True) #pivoting=True switches to RRQR algorithm

k=5 #Choose k vectors out of total
B=A[:,P[0:k]] #B is vectors from the RRQR ordering
C=A[:,0:k] #C is vectors in original ordering
print("Permuted: {}, Un-Permuted: {}".format(np.linalg.det(B.T@B),np.linalg.det(C.T@C)))

#output: Permuted: 60.60606973650909, Un-Permuted: 1.005883253383066

Edit: On second thought this may be much closer to what you explicitly asked for than I realized, and not just a heuristic. You can use the RRQR factorization itself to find the determinant of this submatrix (product of diagonal entries of its upper triangular factor), and since RRQR permutes to make the diagonal entries nonincreasing this suggests we actually get close to the largest possible determinant by using the permutation.

This may not strictly be the case though because the permutation generated by RRQR is approximate, it isn't necessarily the best possible. In other words: there could be other RRQR factorizations which do a little better.

Improve this answer
$\endgroup$
3
  • 3
    $\begingroup$ I confirm that RRQR is just a heuristic and it doesn't give the exact minimizer in all cases. But if I am not mistaken one can prove that it's a factor $O(n^n)$ away (at most) from the optimal determinant (see arxiv.org/abs/1006.4349 for the case of a square submatrix and the paper linked in my answer). This is not as bad as it looks at first, because (1) the determinant is scaled in a funny way and often one works with the logdet (2) in principle, if the columns are badly scaled the determinants could be arbitrarily large. $\endgroup$
    – Federico Poloni
    Commented May 2, 2019 at 7:19
  • $\begingroup$ Thanks for the added context. It surprises me we can get any kind of bound at all. $\endgroup$
    – Reid.Atcheson
    Commented May 2, 2019 at 13:06
  • $\begingroup$ To see why this bound holds (for the case of a square $n\times n$ submatrix of a $n\times m$ submatrix, as in your example), factor the R matrix returned by RRQR as R=DU, where D is diagonal and U has ones on the diagonal and all its entries bounded by 1 (because of how RRQR is constructed): now, the determinant of the submatrix selected by RRQR is det(D), while any other $n\times n$ submatrix can be written as DM, where M is a suitable submatrix of U and hence has all its entries bounded by 1. And if M has all entries bounded by 1 then $\det(M) \leq n! = O(n^n)$. $\endgroup$
    – Federico Poloni
    Commented May 8, 2019 at 8:26
4
$\begingroup$

It's NP-hard, but there are some heuristic algorithms. See https://arxiv.org/abs/1502.07838 which treats this problem.

Improve this answer
$\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.