1
$\begingroup$

I would like to compute, in MATLAB, the basis Z for the nullspace of an m by n matrix A, such that if one row of A is added (resulting in A_a), the basis for A_a is n-m-1 of the n-m columns of Z, i.e., is obtained by deleting one column from Z. Similarly, if one row of A is deleted (resulting in A_d), the basis for A_d will be Z plus one new column. I am willing to compute the Z from scratch each time a row of A is added or deleted, or use an updating method, as long as I achieve the properties stated. You can presume that A is always full rank.

I am not worried about finding the most computationally efficient way of doing this (but all else equal, computational efficiency is good). Note that use of the MATLAB null(A), which is based on SVD, does not achieve this. Picking the last n-m columns of Q in the QR factorization of A' also does not achieve this, even though both of these methods produce a valid nullspace basis Z.

It is doable. How do I know? Because it was figured out more than 40 years ago, and is used in various optimization software. However, I've never seen the (a) method for doing this described clearly and understandably, more along the lines of employing a sequence of Householder transformations to annihilate certain elements, thereby updating a previous basis Z. However, I believe the authors were interested in the most efficient implementation, not the easiest to implement.

I need this in order know how to transform a Quasi-Newton Hessian projected into the nullspace of A, i.e., Z' * Hessian * Z, to be projected into the new nullsapce corresponding to a row being deleted or added to A. That way I don't have to throw out the entirety of my Quasi-Newton approximation when a row goes into or out of A, and can either project my existing projected Hessian into the lower dimensional space when adding a row to A (for instance, by removing the corresponding row and column from my existing projected Hessian), or know where to add a an initialized (e.g., identity) row and column to my existing projected Hessian when deleting a row from A.

This scenario would arise, for instance, when the working set in a nullspace active-set Sequential Quadratic Programming algorithm using Quasi-Newton approximation to the projected (a.k.a. reduced) Hessian, changes. See the bottom half of p. 15 (you may have to read earlier sections to understand this though) of http://web.stanford.edu/class/msande312/restricted/mse312proj2008_3.pdf for the context I am talking about. I.e., updating a projected (a.k.a. reduced) Quasi-Newton Hessian approximation when the nullspace into which the Hessian is being projected, changes due to change in working set.

Thanks.

$\endgroup$

0

You must log in to answer this question.

Browse other questions tagged .