Submatrix with greatest determinant?
- To: mathgroup at christensen.cybernetics.net
- Subject: [mg689] Submatrix with greatest determinant?
- From: rak at canon.co.uk (Richard Kirk)
- Date: Mon, 10 Apr 1995 11:29:15 GMT
Given M vectors in N dimensions, where M > N, I need to find the subset of
N vectors that as an N*N matrix has the greatest determinant.
I can do this by finding out all the possible subsets and evaluating all
the determinants. My crude program went something like this...
--------
Needs ["DiscreteMath`Combinatorica`"];
spectra = << WandN.spectra ;
keeplist = Range[5,35,3];
patchlist = {1,2,3,4,5,6,7,10,11,14,16,23,
32,37,42,43,44,52,53,54};
subspec = spectra[[patchlist,keeplist]];
sublist = KSubsets[Range[Length[subspec]],Length[keeplist]] ;
detlist = Abs[Det[subspec[[#]]]]& /@ sublist ;
detmax = Max[detlist]
{{p}} = Position[detlist,detmax,{1}] ;
newlist = patchlist[[sublist[[p]]]]
newspec = subspec[[sublist[[p]]]];
(etc)
---------
The 'sublist' and the 'detlist' lines take a lot of calculating. I know the
others are not as fast as they might be, but these two are the real killers.
I can avoid keeping the values of 'sublist' and roll the two lines into one.
There is a quick way of finding the nth Ksubset. It doesn't seem to save
that much time, though.
My vectors are bases on experimental results so it is not worth
having a first pass to weed out similar vectors.
Clearly it is possible to re-use a lot of the determinant calibrations
and abandon some of the calculations where it is obvious the determinant
will not exceed the maximum value.
Has anyone got a fast solution to this? Or does anyone want to collaborate
on building one?
--
Richard Kirk 01483-448869 (phone) 01483-448845 (fax)
Canon Research Europe Ltd, rak at canon.co.uk