Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a Image processing application in which I have a Matrix equation as below:

A*R=I

where,

A = 3x3 matrix (Constants)

R = 3x1 matrix (Column Vector) Lets call this as actual output.

I = 3x1 matrix . Lets call I as Ideal output

* denotes matrix multiplication.

I know the values of matrix I, and R. I have to find what matrix A, if post multiplied by R would give me matrix I

How can I set his situation up in matrix algebra and solve it compute A?

Any pointers would be helpful.

Thank You.

-AD.

share|improve this question
5  
Do you have multiple pairs of values for $R$ and $I$ at your disposal? If you have only one pair of values, then there are many possibility for $A$. –  Rasmus Aug 16 '10 at 16:41
    
@Rasmus: Technically i have 24 sets of values for I and R, My ideal situation would be if i find one such A for one set of value of I and R, i can assume it would work for all remaining sets. But for simplicity if i assume there is only one set of I and R, then how would u suggest i proceed? –  goldenmean Aug 16 '10 at 16:48
add comment

5 Answers

Actually if you have 24 sets of I and R:

$$ \mathsf A \cdot \mathbf R_i = \mathbf I_i \qquad i = 1, 2, \dotsc, 24 $$

since there are only 9 variables for each element of A but 24×3 = 72 linear equations, the problem is overdetermined and there may be no solutions. However, if you accept some errors ε,

$$ \mathsf A \cdot \mathbf R_i + \boldsymbol \epsilon_i = \mathbf I_i \qquad i = 1, 2, \dotsc, 24 $$

It is possible to find such an A, as this introduces 72 more variables (the problem becomes underdetermined). The best thing is of course to minimize the total error. We first write A as a column of row vectors:

$$ \mathsf A = \begin{bmatrix} \mathbf A_1 \\ \mathbf A_2 \\ \mathbf A_3 \end{bmatrix} $$

then we have

$$ \mathbf R_i \cdot \mathbf A_j + \epsilon_{ij} = I_{ij} \qquad i = 1, \dotsc, 24; j = 1, 2, 3 $$

this is exactly like a linear regression problem (if we minimize the sum of squares of errors)

$$ \mathsf X \cdot \boldsymbol \beta_j + \boldsymbol \epsilon_j = \mathbf y_j $$

with

\begin{align} \mathsf X &= \begin{bmatrix} R_{1,1} & R_{1,2} & R_{1,3} \\ \vdots & \vdots & \vdots \\ R_{24,1} & R_{24,2} & R_{24,3} \end{bmatrix} \\ \boldsymbol\beta_j &= \begin{bmatrix} A_{j,1} \\ A_{j,2} \\ A_{j,3} \end{bmatrix} \\ \mathbf y_j &= \begin{bmatrix} I_{1,j} \\ \vdots \\ I_{24,j} \end{bmatrix} \end{align}

With these we can use any software supporting regression (or by hand) to find the best approximation of Aj, and thus the whole matrix A.

(This can be easily generalized to $N \gg 24$ pixels.)

share|improve this answer
    
KennyTM: please excuse me: could you check whether you mean A$\cdot \mathbf{R}_{i}=\mathbf{I}_{i}$ instead of A$\cdot \mathbf{I}_{i}=\mathbf{R}_{i}$? (To use the same notation as in the question) –  Américo Tavares Aug 16 '10 at 18:35
    
@Américo: Fixed. Thanks! –  KennyTM Aug 16 '10 at 18:47
add comment

Given some $A$, you can measure how well it performs on the ensemble of $R_1,...,R_{24}$ and $I_1,...,I_{24}$ by computing the error. For example: $$ J = \sum_{i=1}^{24} ||A R_i - I_i ||^2 $$ Where we have used the standard Euclidean norm. The goal is to find the $A$ that makes $J$ as small as possible. We can express this more compactly by stacking the vectors $R_i$ and $I_i$ into larger 3x24 matrices. So if we let: $R = [R_1 R_2 \dots R_{24}]$ and similarly for $I$, we can rewrite our error as: $$ J = ||AR - I||_F^2 $$ where we are now using the Frobenius norm. This optimization problem can be solved in many different ways. For example, you can differentiate J with respect to A and set the result equal to zero. This yields the optimality condition: $$ ARR^T = IR^T $$ So any A that satisfies the above equation will be optimal in the sense that it will minimize J. If R is a full-rank matrix (likely), then the optimal A is given by: $$ A = IR^T(RR^T)^{-1} $$

share|improve this answer
    
+1 and just a tiny algorithmic note on this: instead of computing $RR^T$ directly and inverting (which can result in loss of significant figures), what you might do instead is to perform a QR decomposition $R^T=QS$ (here, to avoid confusion, I denote the upper triangular factor by S instead of the traditional R). You now have the Cholesky decomposition of $RR^T=S^T S$, which you can now use for computing A. –  J. M. Aug 22 '10 at 10:01
add comment

As Rasmus said, if you have only one (I,R) pair, then there are multiple possibilities for A.

If you are interested in any one such A, you can use the following.

Let $R = (x,y,z)$ and assume that $x \neq 0$

Let $I = (a,b,c)$

You can choose the matrix to be

[a/x 0 0]
[b/x 0 0]
[c/x 0 0]
share|improve this answer
    
@Moron: Sorry, to understand clearly your reply, what is $ notation in your reply? –  goldenmean Aug 16 '10 at 16:54
    
The dollar sign is used for displaying math formulas. =) Hold shift and click refresh. –  Rasmus Aug 16 '10 at 17:03
    
@Moron: I see what u replied. Did u mean [a/x 0 0] [0 b/x 0] [0 0 c/x] –  goldenmean Aug 16 '10 at 17:04
1  
@goldenmean: No. I meant what I wrote. Try multiplying that matrix by (x,y,z) and see what you get. –  Aryabhata Aug 16 '10 at 17:10
1  
@golden: They you have 9 variables and 24*3 linear equations in those variables, which might or might not have solutions. Basically, it depends on the data you have. –  Aryabhata Aug 16 '10 at 17:20
show 1 more comment

Let $a_{ij}$ be the number in $i$-th row and $j$-th column in the matrix $A$. Then each equation of the form $AR=I$ is basicly three linear equations with unknowns $a_{ij}$. If there are 24 sets then you have $24 \cdot 3$ linear equations in $9$ unknowns. This system might have no solution in general. But, you can use Linear least squares to find a solution that fits best all those equations.

share|improve this answer
add comment

FIRST CASE. If you had only one set of values for $I$ and $R$, as you said in your answer to Rasmus, then you'd have a system of linear equations with infinitely many solutions.

For psychological reasons, let's write it this way:

$$ XA = B \ . $$

Here $A$ is your $R$, $B$ your $I$ and $X$ your $A$. If we transpose we get a simultaneous system of linear equations

$$ A^t X^t = B^t \ . $$

If $A^t = (a_1 \ a_2 \ a_3)$ and $B^t = (b_1 \ b_2 \ b_3)$, and $(x_i \ y_i \ z_i)$ is the i-th colum $X^t$, we have the linear equations

$$ a_1 x_i + a_2 y_i + a_3 z_i = b_i $$

for $i = 1, 2, 3$.

Which, assuming $a_1 \neq 0$, you can solve like this:

$$ x_i = \frac{b_i}{a_1} - \frac{a_2}{a_1} y_i - \frac{a_3}{a_1} z_i \ . $$

Now, give $y_i$ and $z_i$ the values you want and you have a solution for your problem.

EDIT: Maybe I could develop a little bit more my answer, in order to really include your problem, which is one of overdeterminated simultaneous systems of linear equations, as KennyTM says, since you don't have a prefered pair of values $(R,I)$, do you? In order to handle all the $24$ pairs of values $(R,I)$ you have, maybe you should take into account this SECOND CASE.

SECOND CASE. I'm sorry, but I'm changing slightly the notation again. In the end, I'll write the solution with yours.

Let

$$ AX = B $$

be a (simultaneous) system of linear equations such as yours, with $A$ a $24\times 3$ matrix ($24$ rows, $3$ columns), $X$ a $3\times 3$ matrix and $B$ a $24 \times 3$ matrix.

*Hypothesis: Let's assume that our matrix $A$ (that is, your $R$) has rang $ 3$. *

(If this is not the case, the problem is more involved.)

Let's write the first system this way:

$$ x_1a_1 + y_1a_2 + z_1a_3 = b_1 \ . \qquad [1] $$

Here, $a_i , i = 1,2,3$ are the columns of $A$, $X_1 = \begin{pmatrix} x_1 & y_1 & z_1 \end{pmatrix}^t$ the first column of $X$ and also $b_1$ is the first column of $B$.

So we see in one go a geometrical interpretation of our system of equations: system [1] has a solution $\begin{pmatrix} x_1 & y_1 & z_1 \end{pmatrix}$ if and only if the vector $b_1$ belongs to the linear span generated by the columns of $A$:

$$ AX_1 = b_1 \quad \text{has a solution} \qquad \Longleftrightarrow \qquad b_1 \in [a_1, a_2, a_3] $$

What can we do if this is not the case? -To look for the nearest vector in $[a_1, a_2, a_3]$ to $b_1$.

This nearest vector is, of course, the orthogonal projection of $b_1$ onto the subspace $[a_1, a_2, a_3] $.

According to Wikipedia, http://en.wikipedia.org/wiki/Orthogonal_projection , the matrix of this orthogonal projection in the standard basis of $\mathbb{R}^{24}$ is

$$ P_A = A (A^tA)^{-1}A^t \ . $$

So the best $X = \begin{pmatrix} X_1 & X_2 & X_3\end{pmatrix}$ for you is

$$ X = A (A^tA)^{-1}A^tB $$

where $B = \begin{pmatrix} b_1 & b_2 & b_3 \end{pmatrix}$. Now, let's go back to your notation: $A = X^t$, $R = A^t$ and $I = B^t$. So

$$ A = \left( R^t (R^{tt}R^t)^{-1}R^{tt}I^t \right)^t = I R^t ((RR^t)^{-1})^t R $$

where $R$ and $I$ are now the matrices with all of your $R$'s and $I$'s as columns.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.