3
$\begingroup$

I am facing a problem where I have to find any (nontrivial) vector x such that Ax=0, where A is a rectangular nxm matrix with m>n, so the problem is underdetermined. I must find this x for A, but also for a new matrix A' = (A with the column j removed), and so on...

It would be very helpful to find a way to obtain the new solution x' for the matrix A' knowing the solution x for A without recomputing a whole null space by SVD or QR at each iteration. I managed to find x' with a Newton Raphson method (as x' is close to x with the element j removed), but I have that problem of inverting the Jacobian matrix at each iteration once again.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

There is literature on updating various matrix factorizations under rank-1 modifications (which includes row/column insertions and removals). See for instance Secton 6.5 on Golub--Van Loan 4th edition. In particular, QR updating is already implemented in Matlab and Scipy. I am not familiar with updates of the SVD, but a Google search for "svd update" returns various articles that treat this exact problem.

You will probably want to make sure that the factorization you update is a rank-revealing one; note that QR without column pivoting does not always work: there are counterexamples where all the diagonal entries of $R$ are large, but the matrix is numerically singular. For a specific example, see for instance Golub--Van Loan, 4th ed, sec. 5.4.3: there is an example of a 300x300 upper triangular matrix where the smallest diagonal entry is $\approx 0.05$, and yet the matrix has a singular value $\approx 10^{-19}$.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Hi Federico and also this is a question for the OP too. I was wondering, if the task is to find any non-trivial vector in the nullspace of A why would one choose the SVD or QR? Gaussian Elimination is faster, stable in practice and easy to update given a change in a column vector. $\endgroup$
    – Ivan Meir
    Commented Jun 24, 2020 at 11:38
  • $\begingroup$ @IvanMeir To make Gaussian elimination stable, you need pivoting, but I don't see immediately how you can combine pivoting and column updates. Do you have a specific procedure in mind? Also, standard Gaussian elimination with partial pivoting is known not to be "rank-revealing"; i.e., one can find examples where all pivots are large but the matrix has a very small singular value. $\endgroup$
    – Federico Poloni
    Commented Jun 24, 2020 at 11:47
  • $\begingroup$ For a specific example, see for instance Golub--Van Loan, 4th ed, sec. 5.4.3: there is an example of a 300x300 upper triangular matrix where the smallest diagonal entry is $\approx 0.05$, and yet the matrix has a singular value $\approx 10^{-19}$. $\endgroup$
    – Federico Poloni
    Commented Jun 24, 2020 at 11:54
  • $\begingroup$ Thank you Federico for your reply, I agree these are considerations and I guess the best option it will depend a lot on the data. If the column removed contains a pivot you need to perform more steps to repair the echelon form and recompute the solution but only to the right of the pivot. How expensive this will be overall depends on precisely how many of these columns are eventually removed. In terms of stability I agree there can sometimes be problems though my experience is that you generally do much better than the worst case scenario! Again it generally depends on the application :-) $\endgroup$
    – Ivan Meir
    Commented Jun 24, 2020 at 12:29
  • $\begingroup$ True but if your system is over determined and you don't have a weird case where most columns lie in a low dimensional space just picking a random set of columns should give you a reasonable starting point for elimination. Again it depends on the data distribution and the matrix dimensions. $\endgroup$
    – Ivan Meir
    Commented Jun 24, 2020 at 12:35
1
$\begingroup$

One way to compute a particular vector that solves such an undetermined system is to perform gaussian elimination and compute the row echelon form. If you then eliminate one column from the leading columns - the one's with 0's you can simply update the form with a few more operations and quickly update your solution.

Note that removing a column could require an update in most elements of your solution. For example if you have the following matrix with solution $(1,1,1,-1,0)$ then if you remove the first column the solution becomes $(0,0,0,1,-1)$ which is unique up to multiplication by a non-zero scalar.

$$\left[ \begin{array}{ccccc} 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 \end{array} \right]$$

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .