min ||Ax-b||^2 m>n

[Julian Steinwachs]

Hi there,

 

I'm a physicist working on my PhD, trying to back out forces cancer cells generate against there environment in a controlled in vitro system. And i boilled down one of the problems that i have to a linear algebra problem, which i think is quite general.

 

I've got a Matrix A. It is m by n with m>n (say 12000 by 10000) describing the forces in relation to the deformation x. And i got some external forces b. From that i can copmute an x that minimizes ||Ax-b||^2. Every row of A describes the forces at some position as linear combination of the deformation x. If i would now allow forces at specific index 1<=i<=m that would mean to clear the corresponding relation from A. So A would loose the i'th row. And by that ||Ax-b||^2 could in general be reduced more than with the row that was removed. Because there is less contraint on x now.

 

What i want to compute now as quickly as possible, for a subset of possible i's, is how much does the minimum of ||Ax-b|| get reduced if i remove the i'th row from A.

 

Thanks a lot

Julian