Algorithm for optimizing Ax = b with unknown A and known x values

Question

I would like to solve for the optimum $A$ values for a series of matrix equations $Ax_{1} = b_{1}, Ax_{2} = b_{2} ... Ax_{n} = b_{n}$ where only the $x$ values are known and when I start with an intelligent guess for $A$. I am using QR decomposition to solve the individual matrix equations for $b$, but wondering how to go about optimizing $A$ values as I don't have a real $b$ value to use in defining some error metric to use for convergence.

The nature of the problem is that $x$ is a set of sensor values and $A$ represents a set of constant coefficients defining to what degree the value at an adjacent sensor affects the measured values of $x$. The $b$ values should be the actual values without superposition from other sensors.

Any suggestions on tackling this would be appreciated.

Answer 1

Your problem sounds like Independent Component Analysis. Where $x_i$ are the measurements in which the source signals have got mixed and $b_i$ are the values emitted by the sources. The $A$ in your equations is called the unmixing matrix. There is an iterative procedure to estimate $A$ and hence, the $b_i$s, based on the maximum likelihood principle. Refer to these notes:

Andrew Ng's notes on ICA

[Edit] FastICA looks like a popular implementation:

http://research.ics.aalto.fi/ica/fastica/

http://itpp.sourceforge.net/4.3.0/fastica_8cpp.html

http://tumic.wz.cz/fel/online/libICA/

[Edit] The OP (Jason) also found these for future reference:

https://github.com/cgearhart/students-filters/

http://sourceforge.net/projects/fastica/

http://shulgadim.blogspot.ca/2014/02/independent-component-analysis-ica.html

Answer 2

Reformulate your set of equations such that the coefficients are the unknowns and perform least square fitting on A.

This can be done by the following trick:

Be $x$ a column vector $(n\times 1)$, $A$ the unknown matrix $(n\times n)$, you know that $Ax =b \Rightarrow \sum_j a_{ij} x_j = b_i$ but this can also be seen as $\hat X\, \textrm{Vec}(A)= b$ where $\textrm{Vec}(A)$ is the vectorization operator and $\hat X$ must be n-times repeated and shifted by n $x^T$ or $0^T$ otherwise, leading to $\Rightarrow \hat X=x^T\otimes I_n $, where $I_n$ is the identity matrix of dimension n.

For the full system you can rewrite it as following, set $X=(x_1,...,x_n)$ and $B=(b_1,...,b_n)$ of your original equations $A X = B$, your least square problem for $A$ reads $(X^T\otimes I_n)\textrm{Vec}(A)=\textrm{Vec}(B)$.

So it all boils down if you have enough matrix equations whether this will be an over or undertemined system and can be directly solved by standard numerical techniques.