Mixing
Invert a $4 times 4$ matrix with a given structure?
$begingroup$
When tryig to fit $f(x,y) = a+bx+cy+dxy$ to the values of four points, we will have to invert following matrix. (Let us assume that $x_i,y_i$ are chosen suitably such that it is regular.) We could obviously solve this with any method (LU etc), but does the special structure of this matrix maybe allow for a compact representation of its inverse?
I thought there might be a way because this matrix looks similar to a Vandermonde matrix (but it is obviously not the same), which do sometimes have inverses that are particularly easy to compute.
$$M=begin{bmatrix}
1 & x_1 & y_1 & x_1 y_1\
1 & x_2 & y_2 & x_2 y_2\
1 & x_3 & y_3 & x_3 y_3\
1 & x_4 & y_4 & x_4 y_4end{bmatrix}$$
linear-algebra matrices inverse matrix-decomposition
edited Jan 7 at 23:41
user1101010
7851730
asked Jan 2 at 19:22
flawrflawr
11.3k32445
$endgroup$
add a comment |
$begingroup$
When tryig to fit $f(x,y) = a+bx+cy+dxy$ to the values of four points, we will have to invert following matrix. (Let us assume that $x_i,y_i$ are chosen suitably such that it is regular.) We could obviously solve this with any method (LU etc), but does the special structure of this matrix maybe allow for a compact representation of its inverse?
I thought there might be a way because this matrix looks similar to a Vandermonde matrix (but it is obviously not the same), which do sometimes have inverses that are particularly easy to compute.
$$M=begin{bmatrix}
1 & x_1 & y_1 & x_1 y_1\
1 & x_2 & y_2 & x_2 y_2\
1 & x_3 & y_3 & x_3 y_3\
1 & x_4 & y_4 & x_4 y_4end{bmatrix}$$
linear-algebra matrices inverse matrix-decomposition
edited Jan 7 at 23:41
user1101010
7851730
asked Jan 2 at 19:22
flawrflawr
11.3k32445
$endgroup$
$begingroup$
This is bilinear interpolation.
$endgroup$
– hardmath
Jan 7 at 22:36
$begingroup$
@hardmath Yes, but unfortunately WP also only shows the cases of an unit square and an axes-aligned rectangle.
$endgroup$
– flawr
Jan 7 at 23:07
$begingroup$
I take your points! A more general solution can be found if the four points are an affine image of corners of the unit square. For some four points the determinant vanishes and no matrix inverse exists. I'll add a note.
$endgroup$
– hardmath
Jan 7 at 23:34
$begingroup$
@hardmath The affine image of a rectangle is a parallelogram; thus we still haven't an answer for the general case where the 4 points can be any set of four points.
$endgroup$
– Jean Marie
Jan 8 at 5:55
add a comment |
$begingroup$
When tryig to fit $f(x,y) = a+bx+cy+dxy$ to the values of four points, we will have to invert following matrix. (Let us assume that $x_i,y_i$ are chosen suitably such that it is regular.) We could obviously solve this with any method (LU etc), but does the special structure of this matrix maybe allow for a compact representation of its inverse?
I thought there might be a way because this matrix looks similar to a Vandermonde matrix (but it is obviously not the same), which do sometimes have inverses that are particularly easy to compute.
$$M=begin{bmatrix}
1 & x_1 & y_1 & x_1 y_1\
1 & x_2 & y_2 & x_2 y_2\
1 & x_3 & y_3 & x_3 y_3\
1 & x_4 & y_4 & x_4 y_4end{bmatrix}$$
linear-algebra matrices inverse matrix-decomposition
edited Jan 7 at 23:41
user1101010
7851730
asked Jan 2 at 19:22
flawrflawr
11.3k32445
$endgroup$
When tryig to fit $f(x,y) = a+bx+cy+dxy$ to the values of four points, we will have to invert following matrix. (Let us assume that $x_i,y_i$ are chosen suitably such that it is regular.) We could obviously solve this with any method (LU etc), but does the special structure of this matrix maybe allow for a compact representation of its inverse?
I thought there might be a way because this matrix looks similar to a Vandermonde matrix (but it is obviously not the same), which do sometimes have inverses that are particularly easy to compute.
$$M=begin{bmatrix}
1 & x_1 & y_1 & x_1 y_1\
1 & x_2 & y_2 & x_2 y_2\
1 & x_3 & y_3 & x_3 y_3\
1 & x_4 & y_4 & x_4 y_4end{bmatrix}$$
linear-algebra matrices inverse matrix-decomposition
linear-algebra matrices inverse matrix-decomposition
edited Jan 7 at 23:41
user1101010
7851730
asked Jan 2 at 19:22
flawrflawr
11.3k32445
edited Jan 7 at 23:41
user1101010
7851730
asked Jan 2 at 19:22
flawrflawr
11.3k32445
edited Jan 7 at 23:41
user1101010
7851730
edited Jan 7 at 23:41
user1101010
7851730
edited Jan 7 at 23:41
user1101010
7851730
7851730
asked Jan 2 at 19:22
flawrflawr
11.3k32445
asked Jan 2 at 19:22
flawrflawr
11.3k32445
asked Jan 2 at 19:22
flawrflawr
11.3k32445
11.3k32445
$begingroup$
This is bilinear interpolation.
$endgroup$
– hardmath
Jan 7 at 22:36
$begingroup$
@hardmath Yes, but unfortunately WP also only shows the cases of an unit square and an axes-aligned rectangle.
$endgroup$
– flawr
Jan 7 at 23:07
$begingroup$
I take your points! A more general solution can be found if the four points are an affine image of corners of the unit square. For some four points the determinant vanishes and no matrix inverse exists. I'll add a note.
$endgroup$
– hardmath
Jan 7 at 23:34
$begingroup$
@hardmath The affine image of a rectangle is a parallelogram; thus we still haven't an answer for the general case where the 4 points can be any set of four points.
$endgroup$
– Jean Marie
Jan 8 at 5:55
add a comment |
$begingroup$
This is bilinear interpolation.
$endgroup$
– hardmath
Jan 7 at 22:36
$begingroup$
@hardmath Yes, but unfortunately WP also only shows the cases of an unit square and an axes-aligned rectangle.
$endgroup$
– flawr
Jan 7 at 23:07
$begingroup$
I take your points! A more general solution can be found if the four points are an affine image of corners of the unit square. For some four points the determinant vanishes and no matrix inverse exists. I'll add a note.
$endgroup$
– hardmath
Jan 7 at 23:34
$begingroup$
@hardmath The affine image of a rectangle is a parallelogram; thus we still haven't an answer for the general case where the 4 points can be any set of four points.
$endgroup$
– Jean Marie
Jan 8 at 5:55
$begingroup$
This is bilinear interpolation.
$endgroup$
– hardmath
Jan 7 at 22:36
$begingroup$
This is bilinear interpolation.
$endgroup$
– hardmath
Jan 7 at 22:36
$begingroup$
@hardmath Yes, but unfortunately WP also only shows the cases of an unit square and an axes-aligned rectangle.
$endgroup$
– flawr
Jan 7 at 23:07
$begingroup$
@hardmath Yes, but unfortunately WP also only shows the cases of an unit square and an axes-aligned rectangle.
$endgroup$
– flawr
Jan 7 at 23:07
$begingroup$
I take your points! A more general solution can be found if the four points are an affine image of corners of the unit square. For some four points the determinant vanishes and no matrix inverse exists. I'll add a note.
$endgroup$
– hardmath
Jan 7 at 23:34
$begingroup$
I take your points! A more general solution can be found if the four points are an affine image of corners of the unit square. For some four points the determinant vanishes and no matrix inverse exists. I'll add a note.
$endgroup$
– hardmath
Jan 7 at 23:34
$begingroup$
@hardmath The affine image of a rectangle is a parallelogram; thus we still haven't an answer for the general case where the 4 points can be any set of four points.
$endgroup$
– Jean Marie
Jan 8 at 5:55
$begingroup$
@hardmath The affine image of a rectangle is a parallelogram; thus we still haven't an answer for the general case where the 4 points can be any set of four points.
$endgroup$
– Jean Marie
Jan 8 at 5:55
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Obtaining coefficients $a, b, c, d$ of the surface (quadric) with equation
$$z=a+bx+cy+dxy$$
passing through 4 points doesn't necessitate to solve a system of equations or the inversion of a linear system. It can be obtained directly. Here is how (Meanwhile, we will deepen our understanding because, in this way, one will get the inverse matrix of the initial matrix) :
Let us take the simplified case where the four points are
$$(x,y) = (0,0), (1,0), (0,1), (1,1)$$
with prescribed values :
$$f(0,0)=p, f(1,0)=q, f(0,1)=r, f(1,1)=s. (1)$$
Let us consider the following expression : in it, each one of the 4 terms has a specialized "task" ensuring that the four constraints (1) are fulfilled :
$$
begin{equation}
z=left{begin{array}{llll}
p×& (1-x)(1-y) +... & text{ ``activated'' iff} x=0 & y=0\
q×& x(1-y) +... & text{ ``activated'' iff} x=1 & y=0\
r×& (1-x)y +... & text{ ``activated'' iff} x=0 & y=0\
s×& xy; & text{ ``activated'' iff} x=1 & y=1
end{array}right.
end{equation}
$$
Expanding all, we get :
$$z=p(1-x-y+xy)+q(x-xy)+r(y-xy)+sxy iff$$
$$z=underbrace{p}_{= a}+underbrace{(-p+q)}_{= b}x+underbrace{(-p+r)}_{= c}y+underbrace{(p-q-r+s)}_{= d}xy$$
or, with a matrix formulation :
$$begin{pmatrix}a\b\c\dend{pmatrix}=
begin{pmatrix}
1& 0& 0&0\
-1& 1& 0&0\
-1& 0& 1&0\
1&-1&-1&1
end{pmatrix}
begin{pmatrix}p\q\r\send{pmatrix}$$
which is not surprizing, being naturally the inverse of system
$$begin{pmatrix}p\q\r\send{pmatrix}=
begin{pmatrix}
1&x_1&y_1&x_1y_1\
1&x_2&y_2&x_2y_2\
1&x_3&y_3&x_3y_3\
1&x_4&y_4&x_4y_4\
end{pmatrix}
begin{pmatrix}a\b\c\dend{pmatrix} iff $$
(with $(x_1,y_1)=(0,0), (x_2,y_2)=(1,0), (x_3,y_3)=(0,1), (x_4,y_4)=(1,1))$
$$begin{pmatrix}p\q\r\send{pmatrix}=
begin{pmatrix}
1&0&0&0\
1&1&0&0\
1&0&1&0\
1&1&1&1
end{pmatrix}
begin{pmatrix}a\b\c\dend{pmatrix}.$$
Edit :
1) This method (called "bilinear interpolation" as noted by @hardmath) as the OP has make the remark provides an answer only in the case of points constituting a rectangle with sides parallel to the axes.
2) If we assume that the coordinates axes constitute an orthonormal basis, the determinant of the matrix given in the question can receive a geometrical interpretation when expanded along its fourth column :
$$-x_1y_1underbrace{begin{vmatrix}
1&x_2&y_2\
1&x_3&y_3\
1&x_4&y_4
end{vmatrix}}_{2 times text{area of} P_2P_3P_4} + x_2y_2underbrace{begin{vmatrix}
1&x_1&y_1\
1&x_3&y_3\
1&x_4&y_4
end{vmatrix}}_{2 times text{area of} P_1P_3P_4} + cdots$$
thus a weighted combination of (oriented) areas of the different triangles one can make with points $P_1, P_2, P_3, P_4$ the weights being the product of coordinates of these points.
As one can freely choose the coordinate axes, one can take axes with $P_1$ the origin, and axes with basis $overrightarrow{P_1P_2}, overrightarrow{P_1P_3}$ (under the condition that $P_1,P_2,P_3$ aren't aligned ; this is of course no longer an orthonormal basis in general!). Thus, the determinant reduces to :
$$x_4y_4begin{vmatrix}
1&x_1&y_1\
1&x_2&y_2\
1&x_3&y_3
end{vmatrix}$$
which is nonzero unless point $P_4$ is situated on one of the coordinate axes (i.e. aligned with $P_1$ and $P_2$ or aligned with $P_1$ and $P_3$).
answered Jan 7 at 22:04
Jean MarieJean Marie
29.4k42050
$endgroup$
2
$begingroup$
First of all, thank you for your extensive answer. I see how this simplified result can easily be extended to the case where the four points form an arbitrary rectangle that is aligned with the axes, by modifying the four constraints accordingly. For $(x,y) = (u,v),(u',v),(u',v'),(u,v')$ we'd get $z = ptimes (1-x/u)(1-y/v)+ q times x/u'(1-y/v) + ldots$, which we could expand in the same way as you did to get the coefficients. But I fail to see how this provides a solution (or inverse of the matrix) for the general case. Could you elaborate on that?
$endgroup$
– flawr
Jan 7 at 23:05
1
$begingroup$
I agree on the fact (as I just did in my comment to @hardmath) that bilinear interpolation doesn't cover the general case (when I gave my answer, I recognize that I had completely overlooked this aspect). I just computed the (formal) inverse of the general matrix you give : it is very complicated... I think to two ways to treat the general case : 1) the usage of projective geometry that can provide a correspondence between any quadrilateral and a rectangle or 2) the usage of B-splines that can provide a way analogous to bilinear interpolation, providing a way to specify a local influence
$endgroup$
– Jean Marie
Jan 8 at 6:15
$begingroup$
Similar questions are treated in the very interesting (rather old) book "Group-Theoretical Methods in Image Understanding" by Ken-ichi Kanatani (Springer, 1990)
$endgroup$
– Jean Marie
Jan 8 at 6:27
$begingroup$
I have added an edit to my answer.
$endgroup$
– Jean Marie
Jan 8 at 7:08
add a comment |
$begingroup$
Given four distinct points $(x_1,y_1),(x_2,y_2),(x_3,y_3),(x_4,y_4)$, we can exhibit the cases for which the matrix $M$ is invertible, and hence for which all the bilinear interpolation problems are uniquely solvable, by evaluating the determinant of $M$ as a quartic polynomial in the $x_i,y_i$.
It will simplify our work, and help to provide a geometric interpretation of the result, if we begin with a change of variable translating the first of these points to the origin:
$$ u = x - x_1 $$
$$ v = y - y_1 $$
Supposing that with the same function values at points $(u_i,v_i) = (x_i-x_1,y_i-y_1)$ as in the corresponding original points, a bilinear interpolant exists:
$$ g(u,v) = hat a + hat b u + hat c v + hat d uv $$
Then the solution to the original problem will be:
$$ begin{align*} f(x,y) &= hat a + hat b (x-x_1) + hat c (y-y_1) + hat d (x-x_1)(y-y_1) \
&= (hat a - hat b x_1 - hat c y_1 + hat d x_1 y_1) + (hat b - hat dy_1)x \
&; ; ; + (hat c - hat dx_1)y + hat d xy end{align*} $$
It follows that this solution would uniquely determine the desired bilinear interpolant $f(x,y)$ at the original points:
$$ begin{pmatrix} a \ b \ c \ d end{pmatrix}
= begin{pmatrix} 1 & -x_1 & -y_1 & x_1y_1 \
0 & 1 & 0 & -y_1 \
0 & 0 & 1 & -x_1 \
0 & 0 & 0 & 1 end{pmatrix}
begin{pmatrix} hat a \ hat b \ hat c \ hat d end{pmatrix} $$
In that sense we can assume without loss of generality that $(x_1,y_1) = (0,0)$, and we proceed to find the determinant of $M$ in this slightly special case:
$$ begin{align*} det M &= left| begin{array}{cccc}
1 & 0 & 0 & 0 \
1 & x_2 & y_2 & x_2 y_2 \
1 & x_3 & y_3 & x_3 y_3 \
1 & x_4 & y_4 & x_4 y_4 end{array} right| \
&= left| begin{array}{ccc}
x_2 & y_2 & x_2 y_2 \
x_3 & y_3 & x_3 y_3 \
x_4 & y_4 & x_4 y_4 end{array} right| \
&= x_2x_4y_3(y_4-y_2) + x_3x_4y_2(y_3-y_4) + x_2x_3y_4(y_2-y_3)
end{align*} $$
With this expression we can identify some geometric conditions on the four points for which the matrix has zero determinant and is thus not invertible. One such case is for all four points to be collinear. For example, $(0,0),(1,1),(2,2),(3,3)$. Proof: If all four points are collinear, then the first two columns of the $3times 3$ determinant above are linearly dependent.
Another case is for two points to have the same $x$-coordinate while the other two points share the same $y$-coordinate. For example, $(0,0),(0,1)$ and $(2,1),(2,2)$. Proof: Suppose WLOG that the two points with equal $x$-coordinates are $x_1=x_2=0$ as previously argued. Then $y_3=y_4$ and all the summands in our expression for $|M|$ vanish.
So we can give a formula for the $4times 4$ inverse exactly when determinant of $M$ is not zero. Putting the expression for the determinant back in its more general form, not assuming $(x_1,y_1)=(0,0)$, makes it look a bit more similar to the Vandermonde matrix determinant:
$$ begin{align*} det M &= (x_2-x_1)(x_4-x_1)(y_3-y_1)(y_4-y_2) \
&; ; ; + (x_3-x_1)(x_4-x_1)(y_2-y_1)(y_3-y_4) \
&; ; ; + (x_2-x_1)(x_3-x_1)(y_4-y_1)(y_2-y_3) end{align*} $$
answered Jan 9 at 15:55
hardmathhardmath
28.8k95296
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3059860%2finvert-a-4-times-4-matrix-with-a-given-structure%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Obtaining coefficients $a, b, c, d$ of the surface (quadric) with equation
$$z=a+bx+cy+dxy$$
passing through 4 points doesn't necessitate to solve a system of equations or the inversion of a linear system. It can be obtained directly. Here is how (Meanwhile, we will deepen our understanding because, in this way, one will get the inverse matrix of the initial matrix) :
Let us take the simplified case where the four points are
$$(x,y) = (0,0), (1,0), (0,1), (1,1)$$
with prescribed values :
$$f(0,0)=p, f(1,0)=q, f(0,1)=r, f(1,1)=s. (1)$$
Let us consider the following expression : in it, each one of the 4 terms has a specialized "task" ensuring that the four constraints (1) are fulfilled :
$$
begin{equation}
z=left{begin{array}{llll}
p×& (1-x)(1-y) +... & text{ ``activated'' iff} x=0 & y=0\
q×& x(1-y) +... & text{ ``activated'' iff} x=1 & y=0\
r×& (1-x)y +... & text{ ``activated'' iff} x=0 & y=0\
s×& xy; & text{ ``activated'' iff} x=1 & y=1
end{array}right.
end{equation}
$$
Expanding all, we get :
$$z=p(1-x-y+xy)+q(x-xy)+r(y-xy)+sxy iff$$
$$z=underbrace{p}_{= a}+underbrace{(-p+q)}_{= b}x+underbrace{(-p+r)}_{= c}y+underbrace{(p-q-r+s)}_{= d}xy$$
or, with a matrix formulation :
$$begin{pmatrix}a\b\c\dend{pmatrix}=
begin{pmatrix}
1& 0& 0&0\
-1& 1& 0&0\
-1& 0& 1&0\
1&-1&-1&1
end{pmatrix}
begin{pmatrix}p\q\r\send{pmatrix}$$
which is not surprizing, being naturally the inverse of system
$$begin{pmatrix}p\q\r\send{pmatrix}=
begin{pmatrix}
1&x_1&y_1&x_1y_1\
1&x_2&y_2&x_2y_2\
1&x_3&y_3&x_3y_3\
1&x_4&y_4&x_4y_4\
end{pmatrix}
begin{pmatrix}a\b\c\dend{pmatrix} iff $$
(with $(x_1,y_1)=(0,0), (x_2,y_2)=(1,0), (x_3,y_3)=(0,1), (x_4,y_4)=(1,1))$
$$begin{pmatrix}p\q\r\send{pmatrix}=
begin{pmatrix}
1&0&0&0\
1&1&0&0\
1&0&1&0\
1&1&1&1
end{pmatrix}
begin{pmatrix}a\b\c\dend{pmatrix}.$$
Edit :
1) This method (called "bilinear interpolation" as noted by @hardmath) as the OP has make the remark provides an answer only in the case of points constituting a rectangle with sides parallel to the axes.
2) If we assume that the coordinates axes constitute an orthonormal basis, the determinant of the matrix given in the question can receive a geometrical interpretation when expanded along its fourth column :
$$-x_1y_1underbrace{begin{vmatrix}
1&x_2&y_2\
1&x_3&y_3\
1&x_4&y_4
end{vmatrix}}_{2 times text{area of} P_2P_3P_4} + x_2y_2underbrace{begin{vmatrix}
1&x_1&y_1\
1&x_3&y_3\
1&x_4&y_4
end{vmatrix}}_{2 times text{area of} P_1P_3P_4} + cdots$$
thus a weighted combination of (oriented) areas of the different triangles one can make with points $P_1, P_2, P_3, P_4$ the weights being the product of coordinates of these points.
As one can freely choose the coordinate axes, one can take axes with $P_1$ the origin, and axes with basis $overrightarrow{P_1P_2}, overrightarrow{P_1P_3}$ (under the condition that $P_1,P_2,P_3$ aren't aligned ; this is of course no longer an orthonormal basis in general!). Thus, the determinant reduces to :
$$x_4y_4begin{vmatrix}
1&x_1&y_1\
1&x_2&y_2\
1&x_3&y_3
end{vmatrix}$$
which is nonzero unless point $P_4$ is situated on one of the coordinate axes (i.e. aligned with $P_1$ and $P_2$ or aligned with $P_1$ and $P_3$).
answered Jan 7 at 22:04
Jean MarieJean Marie
29.4k42050
$endgroup$
2
$begingroup$
First of all, thank you for your extensive answer. I see how this simplified result can easily be extended to the case where the four points form an arbitrary rectangle that is aligned with the axes, by modifying the four constraints accordingly. For $(x,y) = (u,v),(u',v),(u',v'),(u,v')$ we'd get $z = ptimes (1-x/u)(1-y/v)+ q times x/u'(1-y/v) + ldots$, which we could expand in the same way as you did to get the coefficients. But I fail to see how this provides a solution (or inverse of the matrix) for the general case. Could you elaborate on that?
$endgroup$
– flawr
Jan 7 at 23:05
1
$begingroup$
I agree on the fact (as I just did in my comment to @hardmath) that bilinear interpolation doesn't cover the general case (when I gave my answer, I recognize that I had completely overlooked this aspect). I just computed the (formal) inverse of the general matrix you give : it is very complicated... I think to two ways to treat the general case : 1) the usage of projective geometry that can provide a correspondence between any quadrilateral and a rectangle or 2) the usage of B-splines that can provide a way analogous to bilinear interpolation, providing a way to specify a local influence
$endgroup$
– Jean Marie
Jan 8 at 6:15
$begingroup$
Similar questions are treated in the very interesting (rather old) book "Group-Theoretical Methods in Image Understanding" by Ken-ichi Kanatani (Springer, 1990)
$endgroup$
– Jean Marie
Jan 8 at 6:27
$begingroup$
I have added an edit to my answer.
$endgroup$
– Jean Marie
Jan 8 at 7:08
add a comment |
$begingroup$
Obtaining coefficients $a, b, c, d$ of the surface (quadric) with equation
$$z=a+bx+cy+dxy$$
passing through 4 points doesn't necessitate to solve a system of equations or the inversion of a linear system. It can be obtained directly. Here is how (Meanwhile, we will deepen our understanding because, in this way, one will get the inverse matrix of the initial matrix) :
Let us take the simplified case where the four points are
$$(x,y) = (0,0), (1,0), (0,1), (1,1)$$
with prescribed values :
$$f(0,0)=p, f(1,0)=q, f(0,1)=r, f(1,1)=s. (1)$$
Let us consider the following expression : in it, each one of the 4 terms has a specialized "task" ensuring that the four constraints (1) are fulfilled :
$$
begin{equation}
z=left{begin{array}{llll}
p×& (1-x)(1-y) +... & text{ ``activated'' iff} x=0 & y=0\
q×& x(1-y) +... & text{ ``activated'' iff} x=1 & y=0\
r×& (1-x)y +... & text{ ``activated'' iff} x=0 & y=0\
s×& xy; & text{ ``activated'' iff} x=1 & y=1
end{array}right.
end{equation}
$$
Expanding all, we get :
$$z=p(1-x-y+xy)+q(x-xy)+r(y-xy)+sxy iff$$
$$z=underbrace{p}_{= a}+underbrace{(-p+q)}_{= b}x+underbrace{(-p+r)}_{= c}y+underbrace{(p-q-r+s)}_{= d}xy$$
or, with a matrix formulation :
$$begin{pmatrix}a\b\c\dend{pmatrix}=
begin{pmatrix}
1& 0& 0&0\
-1& 1& 0&0\
-1& 0& 1&0\
1&-1&-1&1
end{pmatrix}
begin{pmatrix}p\q\r\send{pmatrix}$$
which is not surprizing, being naturally the inverse of system
$$begin{pmatrix}p\q\r\send{pmatrix}=
begin{pmatrix}
1&x_1&y_1&x_1y_1\
1&x_2&y_2&x_2y_2\
1&x_3&y_3&x_3y_3\
1&x_4&y_4&x_4y_4\
end{pmatrix}
begin{pmatrix}a\b\c\dend{pmatrix} iff $$
(with $(x_1,y_1)=(0,0), (x_2,y_2)=(1,0), (x_3,y_3)=(0,1), (x_4,y_4)=(1,1))$
$$begin{pmatrix}p\q\r\send{pmatrix}=
begin{pmatrix}
1&0&0&0\
1&1&0&0\
1&0&1&0\
1&1&1&1
end{pmatrix}
begin{pmatrix}a\b\c\dend{pmatrix}.$$
Edit :
1) This method (called "bilinear interpolation" as noted by @hardmath) as the OP has make the remark provides an answer only in the case of points constituting a rectangle with sides parallel to the axes.
2) If we assume that the coordinates axes constitute an orthonormal basis, the determinant of the matrix given in the question can receive a geometrical interpretation when expanded along its fourth column :
$$-x_1y_1underbrace{begin{vmatrix}
1&x_2&y_2\
1&x_3&y_3\
1&x_4&y_4
end{vmatrix}}_{2 times text{area of} P_2P_3P_4} + x_2y_2underbrace{begin{vmatrix}
1&x_1&y_1\
1&x_3&y_3\
1&x_4&y_4
end{vmatrix}}_{2 times text{area of} P_1P_3P_4} + cdots$$
thus a weighted combination of (oriented) areas of the different triangles one can make with points $P_1, P_2, P_3, P_4$ the weights being the product of coordinates of these points.
As one can freely choose the coordinate axes, one can take axes with $P_1$ the origin, and axes with basis $overrightarrow{P_1P_2}, overrightarrow{P_1P_3}$ (under the condition that $P_1,P_2,P_3$ aren't aligned ; this is of course no longer an orthonormal basis in general!). Thus, the determinant reduces to :
$$x_4y_4begin{vmatrix}
1&x_1&y_1\
1&x_2&y_2\
1&x_3&y_3
end{vmatrix}$$
which is nonzero unless point $P_4$ is situated on one of the coordinate axes (i.e. aligned with $P_1$ and $P_2$ or aligned with $P_1$ and $P_3$).
answered Jan 7 at 22:04
Jean MarieJean Marie
29.4k42050
$endgroup$
2
$begingroup$
First of all, thank you for your extensive answer. I see how this simplified result can easily be extended to the case where the four points form an arbitrary rectangle that is aligned with the axes, by modifying the four constraints accordingly. For $(x,y) = (u,v),(u',v),(u',v'),(u,v')$ we'd get $z = ptimes (1-x/u)(1-y/v)+ q times x/u'(1-y/v) + ldots$, which we could expand in the same way as you did to get the coefficients. But I fail to see how this provides a solution (or inverse of the matrix) for the general case. Could you elaborate on that?
$endgroup$
– flawr
Jan 7 at 23:05
1
$begingroup$
I agree on the fact (as I just did in my comment to @hardmath) that bilinear interpolation doesn't cover the general case (when I gave my answer, I recognize that I had completely overlooked this aspect). I just computed the (formal) inverse of the general matrix you give : it is very complicated... I think to two ways to treat the general case : 1) the usage of projective geometry that can provide a correspondence between any quadrilateral and a rectangle or 2) the usage of B-splines that can provide a way analogous to bilinear interpolation, providing a way to specify a local influence
$endgroup$
– Jean Marie
Jan 8 at 6:15
$begingroup$
Similar questions are treated in the very interesting (rather old) book "Group-Theoretical Methods in Image Understanding" by Ken-ichi Kanatani (Springer, 1990)
$endgroup$
– Jean Marie
Jan 8 at 6:27
$begingroup$
I have added an edit to my answer.
$endgroup$
– Jean Marie
Jan 8 at 7:08
add a comment |
$begingroup$
Obtaining coefficients $a, b, c, d$ of the surface (quadric) with equation
$$z=a+bx+cy+dxy$$
passing through 4 points doesn't necessitate to solve a system of equations or the inversion of a linear system. It can be obtained directly. Here is how (Meanwhile, we will deepen our understanding because, in this way, one will get the inverse matrix of the initial matrix) :
Let us take the simplified case where the four points are
$$(x,y) = (0,0), (1,0), (0,1), (1,1)$$
with prescribed values :
$$f(0,0)=p, f(1,0)=q, f(0,1)=r, f(1,1)=s. (1)$$
Let us consider the following expression : in it, each one of the 4 terms has a specialized "task" ensuring that the four constraints (1) are fulfilled :
$$
begin{equation}
z=left{begin{array}{llll}
p×& (1-x)(1-y) +... & text{ ``activated'' iff} x=0 & y=0\
q×& x(1-y) +... & text{ ``activated'' iff} x=1 & y=0\
r×& (1-x)y +... & text{ ``activated'' iff} x=0 & y=0\
s×& xy; & text{ ``activated'' iff} x=1 & y=1
end{array}right.
end{equation}
$$
Expanding all, we get :
$$z=p(1-x-y+xy)+q(x-xy)+r(y-xy)+sxy iff$$
$$z=underbrace{p}_{= a}+underbrace{(-p+q)}_{= b}x+underbrace{(-p+r)}_{= c}y+underbrace{(p-q-r+s)}_{= d}xy$$
or, with a matrix formulation :
$$begin{pmatrix}a\b\c\dend{pmatrix}=
begin{pmatrix}
1& 0& 0&0\
-1& 1& 0&0\
-1& 0& 1&0\
1&-1&-1&1
end{pmatrix}
begin{pmatrix}p\q\r\send{pmatrix}$$
which is not surprizing, being naturally the inverse of system
$$begin{pmatrix}p\q\r\send{pmatrix}=
begin{pmatrix}
1&x_1&y_1&x_1y_1\
1&x_2&y_2&x_2y_2\
1&x_3&y_3&x_3y_3\
1&x_4&y_4&x_4y_4\
end{pmatrix}
begin{pmatrix}a\b\c\dend{pmatrix} iff $$
(with $(x_1,y_1)=(0,0), (x_2,y_2)=(1,0), (x_3,y_3)=(0,1), (x_4,y_4)=(1,1))$
$$begin{pmatrix}p\q\r\send{pmatrix}=
begin{pmatrix}
1&0&0&0\
1&1&0&0\
1&0&1&0\
1&1&1&1
end{pmatrix}
begin{pmatrix}a\b\c\dend{pmatrix}.$$
Edit :
1) This method (called "bilinear interpolation" as noted by @hardmath) as the OP has make the remark provides an answer only in the case of points constituting a rectangle with sides parallel to the axes.
2) If we assume that the coordinates axes constitute an orthonormal basis, the determinant of the matrix given in the question can receive a geometrical interpretation when expanded along its fourth column :
$$-x_1y_1underbrace{begin{vmatrix}
1&x_2&y_2\
1&x_3&y_3\
1&x_4&y_4
end{vmatrix}}_{2 times text{area of} P_2P_3P_4} + x_2y_2underbrace{begin{vmatrix}
1&x_1&y_1\
1&x_3&y_3\
1&x_4&y_4
end{vmatrix}}_{2 times text{area of} P_1P_3P_4} + cdots$$
thus a weighted combination of (oriented) areas of the different triangles one can make with points $P_1, P_2, P_3, P_4$ the weights being the product of coordinates of these points.
As one can freely choose the coordinate axes, one can take axes with $P_1$ the origin, and axes with basis $overrightarrow{P_1P_2}, overrightarrow{P_1P_3}$ (under the condition that $P_1,P_2,P_3$ aren't aligned ; this is of course no longer an orthonormal basis in general!). Thus, the determinant reduces to :
$$x_4y_4begin{vmatrix}
1&x_1&y_1\
1&x_2&y_2\
1&x_3&y_3
end{vmatrix}$$
which is nonzero unless point $P_4$ is situated on one of the coordinate axes (i.e. aligned with $P_1$ and $P_2$ or aligned with $P_1$ and $P_3$).
answered Jan 7 at 22:04
Jean MarieJean Marie
29.4k42050
$endgroup$
Obtaining coefficients $a, b, c, d$ of the surface (quadric) with equation
$$z=a+bx+cy+dxy$$
passing through 4 points doesn't necessitate to solve a system of equations or the inversion of a linear system. It can be obtained directly. Here is how (Meanwhile, we will deepen our understanding because, in this way, one will get the inverse matrix of the initial matrix) :
Let us take the simplified case where the four points are
$$(x,y) = (0,0), (1,0), (0,1), (1,1)$$
with prescribed values :
$$f(0,0)=p, f(1,0)=q, f(0,1)=r, f(1,1)=s. (1)$$
Let us consider the following expression : in it, each one of the 4 terms has a specialized "task" ensuring that the four constraints (1) are fulfilled :
$$
begin{equation}
z=left{begin{array}{llll}
p×& (1-x)(1-y) +... & text{ ``activated'' iff} x=0 & y=0\
q×& x(1-y) +... & text{ ``activated'' iff} x=1 & y=0\
r×& (1-x)y +... & text{ ``activated'' iff} x=0 & y=0\
s×& xy; & text{ ``activated'' iff} x=1 & y=1
end{array}right.
end{equation}
$$
Expanding all, we get :
$$z=p(1-x-y+xy)+q(x-xy)+r(y-xy)+sxy iff$$
$$z=underbrace{p}_{= a}+underbrace{(-p+q)}_{= b}x+underbrace{(-p+r)}_{= c}y+underbrace{(p-q-r+s)}_{= d}xy$$
or, with a matrix formulation :
$$begin{pmatrix}a\b\c\dend{pmatrix}=
begin{pmatrix}
1& 0& 0&0\
-1& 1& 0&0\
-1& 0& 1&0\
1&-1&-1&1
end{pmatrix}
begin{pmatrix}p\q\r\send{pmatrix}$$
which is not surprizing, being naturally the inverse of system
$$begin{pmatrix}p\q\r\send{pmatrix}=
begin{pmatrix}
1&x_1&y_1&x_1y_1\
1&x_2&y_2&x_2y_2\
1&x_3&y_3&x_3y_3\
1&x_4&y_4&x_4y_4\
end{pmatrix}
begin{pmatrix}a\b\c\dend{pmatrix} iff $$
(with $(x_1,y_1)=(0,0), (x_2,y_2)=(1,0), (x_3,y_3)=(0,1), (x_4,y_4)=(1,1))$
$$begin{pmatrix}p\q\r\send{pmatrix}=
begin{pmatrix}
1&0&0&0\
1&1&0&0\
1&0&1&0\
1&1&1&1
end{pmatrix}
begin{pmatrix}a\b\c\dend{pmatrix}.$$
Edit :
1) This method (called "bilinear interpolation" as noted by @hardmath) as the OP has make the remark provides an answer only in the case of points constituting a rectangle with sides parallel to the axes.
2) If we assume that the coordinates axes constitute an orthonormal basis, the determinant of the matrix given in the question can receive a geometrical interpretation when expanded along its fourth column :
$$-x_1y_1underbrace{begin{vmatrix}
1&x_2&y_2\
1&x_3&y_3\
1&x_4&y_4
end{vmatrix}}_{2 times text{area of} P_2P_3P_4} + x_2y_2underbrace{begin{vmatrix}
1&x_1&y_1\
1&x_3&y_3\
1&x_4&y_4
end{vmatrix}}_{2 times text{area of} P_1P_3P_4} + cdots$$
thus a weighted combination of (oriented) areas of the different triangles one can make with points $P_1, P_2, P_3, P_4$ the weights being the product of coordinates of these points.
As one can freely choose the coordinate axes, one can take axes with $P_1$ the origin, and axes with basis $overrightarrow{P_1P_2}, overrightarrow{P_1P_3}$ (under the condition that $P_1,P_2,P_3$ aren't aligned ; this is of course no longer an orthonormal basis in general!). Thus, the determinant reduces to :
$$x_4y_4begin{vmatrix}
1&x_1&y_1\
1&x_2&y_2\
1&x_3&y_3
end{vmatrix}$$
which is nonzero unless point $P_4$ is situated on one of the coordinate axes (i.e. aligned with $P_1$ and $P_2$ or aligned with $P_1$ and $P_3$).
answered Jan 7 at 22:04
Jean MarieJean Marie
29.4k42050
edited Jan 9 at 22:03
answered Jan 7 at 22:04
Jean MarieJean Marie
29.4k42050
answered Jan 7 at 22:04
Jean MarieJean Marie
29.4k42050
answered Jan 7 at 22:04
Jean MarieJean Marie
29.4k42050
29.4k42050
2
$begingroup$
First of all, thank you for your extensive answer. I see how this simplified result can easily be extended to the case where the four points form an arbitrary rectangle that is aligned with the axes, by modifying the four constraints accordingly. For $(x,y) = (u,v),(u',v),(u',v'),(u,v')$ we'd get $z = ptimes (1-x/u)(1-y/v)+ q times x/u'(1-y/v) + ldots$, which we could expand in the same way as you did to get the coefficients. But I fail to see how this provides a solution (or inverse of the matrix) for the general case. Could you elaborate on that?
$endgroup$
– flawr
Jan 7 at 23:05
1
$begingroup$
I agree on the fact (as I just did in my comment to @hardmath) that bilinear interpolation doesn't cover the general case (when I gave my answer, I recognize that I had completely overlooked this aspect). I just computed the (formal) inverse of the general matrix you give : it is very complicated... I think to two ways to treat the general case : 1) the usage of projective geometry that can provide a correspondence between any quadrilateral and a rectangle or 2) the usage of B-splines that can provide a way analogous to bilinear interpolation, providing a way to specify a local influence
$endgroup$
– Jean Marie
Jan 8 at 6:15
$begingroup$
Similar questions are treated in the very interesting (rather old) book "Group-Theoretical Methods in Image Understanding" by Ken-ichi Kanatani (Springer, 1990)
$endgroup$
– Jean Marie
Jan 8 at 6:27
$begingroup$
I have added an edit to my answer.
$endgroup$
– Jean Marie
Jan 8 at 7:08
add a comment |
2
$begingroup$
First of all, thank you for your extensive answer. I see how this simplified result can easily be extended to the case where the four points form an arbitrary rectangle that is aligned with the axes, by modifying the four constraints accordingly. For $(x,y) = (u,v),(u',v),(u',v'),(u,v')$ we'd get $z = ptimes (1-x/u)(1-y/v)+ q times x/u'(1-y/v) + ldots$, which we could expand in the same way as you did to get the coefficients. But I fail to see how this provides a solution (or inverse of the matrix) for the general case. Could you elaborate on that?
$endgroup$
– flawr
Jan 7 at 23:05
1
$begingroup$
I agree on the fact (as I just did in my comment to @hardmath) that bilinear interpolation doesn't cover the general case (when I gave my answer, I recognize that I had completely overlooked this aspect). I just computed the (formal) inverse of the general matrix you give : it is very complicated... I think to two ways to treat the general case : 1) the usage of projective geometry that can provide a correspondence between any quadrilateral and a rectangle or 2) the usage of B-splines that can provide a way analogous to bilinear interpolation, providing a way to specify a local influence
$endgroup$
– Jean Marie
Jan 8 at 6:15
$begingroup$
Similar questions are treated in the very interesting (rather old) book "Group-Theoretical Methods in Image Understanding" by Ken-ichi Kanatani (Springer, 1990)
$endgroup$
– Jean Marie
Jan 8 at 6:27
$begingroup$
I have added an edit to my answer.
$endgroup$
– Jean Marie
Jan 8 at 7:08
2
2
$begingroup$
First of all, thank you for your extensive answer. I see how this simplified result can easily be extended to the case where the four points form an arbitrary rectangle that is aligned with the axes, by modifying the four constraints accordingly. For $(x,y) = (u,v),(u',v),(u',v'),(u,v')$ we'd get $z = ptimes (1-x/u)(1-y/v)+ q times x/u'(1-y/v) + ldots$, which we could expand in the same way as you did to get the coefficients. But I fail to see how this provides a solution (or inverse of the matrix) for the general case. Could you elaborate on that?
$endgroup$
– flawr
Jan 7 at 23:05
$begingroup$
First of all, thank you for your extensive answer. I see how this simplified result can easily be extended to the case where the four points form an arbitrary rectangle that is aligned with the axes, by modifying the four constraints accordingly. For $(x,y) = (u,v),(u',v),(u',v'),(u,v')$ we'd get $z = ptimes (1-x/u)(1-y/v)+ q times x/u'(1-y/v) + ldots$, which we could expand in the same way as you did to get the coefficients. But I fail to see how this provides a solution (or inverse of the matrix) for the general case. Could you elaborate on that?
$endgroup$
– flawr
Jan 7 at 23:05
1
1
$begingroup$
I agree on the fact (as I just did in my comment to @hardmath) that bilinear interpolation doesn't cover the general case (when I gave my answer, I recognize that I had completely overlooked this aspect). I just computed the (formal) inverse of the general matrix you give : it is very complicated... I think to two ways to treat the general case : 1) the usage of projective geometry that can provide a correspondence between any quadrilateral and a rectangle or 2) the usage of B-splines that can provide a way analogous to bilinear interpolation, providing a way to specify a local influence
$endgroup$
– Jean Marie
Jan 8 at 6:15
$begingroup$
I agree on the fact (as I just did in my comment to @hardmath) that bilinear interpolation doesn't cover the general case (when I gave my answer, I recognize that I had completely overlooked this aspect). I just computed the (formal) inverse of the general matrix you give : it is very complicated... I think to two ways to treat the general case : 1) the usage of projective geometry that can provide a correspondence between any quadrilateral and a rectangle or 2) the usage of B-splines that can provide a way analogous to bilinear interpolation, providing a way to specify a local influence
$endgroup$
– Jean Marie
Jan 8 at 6:15
$begingroup$
Similar questions are treated in the very interesting (rather old) book "Group-Theoretical Methods in Image Understanding" by Ken-ichi Kanatani (Springer, 1990)
$endgroup$
– Jean Marie
Jan 8 at 6:27
$begingroup$
Similar questions are treated in the very interesting (rather old) book "Group-Theoretical Methods in Image Understanding" by Ken-ichi Kanatani (Springer, 1990)
$endgroup$
– Jean Marie
Jan 8 at 6:27
$begingroup$
I have added an edit to my answer.
$endgroup$
– Jean Marie
Jan 8 at 7:08
$begingroup$
I have added an edit to my answer.
$endgroup$
– Jean Marie
Jan 8 at 7:08
add a comment |
$begingroup$
Given four distinct points $(x_1,y_1),(x_2,y_2),(x_3,y_3),(x_4,y_4)$, we can exhibit the cases for which the matrix $M$ is invertible, and hence for which all the bilinear interpolation problems are uniquely solvable, by evaluating the determinant of $M$ as a quartic polynomial in the $x_i,y_i$.
It will simplify our work, and help to provide a geometric interpretation of the result, if we begin with a change of variable translating the first of these points to the origin:
$$ u = x - x_1 $$
$$ v = y - y_1 $$
Supposing that with the same function values at points $(u_i,v_i) = (x_i-x_1,y_i-y_1)$ as in the corresponding original points, a bilinear interpolant exists:
$$ g(u,v) = hat a + hat b u + hat c v + hat d uv $$
Then the solution to the original problem will be:
$$ begin{align*} f(x,y) &= hat a + hat b (x-x_1) + hat c (y-y_1) + hat d (x-x_1)(y-y_1) \
&= (hat a - hat b x_1 - hat c y_1 + hat d x_1 y_1) + (hat b - hat dy_1)x \
&; ; ; + (hat c - hat dx_1)y + hat d xy end{align*} $$
It follows that this solution would uniquely determine the desired bilinear interpolant $f(x,y)$ at the original points:
$$ begin{pmatrix} a \ b \ c \ d end{pmatrix}
= begin{pmatrix} 1 & -x_1 & -y_1 & x_1y_1 \
0 & 1 & 0 & -y_1 \
0 & 0 & 1 & -x_1 \
0 & 0 & 0 & 1 end{pmatrix}
begin{pmatrix} hat a \ hat b \ hat c \ hat d end{pmatrix} $$
In that sense we can assume without loss of generality that $(x_1,y_1) = (0,0)$, and we proceed to find the determinant of $M$ in this slightly special case:
$$ begin{align*} det M &= left| begin{array}{cccc}
1 & 0 & 0 & 0 \
1 & x_2 & y_2 & x_2 y_2 \
1 & x_3 & y_3 & x_3 y_3 \
1 & x_4 & y_4 & x_4 y_4 end{array} right| \
&= left| begin{array}{ccc}
x_2 & y_2 & x_2 y_2 \
x_3 & y_3 & x_3 y_3 \
x_4 & y_4 & x_4 y_4 end{array} right| \
&= x_2x_4y_3(y_4-y_2) + x_3x_4y_2(y_3-y_4) + x_2x_3y_4(y_2-y_3)
end{align*} $$
With this expression we can identify some geometric conditions on the four points for which the matrix has zero determinant and is thus not invertible. One such case is for all four points to be collinear. For example, $(0,0),(1,1),(2,2),(3,3)$. Proof: If all four points are collinear, then the first two columns of the $3times 3$ determinant above are linearly dependent.
Another case is for two points to have the same $x$-coordinate while the other two points share the same $y$-coordinate. For example, $(0,0),(0,1)$ and $(2,1),(2,2)$. Proof: Suppose WLOG that the two points with equal $x$-coordinates are $x_1=x_2=0$ as previously argued. Then $y_3=y_4$ and all the summands in our expression for $|M|$ vanish.
So we can give a formula for the $4times 4$ inverse exactly when determinant of $M$ is not zero. Putting the expression for the determinant back in its more general form, not assuming $(x_1,y_1)=(0,0)$, makes it look a bit more similar to the Vandermonde matrix determinant:
$$ begin{align*} det M &= (x_2-x_1)(x_4-x_1)(y_3-y_1)(y_4-y_2) \
&; ; ; + (x_3-x_1)(x_4-x_1)(y_2-y_1)(y_3-y_4) \
&; ; ; + (x_2-x_1)(x_3-x_1)(y_4-y_1)(y_2-y_3) end{align*} $$
answered Jan 9 at 15:55
hardmathhardmath
28.8k95296
$endgroup$
add a comment |
$begingroup$
Given four distinct points $(x_1,y_1),(x_2,y_2),(x_3,y_3),(x_4,y_4)$, we can exhibit the cases for which the matrix $M$ is invertible, and hence for which all the bilinear interpolation problems are uniquely solvable, by evaluating the determinant of $M$ as a quartic polynomial in the $x_i,y_i$.
It will simplify our work, and help to provide a geometric interpretation of the result, if we begin with a change of variable translating the first of these points to the origin:
$$ u = x - x_1 $$
$$ v = y - y_1 $$
Supposing that with the same function values at points $(u_i,v_i) = (x_i-x_1,y_i-y_1)$ as in the corresponding original points, a bilinear interpolant exists:
$$ g(u,v) = hat a + hat b u + hat c v + hat d uv $$
Then the solution to the original problem will be:
$$ begin{align*} f(x,y) &= hat a + hat b (x-x_1) + hat c (y-y_1) + hat d (x-x_1)(y-y_1) \
&= (hat a - hat b x_1 - hat c y_1 + hat d x_1 y_1) + (hat b - hat dy_1)x \
&; ; ; + (hat c - hat dx_1)y + hat d xy end{align*} $$
It follows that this solution would uniquely determine the desired bilinear interpolant $f(x,y)$ at the original points:
$$ begin{pmatrix} a \ b \ c \ d end{pmatrix}
= begin{pmatrix} 1 & -x_1 & -y_1 & x_1y_1 \
0 & 1 & 0 & -y_1 \
0 & 0 & 1 & -x_1 \
0 & 0 & 0 & 1 end{pmatrix}
begin{pmatrix} hat a \ hat b \ hat c \ hat d end{pmatrix} $$
In that sense we can assume without loss of generality that $(x_1,y_1) = (0,0)$, and we proceed to find the determinant of $M$ in this slightly special case:
$$ begin{align*} det M &= left| begin{array}{cccc}
1 & 0 & 0 & 0 \
1 & x_2 & y_2 & x_2 y_2 \
1 & x_3 & y_3 & x_3 y_3 \
1 & x_4 & y_4 & x_4 y_4 end{array} right| \
&= left| begin{array}{ccc}
x_2 & y_2 & x_2 y_2 \
x_3 & y_3 & x_3 y_3 \
x_4 & y_4 & x_4 y_4 end{array} right| \
&= x_2x_4y_3(y_4-y_2) + x_3x_4y_2(y_3-y_4) + x_2x_3y_4(y_2-y_3)
end{align*} $$
With this expression we can identify some geometric conditions on the four points for which the matrix has zero determinant and is thus not invertible. One such case is for all four points to be collinear. For example, $(0,0),(1,1),(2,2),(3,3)$. Proof: If all four points are collinear, then the first two columns of the $3times 3$ determinant above are linearly dependent.
Another case is for two points to have the same $x$-coordinate while the other two points share the same $y$-coordinate. For example, $(0,0),(0,1)$ and $(2,1),(2,2)$. Proof: Suppose WLOG that the two points with equal $x$-coordinates are $x_1=x_2=0$ as previously argued. Then $y_3=y_4$ and all the summands in our expression for $|M|$ vanish.
So we can give a formula for the $4times 4$ inverse exactly when determinant of $M$ is not zero. Putting the expression for the determinant back in its more general form, not assuming $(x_1,y_1)=(0,0)$, makes it look a bit more similar to the Vandermonde matrix determinant:
$$ begin{align*} det M &= (x_2-x_1)(x_4-x_1)(y_3-y_1)(y_4-y_2) \
&; ; ; + (x_3-x_1)(x_4-x_1)(y_2-y_1)(y_3-y_4) \
&; ; ; + (x_2-x_1)(x_3-x_1)(y_4-y_1)(y_2-y_3) end{align*} $$
answered Jan 9 at 15:55
hardmathhardmath
28.8k95296
$endgroup$
add a comment |
$begingroup$
Given four distinct points $(x_1,y_1),(x_2,y_2),(x_3,y_3),(x_4,y_4)$, we can exhibit the cases for which the matrix $M$ is invertible, and hence for which all the bilinear interpolation problems are uniquely solvable, by evaluating the determinant of $M$ as a quartic polynomial in the $x_i,y_i$.
It will simplify our work, and help to provide a geometric interpretation of the result, if we begin with a change of variable translating the first of these points to the origin:
$$ u = x - x_1 $$
$$ v = y - y_1 $$
Supposing that with the same function values at points $(u_i,v_i) = (x_i-x_1,y_i-y_1)$ as in the corresponding original points, a bilinear interpolant exists:
$$ g(u,v) = hat a + hat b u + hat c v + hat d uv $$
Then the solution to the original problem will be:
$$ begin{align*} f(x,y) &= hat a + hat b (x-x_1) + hat c (y-y_1) + hat d (x-x_1)(y-y_1) \
&= (hat a - hat b x_1 - hat c y_1 + hat d x_1 y_1) + (hat b - hat dy_1)x \
&; ; ; + (hat c - hat dx_1)y + hat d xy end{align*} $$
It follows that this solution would uniquely determine the desired bilinear interpolant $f(x,y)$ at the original points:
$$ begin{pmatrix} a \ b \ c \ d end{pmatrix}
= begin{pmatrix} 1 & -x_1 & -y_1 & x_1y_1 \
0 & 1 & 0 & -y_1 \
0 & 0 & 1 & -x_1 \
0 & 0 & 0 & 1 end{pmatrix}
begin{pmatrix} hat a \ hat b \ hat c \ hat d end{pmatrix} $$
In that sense we can assume without loss of generality that $(x_1,y_1) = (0,0)$, and we proceed to find the determinant of $M$ in this slightly special case:
$$ begin{align*} det M &= left| begin{array}{cccc}
1 & 0 & 0 & 0 \
1 & x_2 & y_2 & x_2 y_2 \
1 & x_3 & y_3 & x_3 y_3 \
1 & x_4 & y_4 & x_4 y_4 end{array} right| \
&= left| begin{array}{ccc}
x_2 & y_2 & x_2 y_2 \
x_3 & y_3 & x_3 y_3 \
x_4 & y_4 & x_4 y_4 end{array} right| \
&= x_2x_4y_3(y_4-y_2) + x_3x_4y_2(y_3-y_4) + x_2x_3y_4(y_2-y_3)
end{align*} $$
With this expression we can identify some geometric conditions on the four points for which the matrix has zero determinant and is thus not invertible. One such case is for all four points to be collinear. For example, $(0,0),(1,1),(2,2),(3,3)$. Proof: If all four points are collinear, then the first two columns of the $3times 3$ determinant above are linearly dependent.
Another case is for two points to have the same $x$-coordinate while the other two points share the same $y$-coordinate. For example, $(0,0),(0,1)$ and $(2,1),(2,2)$. Proof: Suppose WLOG that the two points with equal $x$-coordinates are $x_1=x_2=0$ as previously argued. Then $y_3=y_4$ and all the summands in our expression for $|M|$ vanish.
So we can give a formula for the $4times 4$ inverse exactly when determinant of $M$ is not zero. Putting the expression for the determinant back in its more general form, not assuming $(x_1,y_1)=(0,0)$, makes it look a bit more similar to the Vandermonde matrix determinant:
$$ begin{align*} det M &= (x_2-x_1)(x_4-x_1)(y_3-y_1)(y_4-y_2) \
&; ; ; + (x_3-x_1)(x_4-x_1)(y_2-y_1)(y_3-y_4) \
&; ; ; + (x_2-x_1)(x_3-x_1)(y_4-y_1)(y_2-y_3) end{align*} $$
answered Jan 9 at 15:55
hardmathhardmath
28.8k95296
$endgroup$
Given four distinct points $(x_1,y_1),(x_2,y_2),(x_3,y_3),(x_4,y_4)$, we can exhibit the cases for which the matrix $M$ is invertible, and hence for which all the bilinear interpolation problems are uniquely solvable, by evaluating the determinant of $M$ as a quartic polynomial in the $x_i,y_i$.
It will simplify our work, and help to provide a geometric interpretation of the result, if we begin with a change of variable translating the first of these points to the origin:
$$ u = x - x_1 $$
$$ v = y - y_1 $$
Supposing that with the same function values at points $(u_i,v_i) = (x_i-x_1,y_i-y_1)$ as in the corresponding original points, a bilinear interpolant exists:
$$ g(u,v) = hat a + hat b u + hat c v + hat d uv $$
Then the solution to the original problem will be:
$$ begin{align*} f(x,y) &= hat a + hat b (x-x_1) + hat c (y-y_1) + hat d (x-x_1)(y-y_1) \
&= (hat a - hat b x_1 - hat c y_1 + hat d x_1 y_1) + (hat b - hat dy_1)x \
&; ; ; + (hat c - hat dx_1)y + hat d xy end{align*} $$
It follows that this solution would uniquely determine the desired bilinear interpolant $f(x,y)$ at the original points:
$$ begin{pmatrix} a \ b \ c \ d end{pmatrix}
= begin{pmatrix} 1 & -x_1 & -y_1 & x_1y_1 \
0 & 1 & 0 & -y_1 \
0 & 0 & 1 & -x_1 \
0 & 0 & 0 & 1 end{pmatrix}
begin{pmatrix} hat a \ hat b \ hat c \ hat d end{pmatrix} $$
In that sense we can assume without loss of generality that $(x_1,y_1) = (0,0)$, and we proceed to find the determinant of $M$ in this slightly special case:
$$ begin{align*} det M &= left| begin{array}{cccc}
1 & 0 & 0 & 0 \
1 & x_2 & y_2 & x_2 y_2 \
1 & x_3 & y_3 & x_3 y_3 \
1 & x_4 & y_4 & x_4 y_4 end{array} right| \
&= left| begin{array}{ccc}
x_2 & y_2 & x_2 y_2 \
x_3 & y_3 & x_3 y_3 \
x_4 & y_4 & x_4 y_4 end{array} right| \
&= x_2x_4y_3(y_4-y_2) + x_3x_4y_2(y_3-y_4) + x_2x_3y_4(y_2-y_3)
end{align*} $$
With this expression we can identify some geometric conditions on the four points for which the matrix has zero determinant and is thus not invertible. One such case is for all four points to be collinear. For example, $(0,0),(1,1),(2,2),(3,3)$. Proof: If all four points are collinear, then the first two columns of the $3times 3$ determinant above are linearly dependent.
Another case is for two points to have the same $x$-coordinate while the other two points share the same $y$-coordinate. For example, $(0,0),(0,1)$ and $(2,1),(2,2)$. Proof: Suppose WLOG that the two points with equal $x$-coordinates are $x_1=x_2=0$ as previously argued. Then $y_3=y_4$ and all the summands in our expression for $|M|$ vanish.
So we can give a formula for the $4times 4$ inverse exactly when determinant of $M$ is not zero. Putting the expression for the determinant back in its more general form, not assuming $(x_1,y_1)=(0,0)$, makes it look a bit more similar to the Vandermonde matrix determinant:
$$ begin{align*} det M &= (x_2-x_1)(x_4-x_1)(y_3-y_1)(y_4-y_2) \
&; ; ; + (x_3-x_1)(x_4-x_1)(y_2-y_1)(y_3-y_4) \
&; ; ; + (x_2-x_1)(x_3-x_1)(y_4-y_1)(y_2-y_3) end{align*} $$
answered Jan 9 at 15:55
hardmathhardmath
28.8k95296
edited Jan 9 at 20:53
answered Jan 9 at 15:55
hardmathhardmath
28.8k95296
answered Jan 9 at 15:55
hardmathhardmath
28.8k95296
answered Jan 9 at 15:55
hardmathhardmath
28.8k95296
28.8k95296
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3059860%2finvert-a-4-times-4-matrix-with-a-given-structure%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
This is bilinear interpolation.
$endgroup$
– hardmath
Jan 7 at 22:36
$begingroup$
@hardmath Yes, but unfortunately WP also only shows the cases of an unit square and an axes-aligned rectangle.
$endgroup$
– flawr
Jan 7 at 23:07
$begingroup$
I take your points! A more general solution can be found if the four points are an affine image of corners of the unit square. For some four points the determinant vanishes and no matrix inverse exists. I'll add a note.
$endgroup$
– hardmath
Jan 7 at 23:34
$begingroup$
@hardmath The affine image of a rectangle is a parallelogram; thus we still haven't an answer for the general case where the 4 points can be any set of four points.
$endgroup$
– Jean Marie
Jan 8 at 5:55