Expressing vectors as linear combinations of a set of other vectors

Question

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.

Answer 1

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}

Answer 2

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]

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

(rr = RowReduce[am]) // MatrixForm

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

Answer 3

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.