Select columns from multiple matrices to form a well-conditioned matrix

Hi,

Given multiple matrices of the same size, is there a way to select one column from each matrix to form a well-conditioned matrix?

For example, given four 4-by-10 matrices A B C D (real, positive and full ranked), I would like to select exactly one column from each matrix, and form a new 4-by-4 matrix E, such that E is well-conditioned. I know that it's NP-hard to find the optimal solution, but is there any algorithm to efficiently solve this problem? Thank you!

[Matt J]

How efficient does it need to be? What is the typical number and dimension of the matrices in a realistic example?

[Slime]

Hi,

A typical problem contains four 4X8 matrices, and you need to pick one column from each of them to form a new 4X4 matrix. With brute force you will have to try 8^4 = 4096 combinations. I am looking for a heuristic method that might take polynomial time.

Answer 1

[John BG]

Slime

In MATLAB R2016a the following only takes 0.2 seconds, is this delay acceptable?

p=combinator(8,4,'p','r');
randi([-10 10],4,8)
A=randi([-10 10],4,8);    % test inputs
B=randi([-10 10],4,8);
C=randi([-10 10],4,8);
D=randi([-10 10],4,8);

R={};
tic;
for k=1:1:length(p) 
    R=[R [A(:,p(1)) B(:,p(2)) C(:,p(3)) D(:,p(4))] ];   
end
toc;

Elapsed time is 0.200348 seconds.

To get each row combination

E1=R{1} 
E1 =
         -5.00          8.00          1.00         -5.00
        -10.00         10.00         -1.00          6.00
         -8.00          1.00        -10.00         -1.00
          7.00         -8.00         -3.00          9.00

To find a 'heuristic' way to calculate matrices E, you may want to define a cost function, or to define a rule to

1.- start generating a few E,

2.- choose one to minimize the cost

3.- generate a few more E that has something in common to the 1st chosen E, like one or more elements, or a row.

Iterate until the target E reached

If you find this answer of any help solving your question,

please click on the thumbs-up vote link,

thanks in advance

John

[e-mail]

[Slime]

Thanks!