I've got a (to be a bit specific) 84-dimensional rational vector space, and as many as 1197 vectors in it. In the basis of the space that I've got, numbers of nonzero coordinates for these vectors range from 1 (in two cases) to 71 (in six cases), the average number being between 40 and 41.
I want to find a basis in which the numbers of nonzero coordinates in my 1197 vectors become as small as possible. What would be an efficient algorithm to achieve that?
I asked ChatGPT and it named spgl1 in MATLAB, along with non-specific advice on using GUROBI, CPLEX, the LINBOX C++ library. Maybe somebody has specific experience of using these or other tools for this particular kind of problem?
I found a related question here, Minimize the maximum Hamming weight of basis vectors spanning a binary subspace but it is about Hamming weights of binary vectors, i. e. the 2-element field, while I need rationals.
-
$\begingroup$ Sorry, from your question I thought you wanted to minimize number of non-zero components of the basis vectors. So you want to minimize number of non-zero components of the vectors in your set when written wrt the new basis? $\endgroup$SilvioM– SilvioM2024年08月14日 16:28:25 +00:00Commented Aug 14, 2024 at 16:28
-
$\begingroup$ @SilvioM yes exactly $\endgroup$მამუკა ჯიბლაძე– მამუკა ჯიბლაძე2024年08月14日 16:29:31 +00:00Commented Aug 14, 2024 at 16:29