Best way to solve $A$ from $Ax=b$ when $x$ and $b$ are given

Question

I was about to solve this equation:

$$z_1 = Ax$$ $$z_2 = Bz_1$$ $$z_3 = Cz_3$$ $$b = Dz_3$$

where $b$ is a vector and $x$ is a vector and $A, B, C, D$ are matrices. But then I realize that $A, B, C, D$ are unknown to me. So I hade to use a simplier example.

So let's assume that we have this system of equation:

$$b = Ax$$

Where we want to find $A$. What is the best way to find $A$ if $b$ and $x$ are known vectors?

Here is two options what I have found.

• Pseudo inverse: Using numerical linear algebra
• Backpropagation: Using gradient descent
• Estimation: Using a kalman filter

So what do you recommend here for me if I want to solve $A$ or in the other case, find $DCBA$ from $b = DCBAx$

Answer 1

My deleted answer did not address the question as correctly observed by @Winter.

---

Given two vectors $x$ and $b$, the objective is to construct a matrix $A$ such that $$Ax=b.$$

If $x=0$, then $Ax=0$ for any $A$ and we must have $b=0$ or the problem has no solution.

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

If $x\not=0$, then the matrix given by $$A=\frac{1}{\|x\|^2_2}bx^T$$ satisfies $$Ax = \frac{1}{\|x\|^2_2}bx^Tx = b.$$

There is a significant downside to this matrix $A$. It has rank 1, so it likely to break any software based on Gaussian elimination.

To make further progress we turn to the singular value decomposition and write a general matrix $A$ as $$ A = \sum_{j=0}^m \sigma_j v_j u_j^T$$ We want to choose the singular value and the singular vectors such that $$Ax=b$$ and $A$ will not break software based on Gaussian elimination.

Again if $x=0$, then we must have $b = 0$ and $A=I$ will work.

If $x \not = 0$, then we consider $b$ as follows.

If $b = 0$, then any acceptable $A$ will be singular and it should break software based on Gaussian elimination.

If $b \not =0$, then we set $u_1 = x/\|x\|_2$ and extend $u_1$ to an orthogonal matrix $U$ using Gram-Schmidt's method. We set $v_1 = b/\|b\|_2$ and extend $v_1$ to an orthogonal matrix $V$ using Gram-Schmidt's method. Then $$Ax = \sum_{j=0}^m \sigma_j v_j u_j^T x = \sigma_1 v_1 u_1^Tx = \sigma_1 \frac{b}{\|b\|_2} \frac{x^Tx}{\|x\|_2}$$ It follows that we should choose $\sigma_1 = \frac{\|b\|_2}{\|x\|_2}$. We are free to choose the remaining $\sigma_j$. The choice of $$ \sigma_j = \frac{\|b\|_2}{\|x\|_2}$$ is attractive because it ensures that the test matrix is well-conditioned. On the other hand we have the freedom to ensure that matrix $A$ is arbitrarily ill-conditioned.

Answer 2

As it is stated, the problem may not even have a solution. If $x_1=x_2 = \cdots =x_n = 0$, the problem only has a solution if $b_1=b_2= \cdots b_n = 0$ (in that case you can just take any matrix $A$.

In the opposite corner, if $x_i \ne 0, i= 1,\cdots, n$, you can take $A$ as a diagonal matrix with entries $a_{ii} = \frac{b_i}{x_i}$.

A general intermediate situation would correspond (after reordering) to have $x_1, \cdots , x_k \ne 0$ and $x_{k+1}= \cdots = x_n =0$. In this scenario, the first $k$ lines of $A$ can correspond to the diagonal matrix mentioned before. The entries $a_{ij}, i \ge k, j\ge n-k$ become arbitrary (set them to zero!) and you end up with the problem of determining the entries $a_{ij}$ with $i\ge k$ and $j \leq k$. So, the missing entries satisfy $$ \begin{cases} a_{k+1,1}x_1 + \cdots a_{k+1,n}x_k = b_{k+1}\\ \vdots\\ a_{n,1}x_1 + \cdots a_{n,k} x_k = b_n \end{cases} $$

A possible choice could be setting $a_{i,1} = \frac{b_i}{x_1}, i \ge k+1$ and let the rest be zero.

This leads to the block matrix $$ A = \begin{bmatrix}A_1 & 0\\ A_2 & 0 \end{bmatrix}, $$

where $$ A_1 = \textrm{diag}(\frac{b_1}{x_1}, \cdots, \frac{b_k}{x_k}) $$

and $$ A_2 = \begin{bmatrix} \frac{b_{k+1}}{x_1} & 0 & \cdots & 0 \\ \vdots & & \ddots\\ \frac{b_n}{x_1} & 0 & \cdots & 0 \end{bmatrix} $$

If the non-zero entries of $x$ are not in the beginning of the vector, we start by computing $A_p$ such that $A_P Px = Pb$, where $Px$ has the non zero entries in the beginning. In this case the final answer would be $A = P^{-1}A_P P$.