1

I have a feeling that this is a rather silly question. If I have an $r$-ranked matrix ${\bf{A}} \in {\Bbb{R}^{m \times n}}$ which describes an overdetermined system (there are more equations than unknowns, $m>n$). There exists a basis of null-space of ${\bf{A}}$, denoted as ${\bf{C}} \in {\Bbb{R}^{n \times r}}$, such that ${\bf{A}}\left( {{\bf{C\beta }}} \right) = 0$ for any ${\bf{\beta }} \in {\Bbb{R}^r}$. Matrix ${\bf{A}}$ itself is a nonlinear function of vector ${\bf{x}} \in {\Bbb{R}^{m}}$. Is there a plausible way to calculate the first derivative of ${\bf{C}}$ with respect to ${\bf{x}}$, or ${\nabla _{\bf{x}}}{\bf{C}}$?

ar_k
  • 51
  • What do you mean by the derivative of the subspace $\text{ker}(A)$ with respect to $x$? – Robert Israel Nov 14 '19 at 15:12
  • 1
    Yes. Here is one way: suppose that the rank of A is constant in a neighborhood of x. Then the dimension of C is constant, say k. So, we obtain a function from x to the Grassmannian of k planes. The latter is a smooth manifold, so you can compute the derivative of that map, as a linear function between the tangent spaces. I assume there is a more concrete matrix algebra interpretation of this also, but I don't know it. Start with the case k = 1, by comparing to the sphere you can work out the tangent space explicitly. You can reduce to the case m = 1 by linearity. So you have a curve of lines. – Elle Najt Nov 14 '19 at 15:17
  • @RobertIsrael The marix ${\bf{A}}$ is a function of vector ${\bf{x}}$. The derivative of ${\bf{A}}$, ${\nabla _{\bf{x}}}{\bf{C}}$ exists and rather easy to find. What I am looking for is ${\nabla _{\bf{x}}}\ker \left( {\bf{A}} \right)$ – ar_k Nov 15 '19 at 12:18
  • @LorenzoNajt seems interesting. I am not at all famiiar with the Grassmannian, do you have a good reference? – ar_k Nov 15 '19 at 12:20
  • 1
    I repeat, $\ker(A)$ is a vector space, not a vector or matrix. What does $\nabla_x \ker(A)$ mean? – Robert Israel Nov 15 '19 at 13:30
  • It is a standard example in most books on smooth manifolds or algebraic geometry. – Elle Najt Nov 15 '19 at 13:30
  • @RobertIsrael I meant the basis of the null space of ${\bf{A}}$. I have to admit that I am not entirely sure how to notate that. – ar_k Nov 25 '19 at 09:10
  • 1
    $\bf{C}$ is not unique. – edm Nov 25 '19 at 09:21
  • 1
    The kernel of a matrix is a set of vectors that are mapped to 0. This set can be described by a set of basis vectors, but these are not unique (many different sets of basis vectors work) and their order is also arbitrary. Therefore even for a well-intentioned reader there is no way to give a meaningful definition for $\bf C$. – orlp Nov 25 '19 at 09:44
  • 2
    You can fix all of these objections about uniqueness, since if you pick some starting C there is a natural way to continue your choice. You can do this by using parallel transport of sections of the tautological bundle on the Grassmannian: https://math.stackexchange.com/a/832445/54092 this sounds fancy but is pretty concrete /programmable , see the comments on that answer. I'm not totally sure that this preserves basis (or inner products between vectors), but I guess it probably does. – Elle Najt Nov 27 '19 at 17:49
  • Maybe you can interpret that parallel transport as finding the nearest ordered basis for the new subspace to the previous basis for the old one, where you use the Euclidean distance. – Elle Najt Nov 27 '19 at 17:54
  • @LorenzoNajt But surely this applies only locally? Because I have tried to numerically vary ${\bf{A}}$, and I found the basis of null space (computed via SVD) highly discontinuous. – ar_k Dec 01 '19 at 16:50
  • 1
    If you recompute the null space for each A, there's no guarantee that you will get basis that are close to each other. Numerically, I think you can do the following. Say you have a basis for A_0 and a basis for A_1 (where A_0 and A_1 are close), B_0 and B_1. Then, find the matrix Q that minimizes || B_0 - B_1 Q||_2. Here the B_i are m times n and Q is a square n x n matrix, which is finding a basis for A_1 that is near to the basis B_0. You may want to add the constraints that Q^T Q= I ... Or maybe just applying Gram-Schmidt to B_1 Q will work, where Q solves the unconstrained problem. – Elle Najt Dec 01 '19 at 17:22
  • On that optimization problem: https://en.wikipedia.org/wiki/Orthogonal_Procrustes_problem – Elle Najt Dec 01 '19 at 17:40
  • @LorenzoNajt Your procrustes idea is actually very useful. Thanks! – ar_k Dec 04 '19 at 18:26
  • You're welcome. :-) Glad it was helpful. – Elle Najt Dec 05 '19 at 22:31
  • @LorenzoNajt Can you provide a reference to a book which shows a solution to this problem? You said it is a standard example, but I've been banging my head against this the whole week and I've neither found a reference nor managed to solve it myself. – cfh Sep 18 '20 at 16:22
  • @cfh I meant that the Grassmannian is a standard example of a manifold or variety. This looks like a nice survey: https://www-m3.ma.tum.de/foswiki/pub/M3/Allgemeines/DanielKarrasch/Intro_Grassmann.pdf What exactly is the problem you are trying to solve? To me it seems like the discussion above evolved into 'the problem isn't really well defined, but there's a way you can make it well defined, and maybe this numerical approach will work.' – Elle Najt Sep 18 '20 at 17:08
  • @LorenzoNajt The problem I'm trying to solve is much like the stated question, but with the added understanding that the space spanned by the matrix as well as its transverse, the nullspace, are members of the Grassmannian. This takes care of the uniqueness problems, as you noted. You said "I assume there is a more concrete matrix algebra interpretation of this also, but I don't know it." That's what I'm trying to derive, since I need the derivative in computable (and, if possible, closed) form for an algorithm. – cfh Sep 18 '20 at 18:35
  • @cfh It seems like they work some of that question out on page 15 of the notes I linked you to in the previous comment? Lemma 4.6 seems to be saying something about gradients on the Stiefel manifold. I haven't read these notes too closely, so I'm not sure what half of the notation means. I guess at least a partial answer to your question is in them. – Elle Najt Sep 19 '20 at 02:33
  • Also, maybe the person who originally asked has a working solution or reference at this point that they can share? @ar_k Anyway, you (cfh) might have better luck opening a new question. – Elle Najt Sep 19 '20 at 02:34
  • @LorenzoNajt I think I finally worked it out. I will check through the notes you linked and see if the result is already there, or easily obtained as a corollary. Otherwise I have to work out all the details and write up the result. Thanks for your comments. – cfh Sep 19 '20 at 11:30
  • @cfh I'm really not the right person to ask about whether or not the result exists in the literature somewhere. I would not be very surprised if it did not -- a lot of results come up if you google things like "numerical analysis Grassmannian" and similar search queries. – Elle Najt Sep 19 '20 at 17:43

0 Answers0