# Methods to solve a system of many Ax=B equations using least-squares

I am working with a force measurement instrument which needs calibration via a calibration matrix. For each of a set of controlled measurements I have a vector $k$ of three known, independent values, and a corresponding vector $m$ containing three measured values, that due to instrument constraints end up being non-orthogonal.

From each measurement, I can assemble an equation in the form

$Cm = k$

where $C$ is a 3x3 calibration matrix for that measurement, found by solving the system.

My goal is to find some calibration matrix that is the least-squares best fit for ALL the measurements in the set of measurements. That would mean I would have a system like:

$Cm_1 = k_1\\ Cm_2 = k_2\\ ...\\ Cm_n = k_n$

that I would have to solve for C, and that is my question: how do I solve such a system, where I have a MATRIX as the unknown?

I am not familiar with heavy math notation, and I plan to solve this using Python (Numpy/Scipy), so I'm looking more for a theoretical basis and proper nomenclature of which kind of procedure I should use, and then I could figure out how to implement it numerically.

Any help is much appreciated, thanks for reading!

-
Should $C_1,\ldots, C_n$ all just be $C$? –  littleO Nov 7 '12 at 12:44
You're right, I corrected the question. –  heltonbiker Nov 7 '12 at 12:46

Let's denote $C$ as $C = \begin{pmatrix} c_{11} & c_{12} & c_{13}\\ c_{21} & c_{22} & c_{23} \\ c_{31} & c_{32} & c_{33} \end{pmatrix}$ We can write the equation $Cm_i = k_i$ as \begin{align*} m_{i1} c_{11} + m_{i2}c_{12} + m_{i3} c_{13} &= k_{i1}\\ m_{i1} c_{21} + m_{i2}c_{22} + m_{i3} c_{23} &= k_{i2}\\ m_{i1} c_{31} + m_{i2}c_{32} + m_{i3} c_{33} &= k_{i3} \end{align*} or $$\begin{pmatrix} m_{i1} & m_{i2} & m_{i3} & 0 & 0 &0 & 0 & 0 &0\\ 0 & 0 & 0 & m_{i1} & m_{i2} & m_{i3} & 0 & 0 & 0\\ 0 & 0 &0 & 0 & 0 &0 & m_{i1} & m_{i2} & m_{i3}\end{pmatrix} \begin{pmatrix} c_{11} \\ c_{12}\\c_{13}\\ c_{21} \\ c_{22} \\ c_{23} \\ c_{31} \\ c_{32} \\c_{33} \end{pmatrix} = \begin{pmatrix} k_{i1} \\ k_{i2} \\ k_{i3}\end{pmatrix}$$ Doing this for all $i$ gives $$\begin{pmatrix} m_{11} & m_{12} & m_{13} & 0 & 0 &0 & 0 & 0 &0\\ 0 & 0 & 0 & m_{11} & m_{12} & m_{13} & 0 & 0 & 0\\ 0 & 0 &0 & 0 & 0 &0 & m_{11} & m_{12} & m_{13}\\ & \vdots & &&&&& \vdots \\ m_{n1} & m_{n2} & m_{n3} & 0 & 0 &0 & 0 & 0 &0\\ 0 & 0 & 0 & m_{n1} & m_{n2} & m_{n3} & 0 & 0 & 0\\ 0 & 0 &0 & 0 & 0 &0 & m_{n1} & m_{n2} & m_{n3}\end{pmatrix} \begin{pmatrix} c_{11} \\ c_{12}\\c_{13}\\ c_{21} \\ c_{22} \\ c_{23} \\ c_{31} \\ c_{32} \\c_{33} \end{pmatrix} = \begin{pmatrix} k_{11} \\ k_{12} \\ k_{13} \\ \vdots \\ k_{n1} \\ k_{n2} \\ k_{n3}\end{pmatrix}$$ Now apply your usual least squares method.

-
Amazing! Very clear answer. You solved me a big problem. Thanks very much! –  heltonbiker Nov 7 '12 at 12:55
Note that these equations decouple into three separate overdetermined systems. –  littleO Nov 7 '12 at 13:04
In case someone is interested in a Python (scipy) literal implementation of this answer, it is here: stackoverflow.com/a/13292441/401828 –  heltonbiker Nov 8 '12 at 15:47

Let's write $k_j$ as $k_j = \begin{bmatrix} k_j^1 \\ k_j^2 \\ k_j^3 \end{bmatrix}$.

Let the rows of $C$ be $c_1^T,c_2^T$, and $c_3^T$, so that $C = \begin{bmatrix} c_1^T \\ c_2^T \\c_3 ^T \end{bmatrix}$. Each measurement gives you three equations:

\begin{align*} c_1^T m_j &= k_j^1 \\ c_2^T m_j &= k_j^2 \\ c_3^T m_j &= k_j^3. \end{align*} which can equally well be written as \begin{align*} m_j^T c_1 &= k_j^1 \\ m_j^T c_2 &= k_j^2 \\ m_j^T c_3 &= k_j^3. \end{align*}

Let $$A = \begin{bmatrix} m_1^T \\ m_2^T \\ \vdots \\ m_n^T \end{bmatrix}.$$

Let $$k^1 = \begin{bmatrix} k_1^1 \\ k_2^1 \\ \vdots \\ k_n^1 \end{bmatrix}$$ and let $k^2$ and $k^3$ be defined similarly.

Then we have three separate overdetermined systems of equations: \begin{align*} A c_1 &= k^1 \\ A c_2 &= k^2 \\ A c_3 &= k^3 . \end{align*}

Each of these overdetermined systems can be solved by least squares. For example, in Matlab we could use \begin{align*} c_1 &= A \backslash k^1 \\ c_2 &= A \backslash k^2 \\ c_3 &= A \backslash k^3 \end{align*} (Here I'm using Matlab's backslash operator, which finds leasts squares solutions to overdetermined systems efficiently.)

-
I appreciate this answer, but the notation is a bit more fuzzy to get along. Since the number of measurements probably is not so large, perhaps the speed penalty of having one big system instead of three separate, decoupled ones, is not so severe. Anyway, if speed becomes a problem, I'll come back to this answer. Thank you very much for your time and interest! –  heltonbiker Nov 7 '12 at 13:06