1
$\begingroup$

If $v$ is a row vector and $A$ a matrix, the product $w = v A$ can be seen as a vector containing a number of linear combinations of the columns of vector $v$. For instance, if $$ v = \begin{bmatrix}1, 2\end{bmatrix}, \quad A = \begin{bmatrix}0 & 0 & 0 \\ 1 & 1 & 1\end{bmatrix}, \quad w = vA = \begin{bmatrix}2, 2, 2\end{bmatrix} $$ read by columns, the matrix $A$ is saying: make 3 combinations of the columns of vector $v$, each of which consists of taking 0 times the first column and 1 time the second column.

Now, the goal is to reconstruct, to the extent of possible, vector $v$ from $A$ and $w$, in other words to find a vector $v'$ such that $$v'A = w .$$

Two things to consider:

  • The matrix $A$ can have any number of columns and may or may not be square or invertible.

  • There are times when elements of the original vector can't be known, because $w$ contains no information about them. In the previous example, this would be the case of $v_1$. In this case, we would accept any value of $v'_1$ as correct.

How would you approach this problem? Can $v'$ be found doing simple operations with $w$ and $A$ or do I have to invent an algorithm specifically for the purpose?

  • 0
    Least squares? Side remark: Is there any particular reason you are using row vectors?2012-11-04
  • 0
    Least squares does indeed work, but not always because $A^{T}A$ may be singular. There is no particular reason I'm using row vectors.2012-11-04
  • 0
    Well, not just least squares, but something like the Moore-Penrose pseudoinverse. (Probably not computationally efficient.)2012-11-04

1 Answers 1

2

Given $A$ and $b$, you are trying to solve for $x$ in $xA=b$. This is just solving a system of linear equations, and the usual methods apply. Well, usually the problem is presented as $Ax=b$, but that just means instead of doing elementary row operations you'll be doing elementary column operations. Or, you could take the transpose and solve $A^tx^t=b^t$, and then you'd be back in line with the rest of us.

  • 0
    The OP wants to know what to do when $A$ isn't invertible.2012-11-04
  • 0
    @wj32 Solving a system doesn't require $A$ to be invertible.2012-11-04
  • 0
    @wj32, yes --- what's your point? The usual methods for solving $Ax=b$ (that is, reduction to row echelon form) do not rely on $A$ being invertible, or even square.2012-11-04
  • 0
    To me the question seemed to indicate some kind of approximation was desired if there is no solution. Well, maybe that's just my strange interpretation...2012-11-04
  • 0
    @GerryMyerson Sorry for using an nonstandard presentation for the problem. So, basically I have to solve a system of equation with potentially redundant equations.2012-11-04
  • 0
    @wj32, my apologies, I think you're right. The example in the post leads to 3 equations in 2 unknowns. If there is an exact solution, column reduction will get you there, but if column reduction shows there is no exact solution, then we're talking about least squares (or some refinement thereof).2012-11-04