0
$\begingroup$

Take a linear system of the form $Ax=b$. Usually, for obvious reasons, we want to find $x$ given $A$ and $b$. As you all know, the solutions may not be unique, or exist, and many algorithms have been proposed to find them effectively for different $A$.

Are there any methods to generate $A$ given $x$ and $b$? I realise that, of course, a) this might not be a useful problem to consider, and b) $A$ is of course not unique. Apologies if c) I'm missing an obvious trick to generate a trivial $A$.

Here's some background about my problem: I'm solving a large linear system with an LSQR algorithm. Here, $A$ is about $4000\times2000$, not sparse, and ill conditioned -- $\text{cond}(A)$ is about $10^{10}$. It transpires that my problem is "semi convergent", in the sense that this large condition number means that any attempt to solve it eventually fails due to effects of numerical precision. The literature states that people take enough iterations of LSQR to decrease the residual a lot, and then give up as further iterations serve to make the solution worse; commonly the number of iterations, $n$, used is only 4-10; for my problem, all hell breaks loose when $n>10$ and $n=4$ is, amazingly, pretty good.

I've had success building some physics into my model such that every evaluation of $A$ is very slightly (but deterministically) different, with changes that are physically motivated. The solution is quantitatively and qualitatively "much better", and is still good for $n>200$. I am certain that the effect of my modifications to $A$ are essentially preconditioning it with something like a Fourier matrix multiplied by a filter that kills high frequency noise. I'd like to know what the condition number of my 'equivalent' $A$ is, and moreover just how different a given $A$ is from the problem I started with.

Apologies if this should be on another SE instead, but my fundamental question is one of linear algebra.

EDIT: For my problem, $x$ and $b$ are just vectors $\in\mathbb{C}$, and $A$ is a complex rectangular matrix. I'd of course be interested in general answers, however.

$\endgroup$
3
  • 1
    $\begingroup$ Given why you want to recover $A$, the answer is certainly no. As you point out, the choice of $A$ is not unique. There is not going to be a way to retrieve the one you need for condition number estimation. But LSQR can actually recover an estimate of the condition number as part of its iteration process. $\endgroup$ – Michael Grant Mar 9 '15 at 20:51
  • 1
    $\begingroup$ math.stackexchange.com/questions/1170843/… $\endgroup$ – Algebraic Pavel Mar 9 '15 at 22:07
  • $\begingroup$ Are you by any chance interested in the least squares backward error? In that case, not any $A$ would work for a given $b$ and, in particular, $x$. $\endgroup$ – Algebraic Pavel Mar 9 '15 at 22:14
2
$\begingroup$

Yes, given $x$ and $b$, it is trivial to generate $A$ such that $Ax=b$ -- unless, of course, $x$ is zero and $b$ is nonzero, in which case it is impossible.

If $x=b=0$, then any $A$ will work.

Otherwise pick a nonzero entry of $x$, say $x_i$. Now let all of $A$ be zero, except that the $i$th column is $b$ scaled by $\frac1{x_i}$.

$\endgroup$
2
  • $\begingroup$ I've just realised that here the length of $b$ is not the same as the length of $x$. What happens to the extra elements? $\endgroup$ – Landak Mar 9 '15 at 21:09
  • $\begingroup$ @Landak: The length of $b$ is the height of $A$; the length of $x$ is the width of $A$. It all works out without any elements sticking out. $\endgroup$ – hmakholm left over Monica Mar 9 '15 at 21:19
2
$\begingroup$

Not sure if this is what you're looking for, but take the case $b = (b_{1}, b_{2}, b_{3}), x = (x_{1}, x_{2}, x_{3})$ with each $x_{i}$ invertible, then a trivial answer is $A = (a_{i,j})$ where $a_{i,i} = b_{i}x_{i}^{-1}$ and other entries are $0$.

$\endgroup$
1
  • $\begingroup$ These are all excellent answers that made me aware how I'd completely missed the obvious answer. Thank you! $\endgroup$ – Landak Mar 9 '15 at 20:38
2
$\begingroup$

Assuming $x,b \neq 0$ (otherwise cases are trivial). Normalize $x$ and then write normalized $x$ as the first row of square matrix $M$, and then fill in the rest of the rows with whatever vectors you want to make an orthonormal basis. Then fill in the first column of a matrix $M'$ with $b$ and similarly complete the columns to form a basis. Then one possibility for an invertible form of your matrix is $A=M'M$.

I'm not totally sure but I think there are enough degrees of freedom in constructing $A$ this way that this may capture all possible invertible $A$ when $x,b \neq 0$.

$\endgroup$
4
  • $\begingroup$ Well, if you construct both $M$ and $M'$ to be orthogonal, then $M'M$ will naturally be so, too. But if you allow the other columns of $M'$ to be arbitrary then you do get all possible $A$, invertible or not. $\endgroup$ – hmakholm left over Monica Mar 9 '15 at 20:38
  • $\begingroup$ @HenningMakholm Yes I wasn't totally clear but I omitted the word "orthogonal" or "orthonormal" when constructing $M'$ on purpose, I only intended that to be an arbitrary basis (including $b$, of course). It's interesting that arbitrary $M'$ gives all $A$, I don't see the proof but I'll take your word for it. $\endgroup$ – user2566092 Mar 9 '15 at 20:40
  • $\begingroup$ x @user, proof: Given an arbitrary $A$ with $Ax=b$, you can let $M'=AM^{-1}$. Then certainly $M'M=A$. And since $M'Mx=b$ and $Mx=\mathbf e_1$ by construction, the first column of $M'$ must be $b$. $\endgroup$ – hmakholm left over Monica Mar 9 '15 at 20:48
  • $\begingroup$ @HenningMakholm Neat! I was hoping that this construction gave arbitrary $A$. Thanks for sharing. $\endgroup$ – user2566092 Mar 9 '15 at 20:52
1
$\begingroup$

In quasi-Newton methods like Broyden or BFGS one uses the minimal rank-1 or rank-2 modification of an existing matrix such that the new matrix satisfies your initial equation. This has an exact mathematical theory $$ \text{minimize } \|A-B\|_F\text{ s.t. } Ax=b, $$ i.e., using the Lagrange formalism for $$ L(A)=\frac12\,\|A-B\|_F^2+v^T(Ax-b) $$ with the derivative $$ 0=L'(A)=(A-B)+vx^T $$ so that $A=B-vx^T$ and inserting into the constraint $b=Bx-vx^Tx$ so that finally $$ A=B-\frac{(Bx-b)x^T}{x^Tx} $$

The other Broyden method results from minimizing $\|A^{-1}-B^{-1}\|_F$

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.