2
$\begingroup$

I have a list of twenty different 125-component vectors.

I have a bunch of other 125-component vectors which are known a priori to be expressible as a linear combination of these twenty.

I want a way to input a 125-component vector and return a 20-component vector which is the coefficient of each of my twenty 'basis' vectors in said linear combination.

I realise this can be done using 'Solve', but when I scale this up (i.e. more vectors with more components), it gets extremely slow. Is there an elegant way to do this with something like a row reduction?

As a simple test case it would be good to have a procedure which can give me the coefficients of {5,1,0,2,3,4} in terms of {{1,1,0,0,0,0}, {0,1,0,0,0,0}, {0,0,0,2,0,1}, {0,0,0,0,1,0}, {0,0,0,0,0,1}}, for which I would want output {5,-4,1,3,3}.

Edit: approaches like Solve or LinearSolve do work, but they become extremely slow on scaling. I should add that both the basis vectors and the vectors themselves are generically rather sparse, so my suspicion is that some more manifestly matrix-based method using e.g. row reduction might be better suited.

$\endgroup$

3 Answers 3

2
$\begingroup$

Does LinearSolve do what you need?

LinearSolve[
    Transpose @ {{1,1,0,0,0,0},{0,1,0,0,0,0},{0,0,0,2,0,1},{0,0,0,0,1,0},{0,0,0,0,0,1}},
    {5,1,0,2,3,4}
]

{5, -4, 1, 3, 3}

$\endgroup$
1
  • $\begingroup$ LinearSolve does work, and it fares a bit faster than Solve -- but it does still get very slow once scaling up. $\endgroup$
    – Facieod
    Mar 29, 2023 at 16:09
1
$\begingroup$

To get the coefficients of "v" relative to the base: "bas" using "RowReduce" you would first create the column matrix of base vectors and append "v" on the right side to get the augmented matrix: "am":

bas = {{1, 1, 0, 0, 0, 0}, {0, 1, 0, 0, 0, 0}, {0, 0, 0, 2, 0, 1}, {0,
     0, 0, 0, 1, 0}, {0, 0, 0, 0, 0, 1}};
v = {5, 1, 0, 2, 3, 4};

am = Join[Transpose[bas], Transpose[{v}], 2];
MatrixForm[am]

enter image description here

Now "RowReduce" gives the solution as the first 5 numbers of the last column:

(rr = RowReduce[am]) // MatrixForm

enter image description here

The solution are the 5 first numbers of the last column:

sol= rr[[;;4,-1]]
{5, -4, 1, 3, 3}

To check if this linear combination of the base really give "v" we may write:

sol.bas == v
True
$\endgroup$
1
$\begingroup$

You can use the Moore–Penrose pseudoinverse:

A = {{1, 1, 0, 0, 0, 0}, {0, 1, 0, 0, 0, 0}, {0, 0, 0, 2, 0, 1},
     {0, 0, 0, 0, 1, 0}, {0, 0, 0, 0, 0, 1}};

B = PseudoInverse[Transpose[A]];

B . {5, 1, 0, 2, 3, 4}
(*    {5, -4, 1, 3, 3}    *)

or (equivalently) a least-squares solver:

LeastSquares[Transpose[A], {5, 1, 0, 2, 3, 4}]
(*    {5, -4, 1, 3, 3}    *)

LeastSquares has a Method argument that may speed up the calculation. Specifically Method -> "Krylov" may be very efficient for sparse systems.

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