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

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.

• Since you're using QR, are you doing least-squares fitting? – Geoff Oxberry May 9 '15 at 8:00
• How would you quantify whether $A$ has an optimum value or not? Do you have any idea what $b_n$ should look like? – fibonatic May 9 '15 at 9:01
• Why do you need QR to solve for $b_n$, can't you just multiply? – Bill Barth May 9 '15 at 13:12
• I am doing least squares as the values aren't going be exact and I am trying to derive the "best" A coefficients for a whole set of data points. I need the best fit since these are sensor readings and not the real, independent values that I would like to extract, but don't know if A has an optimum value or more than one. Bill, you are probably might be right that straight multiplication would work for this portion. My biggest problems is really getting that "best" A matrix such that I can tease out the actual values from my readings. – Jason K. May 9 '15 at 14:53
• The title and the question say two different things. It would be useful if you edited and specified clearly what is given and what is an unknown. Also, what are the matrix sizes? Are they related to $n$? And please avoid the term "series", in mathematics it means something else and it can be confusing. – Federico Poloni May 11 '15 at 19:30

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

 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/

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

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

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

• This does look like the sort of thing I need. I am going to try it out and get back. If you know of some implementations, please let me know. – Jason K. May 9 '15 at 14:59
• Thanks for these. I also found and have added some. I have a few to try out. Many thanks. – Jason K. May 9 '15 at 16:01
• Answer accepted. (It was the first one I accepted so wasn't sure what I was looking for at first) – Jason K. May 9 '15 at 16:35

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.