Finding the matrix that transforms a given input vector into a given output vector

Question

I have two vectors - the input and output. I would like to find a matrix that multiplied by the input vector gives the output vector.

What algorithms should be used? What is their complexity?

Answer 1

So you want a matrix, which given the input vector $a$ produces the output vector $b$.

Here is a rank-1 matrix which does that $$M=\frac{ba^T}{a^Ta}=ba^+$$ where $a^+$ is the pseudoinverse of $a$.

Later, you discover that you actually need to map a set of input vectors $\{a_k\}$ to a set of output vectors $\{b_k\}.\,\,\,$ Here is a matrix which addresses that situation $$M=BA^+$$ where $B$ is a matrix whose columns are the $\{b_k\}$ vectors, and ditto for $A$.

For a more complete solution, you can include contributions from the nullspace of $A$ $$M=BA^+ + G\,(I-AA^+)$$ where $G$ is an arbitrary matrix.

This solution remains valid when $A$ reverts to being the vector $a$, and is likely the answer to your original question.

Answer 2

Given an input $\mathrm a \in \mathbb R^n$ and an output $\mathrm b \in \mathbb R^m$, we would like to find $\mathrm X \in \mathbb R^{m \times n}$ such that

$$\mathrm X \mathrm a = \mathrm b$$

Vectorizing both sides, we obtain a linear system of $m$ equations in $m n$ unknowns

$$(\mathrm a^{\top} \otimes \mathrm I_m) \, \mbox{vec} (\mathrm X) = \mathrm b$$

Since this system is underdetermined when $n > 1$, there are infinitely many solutions. Let us look for the solution with the least Frobenius norm

$$\begin{array}{ll} \text{minimize} & \| \mathrm X \|_{\text{F}}^2\\ \text{subject to} & \mathrm X \mathrm a = \mathrm b\end{array}$$

We define the Lagrangian

$$\mathcal L (\mathrm x, \lambda) := \frac 12 \| \mathrm X \|_{\text{F}}^2 - \lambda^{\top} \left( \mathrm X \mathrm a - \mathrm b \right)$$

Taking partial derivatives and finding where they vanish, we obtain

$$\mathrm X = \lambda \mathrm a^{\top} \qquad \qquad \qquad \mathrm X \mathrm a = \mathrm b$$

Right-multiplying both sides of $\mathrm X = \lambda \mathrm a^{\top}$ by vector $\mathrm a$, we obtain

$$\lambda = \frac{\mathrm b \,\,}{\| \mathrm a \|_2^2}$$

and, thus, the least-norm solution is

$$\boxed{\mathrm X^* := \dfrac{\,\,\mathrm b \mathrm a^{\top}}{\| \mathrm a \|_2^2}}$$