How to deal with the non-uniqueness of SVD in numerical applications?
$begingroup$
There are many applications in applied mathematics where the SVD of a matrix comes in handy. For example, consider the problem where we want to find an approximate solution to a(n) (overdetermined) linear system of equations $Avec{x}=0$ subject to $|vec{x}|=1$. It can be shown that the last column of $V$ in $A = UDV^t$ is the solution to this system subject to $|vec{x}| = 1$.
The problem is that the SVD of a matrix is not unique. $U$ and $V$ are orthonormal matrices but we still have freedom in choosing signs. In cases like this, how can I do something that resolves the ambiguity? Is there a trick or a natural convention for the signs that ensures I always get the same answer no matter what?
In particular, what can I do in MATLAB to avoid this ambiguity?
Edit:
A specific example where non-uniquess can become an issue:
Suppose that you want to measure the intrinsic parameters of a pinhole camera. It turns out that in practical cases, $K$, the calibration matrix,
is an upper triangular matrix. A little bit of algebraic manipulation, gives us a symmetric matrix $B=K^{-t}K^{-1}$ which has a nice interpretation and it's sufficient for finding $K$. Anyway, to find $K$, you will take photos of a checkerboard pattern and generally, you arrive at a linear system like $A_{n times 6} times b_{6 times 1}=0_{n times 1}$ with the additional constraint that $|vec{b}|=1$ (to avoid the trivial answer). Here are some numerical results that I have obtained for $B$ after running the algorithm on synthesized checkerboard photos:
begin{bmatrix}
0.000000082076150 && -0.000000000008003 && -0.000037912894906 \
-0.000000000008003 && 0.000000071823158 && -0.000055278469079 \
-0.000037912894906 && -0.000055278469079 && 0.999999997753446 \
end{bmatrix}
begin{bmatrix}
-0.000000104164118 && -0.000000000027239 && 0.000053428189068 \
-0.000000000027239 && -0.000000091142604 && 0.000067709246949 \
0.000053428189068 && 0.000067709246949 && -0.999999996280434
end{bmatrix}
begin{bmatrix}
0.000000109630415 && 0.000000000051933 && -0.000056355404234 \
0.000000000051933 && 0.000000095949976 && -0.000071441815015 \
-0.000056355404234 && -0.000071441815015 && 0.999999995860057
end{bmatrix}
Since $K$ is intrinsic and it only depends on the structure of the camera itself, the values we find for $p_x$, $p_y$, $f_x$ and $f_y$ must remain close to each other. Unfortunately, using the above matrices, sometimes $p_x$ and $p_y$ are minus their actual values. I blame the sign inconsistency of SVD decomposition for this.
linear-algebra matlab svd
asked Dec 14 '18 at 19:46
stressed outstressed out
6,5231939
$endgroup$
|
show 13 more comments
$begingroup$
There are many applications in applied mathematics where the SVD of a matrix comes in handy. For example, consider the problem where we want to find an approximate solution to a(n) (overdetermined) linear system of equations $Avec{x}=0$ subject to $|vec{x}|=1$. It can be shown that the last column of $V$ in $A = UDV^t$ is the solution to this system subject to $|vec{x}| = 1$.
The problem is that the SVD of a matrix is not unique. $U$ and $V$ are orthonormal matrices but we still have freedom in choosing signs. In cases like this, how can I do something that resolves the ambiguity? Is there a trick or a natural convention for the signs that ensures I always get the same answer no matter what?
In particular, what can I do in MATLAB to avoid this ambiguity?
Edit:
A specific example where non-uniquess can become an issue:
Suppose that you want to measure the intrinsic parameters of a pinhole camera. It turns out that in practical cases, $K$, the calibration matrix,
is an upper triangular matrix. A little bit of algebraic manipulation, gives us a symmetric matrix $B=K^{-t}K^{-1}$ which has a nice interpretation and it's sufficient for finding $K$. Anyway, to find $K$, you will take photos of a checkerboard pattern and generally, you arrive at a linear system like $A_{n times 6} times b_{6 times 1}=0_{n times 1}$ with the additional constraint that $|vec{b}|=1$ (to avoid the trivial answer). Here are some numerical results that I have obtained for $B$ after running the algorithm on synthesized checkerboard photos:
begin{bmatrix}
0.000000082076150 && -0.000000000008003 && -0.000037912894906 \
-0.000000000008003 && 0.000000071823158 && -0.000055278469079 \
-0.000037912894906 && -0.000055278469079 && 0.999999997753446 \
end{bmatrix}
begin{bmatrix}
-0.000000104164118 && -0.000000000027239 && 0.000053428189068 \
-0.000000000027239 && -0.000000091142604 && 0.000067709246949 \
0.000053428189068 && 0.000067709246949 && -0.999999996280434
end{bmatrix}
begin{bmatrix}
0.000000109630415 && 0.000000000051933 && -0.000056355404234 \
0.000000000051933 && 0.000000095949976 && -0.000071441815015 \
-0.000056355404234 && -0.000071441815015 && 0.999999995860057
end{bmatrix}
Since $K$ is intrinsic and it only depends on the structure of the camera itself, the values we find for $p_x$, $p_y$, $f_x$ and $f_y$ must remain close to each other. Unfortunately, using the above matrices, sometimes $p_x$ and $p_y$ are minus their actual values. I blame the sign inconsistency of SVD decomposition for this.
linear-algebra matlab svd
asked Dec 14 '18 at 19:46
stressed outstressed out
6,5231939
$endgroup$
1
$begingroup$
Can you be a bit more specific as to how non-uniqueness becomes a problem?
$endgroup$
– Omnomnomnom
Dec 14 '18 at 19:59
1
$begingroup$
Enforce a positive determinant for $U$ and the ambiguity is gone.
$endgroup$
– Yves Daoust
Dec 14 '18 at 20:23
$begingroup$
Yep, my bad. You could enforce a particular element being positive, but this doesn't work when the element is zero. This is why I suggested a determinant.
$endgroup$
– Yves Daoust
Dec 14 '18 at 20:29
1
$begingroup$
@stressedout How are you getting multiple measurements for the intrinsic parameters? As I recall, the procedure for measuring them consists of taking several photos from different angles, putting all the keypoints in a matrix, then crunching numbers with the svd to solve a problem that produces a single set of measurements. No matter how many pictures you took, they'd all go into the same single computation that is aimed toward a single set of parameters. Are you measuring multiple times and getting wildly different answers for some reason?
$endgroup$
– rschwieb
Dec 14 '18 at 21:05
1
$begingroup$
@Raaja overdetermined systems almost always are inconsistent. This is where the condition that $|x| = 1$ comes into play. $| cdot |$ here denotes the Euclidean norm, but one can use other norms. It really depends on you to choose what you're looking for. This is what rschwieb refers to as a best-fit solution.
$endgroup$
– stressed out
Dec 14 '18 at 21:11
|
show 13 more comments
$begingroup$
There are many applications in applied mathematics where the SVD of a matrix comes in handy. For example, consider the problem where we want to find an approximate solution to a(n) (overdetermined) linear system of equations $Avec{x}=0$ subject to $|vec{x}|=1$. It can be shown that the last column of $V$ in $A = UDV^t$ is the solution to this system subject to $|vec{x}| = 1$.
The problem is that the SVD of a matrix is not unique. $U$ and $V$ are orthonormal matrices but we still have freedom in choosing signs. In cases like this, how can I do something that resolves the ambiguity? Is there a trick or a natural convention for the signs that ensures I always get the same answer no matter what?
In particular, what can I do in MATLAB to avoid this ambiguity?
Edit:
A specific example where non-uniquess can become an issue:
Suppose that you want to measure the intrinsic parameters of a pinhole camera. It turns out that in practical cases, $K$, the calibration matrix,
is an upper triangular matrix. A little bit of algebraic manipulation, gives us a symmetric matrix $B=K^{-t}K^{-1}$ which has a nice interpretation and it's sufficient for finding $K$. Anyway, to find $K$, you will take photos of a checkerboard pattern and generally, you arrive at a linear system like $A_{n times 6} times b_{6 times 1}=0_{n times 1}$ with the additional constraint that $|vec{b}|=1$ (to avoid the trivial answer). Here are some numerical results that I have obtained for $B$ after running the algorithm on synthesized checkerboard photos:
begin{bmatrix}
0.000000082076150 && -0.000000000008003 && -0.000037912894906 \
-0.000000000008003 && 0.000000071823158 && -0.000055278469079 \
-0.000037912894906 && -0.000055278469079 && 0.999999997753446 \
end{bmatrix}
begin{bmatrix}
-0.000000104164118 && -0.000000000027239 && 0.000053428189068 \
-0.000000000027239 && -0.000000091142604 && 0.000067709246949 \
0.000053428189068 && 0.000067709246949 && -0.999999996280434
end{bmatrix}
begin{bmatrix}
0.000000109630415 && 0.000000000051933 && -0.000056355404234 \
0.000000000051933 && 0.000000095949976 && -0.000071441815015 \
-0.000056355404234 && -0.000071441815015 && 0.999999995860057
end{bmatrix}
Since $K$ is intrinsic and it only depends on the structure of the camera itself, the values we find for $p_x$, $p_y$, $f_x$ and $f_y$ must remain close to each other. Unfortunately, using the above matrices, sometimes $p_x$ and $p_y$ are minus their actual values. I blame the sign inconsistency of SVD decomposition for this.
linear-algebra matlab svd
asked Dec 14 '18 at 19:46
stressed outstressed out
6,5231939
$endgroup$
There are many applications in applied mathematics where the SVD of a matrix comes in handy. For example, consider the problem where we want to find an approximate solution to a(n) (overdetermined) linear system of equations $Avec{x}=0$ subject to $|vec{x}|=1$. It can be shown that the last column of $V$ in $A = UDV^t$ is the solution to this system subject to $|vec{x}| = 1$.
The problem is that the SVD of a matrix is not unique. $U$ and $V$ are orthonormal matrices but we still have freedom in choosing signs. In cases like this, how can I do something that resolves the ambiguity? Is there a trick or a natural convention for the signs that ensures I always get the same answer no matter what?
In particular, what can I do in MATLAB to avoid this ambiguity?
Edit:
A specific example where non-uniquess can become an issue:
Suppose that you want to measure the intrinsic parameters of a pinhole camera. It turns out that in practical cases, $K$, the calibration matrix,
is an upper triangular matrix. A little bit of algebraic manipulation, gives us a symmetric matrix $B=K^{-t}K^{-1}$ which has a nice interpretation and it's sufficient for finding $K$. Anyway, to find $K$, you will take photos of a checkerboard pattern and generally, you arrive at a linear system like $A_{n times 6} times b_{6 times 1}=0_{n times 1}$ with the additional constraint that $|vec{b}|=1$ (to avoid the trivial answer). Here are some numerical results that I have obtained for $B$ after running the algorithm on synthesized checkerboard photos:
begin{bmatrix}
0.000000082076150 && -0.000000000008003 && -0.000037912894906 \
-0.000000000008003 && 0.000000071823158 && -0.000055278469079 \
-0.000037912894906 && -0.000055278469079 && 0.999999997753446 \
end{bmatrix}
begin{bmatrix}
-0.000000104164118 && -0.000000000027239 && 0.000053428189068 \
-0.000000000027239 && -0.000000091142604 && 0.000067709246949 \
0.000053428189068 && 0.000067709246949 && -0.999999996280434
end{bmatrix}
begin{bmatrix}
0.000000109630415 && 0.000000000051933 && -0.000056355404234 \
0.000000000051933 && 0.000000095949976 && -0.000071441815015 \
-0.000056355404234 && -0.000071441815015 && 0.999999995860057
end{bmatrix}
Since $K$ is intrinsic and it only depends on the structure of the camera itself, the values we find for $p_x$, $p_y$, $f_x$ and $f_y$ must remain close to each other. Unfortunately, using the above matrices, sometimes $p_x$ and $p_y$ are minus their actual values. I blame the sign inconsistency of SVD decomposition for this.
linear-algebra matlab svd
linear-algebra matlab svd
asked Dec 14 '18 at 19:46
stressed outstressed out
6,5231939
asked Dec 14 '18 at 19:46
stressed outstressed out
6,5231939
edited Dec 14 '18 at 20:54
stressed out
asked Dec 14 '18 at 19:46
stressed outstressed out
6,5231939
asked Dec 14 '18 at 19:46
stressed outstressed out
6,5231939
asked Dec 14 '18 at 19:46
stressed outstressed out
6,5231939
6,5231939
1
$begingroup$
Can you be a bit more specific as to how non-uniqueness becomes a problem?
$endgroup$
– Omnomnomnom
Dec 14 '18 at 19:59
1
$begingroup$
Enforce a positive determinant for $U$ and the ambiguity is gone.
$endgroup$
– Yves Daoust
Dec 14 '18 at 20:23
$begingroup$
Yep, my bad. You could enforce a particular element being positive, but this doesn't work when the element is zero. This is why I suggested a determinant.
$endgroup$
– Yves Daoust
Dec 14 '18 at 20:29
1
$begingroup$
@stressedout How are you getting multiple measurements for the intrinsic parameters? As I recall, the procedure for measuring them consists of taking several photos from different angles, putting all the keypoints in a matrix, then crunching numbers with the svd to solve a problem that produces a single set of measurements. No matter how many pictures you took, they'd all go into the same single computation that is aimed toward a single set of parameters. Are you measuring multiple times and getting wildly different answers for some reason?
$endgroup$
– rschwieb
Dec 14 '18 at 21:05
1
$begingroup$
@Raaja overdetermined systems almost always are inconsistent. This is where the condition that $|x| = 1$ comes into play. $| cdot |$ here denotes the Euclidean norm, but one can use other norms. It really depends on you to choose what you're looking for. This is what rschwieb refers to as a best-fit solution.
$endgroup$
– stressed out
Dec 14 '18 at 21:11
|
show 13 more comments
1
$begingroup$
Can you be a bit more specific as to how non-uniqueness becomes a problem?
$endgroup$
– Omnomnomnom
Dec 14 '18 at 19:59
1
$begingroup$
Enforce a positive determinant for $U$ and the ambiguity is gone.
$endgroup$
– Yves Daoust
Dec 14 '18 at 20:23
$begingroup$
Yep, my bad. You could enforce a particular element being positive, but this doesn't work when the element is zero. This is why I suggested a determinant.
$endgroup$
– Yves Daoust
Dec 14 '18 at 20:29
1
$begingroup$
@stressedout How are you getting multiple measurements for the intrinsic parameters? As I recall, the procedure for measuring them consists of taking several photos from different angles, putting all the keypoints in a matrix, then crunching numbers with the svd to solve a problem that produces a single set of measurements. No matter how many pictures you took, they'd all go into the same single computation that is aimed toward a single set of parameters. Are you measuring multiple times and getting wildly different answers for some reason?
$endgroup$
– rschwieb
Dec 14 '18 at 21:05
1
$begingroup$
@Raaja overdetermined systems almost always are inconsistent. This is where the condition that $|x| = 1$ comes into play. $| cdot |$ here denotes the Euclidean norm, but one can use other norms. It really depends on you to choose what you're looking for. This is what rschwieb refers to as a best-fit solution.
$endgroup$
– stressed out
Dec 14 '18 at 21:11
1
1
$begingroup$
Can you be a bit more specific as to how non-uniqueness becomes a problem?
$endgroup$
– Omnomnomnom
Dec 14 '18 at 19:59
$begingroup$
Can you be a bit more specific as to how non-uniqueness becomes a problem?
$endgroup$
– Omnomnomnom
Dec 14 '18 at 19:59
1
1
$begingroup$
Enforce a positive determinant for $U$ and the ambiguity is gone.
$endgroup$
– Yves Daoust
Dec 14 '18 at 20:23
$begingroup$
Enforce a positive determinant for $U$ and the ambiguity is gone.
$endgroup$
– Yves Daoust
Dec 14 '18 at 20:23
$begingroup$
Yep, my bad. You could enforce a particular element being positive, but this doesn't work when the element is zero. This is why I suggested a determinant.
$endgroup$
– Yves Daoust
Dec 14 '18 at 20:29
$begingroup$
Yep, my bad. You could enforce a particular element being positive, but this doesn't work when the element is zero. This is why I suggested a determinant.
$endgroup$
– Yves Daoust
Dec 14 '18 at 20:29
1
1
$begingroup$
@stressedout How are you getting multiple measurements for the intrinsic parameters? As I recall, the procedure for measuring them consists of taking several photos from different angles, putting all the keypoints in a matrix, then crunching numbers with the svd to solve a problem that produces a single set of measurements. No matter how many pictures you took, they'd all go into the same single computation that is aimed toward a single set of parameters. Are you measuring multiple times and getting wildly different answers for some reason?
$endgroup$
– rschwieb
Dec 14 '18 at 21:05
$begingroup$
@stressedout How are you getting multiple measurements for the intrinsic parameters? As I recall, the procedure for measuring them consists of taking several photos from different angles, putting all the keypoints in a matrix, then crunching numbers with the svd to solve a problem that produces a single set of measurements. No matter how many pictures you took, they'd all go into the same single computation that is aimed toward a single set of parameters. Are you measuring multiple times and getting wildly different answers for some reason?
$endgroup$
– rschwieb
Dec 14 '18 at 21:05
1
1
$begingroup$
@Raaja overdetermined systems almost always are inconsistent. This is where the condition that $|x| = 1$ comes into play. $| cdot |$ here denotes the Euclidean norm, but one can use other norms. It really depends on you to choose what you're looking for. This is what rschwieb refers to as a best-fit solution.
$endgroup$
– stressed out
Dec 14 '18 at 21:11
$begingroup$
@Raaja overdetermined systems almost always are inconsistent. This is where the condition that $|x| = 1$ comes into play. $| cdot |$ here denotes the Euclidean norm, but one can use other norms. It really depends on you to choose what you're looking for. This is what rschwieb refers to as a best-fit solution.
$endgroup$
– stressed out
Dec 14 '18 at 21:11
|
show 13 more comments
0
active
oldest
votes
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%2f3039817%2fhow-to-deal-with-the-non-uniqueness-of-svd-in-numerical-applications%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
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%2f3039817%2fhow-to-deal-with-the-non-uniqueness-of-svd-in-numerical-applications%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
1
$begingroup$
Can you be a bit more specific as to how non-uniqueness becomes a problem?
$endgroup$
– Omnomnomnom
Dec 14 '18 at 19:59
1
$begingroup$
Enforce a positive determinant for $U$ and the ambiguity is gone.
$endgroup$
– Yves Daoust
Dec 14 '18 at 20:23
$begingroup$
Yep, my bad. You could enforce a particular element being positive, but this doesn't work when the element is zero. This is why I suggested a determinant.
$endgroup$
– Yves Daoust
Dec 14 '18 at 20:29
1
$begingroup$
@stressedout How are you getting multiple measurements for the intrinsic parameters? As I recall, the procedure for measuring them consists of taking several photos from different angles, putting all the keypoints in a matrix, then crunching numbers with the svd to solve a problem that produces a single set of measurements. No matter how many pictures you took, they'd all go into the same single computation that is aimed toward a single set of parameters. Are you measuring multiple times and getting wildly different answers for some reason?
$endgroup$
– rschwieb
Dec 14 '18 at 21:05
1
$begingroup$
@Raaja overdetermined systems almost always are inconsistent. This is where the condition that $|x| = 1$ comes into play. $| cdot |$ here denotes the Euclidean norm, but one can use other norms. It really depends on you to choose what you're looking for. This is what rschwieb refers to as a best-fit solution.
$endgroup$
– stressed out
Dec 14 '18 at 21:11