1
$\begingroup$

Given an overdetermined real linear system $Ax = b$, with $m$ equations, $n$ variables, and some unknown elements in both $A$ and $b$. I need to know what constraints must be imposed on those unknown elements (not the variables) so that the system becomes consistent and with a single solution (the solution itself doesn't matter).

The system must thus satisfy two conditions ($A^+$ is the Moore-Penrose pseudo inverse):

  • $AA^+b = b$: the system is consistent
  • $A^+A = I$: there is only one solution

The question is how to derive $A^+$? The Wikipedia page on the pseudo inverse lists various methods, but only one, QR decomposition, is not iterative or rely on $A$ being full rank (or at least having a known rank). QR decomposition can be carried out analytically (by using the Gram–Schmidt process, for example), but how can I obtain $A^+$ from $Q$ and $R$? I've googled for a few hours, but the only result found was (from algopy): $A^+ = w$, where $w$ is the solution to $Rw = y$ and $y$ is the solution to $R^Ty = A^T$, but it assumes $A$ is full rank.

$\endgroup$
  • $\begingroup$ I think your question is a little too general. We have a matrix A about which we know only that it is overdetermined. We know nothing about the composition of A, which elements may be unknown, etc. Likewise with b. So I don't see how we could derive A+ when we know nothing about A. Perhaps you could begin with a specific example of A and b, say A upper triangular with a11 unknown and all the other rows basis vectors; and maybe b1 unknown. See where that gets you. It might throw some light on things. $\endgroup$ – Betty Mock Aug 16 '13 at 4:33
  • $\begingroup$ @Betty Mock: the linear system is unconstrained, and I am hoping I can avoid special cases. My problem is, I have a collection of objects and a collection of sets, where set membership is controlled various constraints and represented by a linear system. If the system is consistent, the object is in, otherwise it's out. Instead of trying every object + set combination, I'm trying to find a way to speed things up by ruling out some combinations. $\endgroup$ – moatPylon Aug 16 '13 at 5:04
  • 1
    $\begingroup$ I suggested looking at some special cases not because that solves your problem per se, but because such cases often illuminate the situation. I looked around a bit about pseudo inverses and found a suggestion of using the singular value decomposition, which seems to be a generalization of eigenvalue decomposition. It does not depend on full rank. $\endgroup$ – Betty Mock Aug 17 '13 at 3:52
  • $\begingroup$ @Betty Mock: I'll see if I can learn something from a few examples here. Regarding SVD, the analytical approaches I found are way over my head :( $\endgroup$ – moatPylon Aug 18 '13 at 19:44
  • $\begingroup$ When I get a little time I'll try to look into it. I do like this pseudo inverse -- it looks so useful. Keep working. You're bound to get somewhere (if not to exactly where you hoped). $\endgroup$ – Betty Mock Aug 19 '13 at 15:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.