Mixing
Lower bound for distance between matrices from singular values
$begingroup$
Let $A,B in mathbb{C}^{n times m}$ be rank $r$ matrices and let
$$
A=U_A Sigma_A V_A^* quad quad quad B=U_B Sigma_B V_B^*
$$
be the singular value decompositions for $A$ and $B$, and diagonal entries of $Sigma_A$ and $Sigma_B$ are ordered from largest to smallest
I would like to show
$$
|A-B| geq |Sigma_A-Sigma_B|
$$
where $|cdot |$ is the Frobenius norm or the spectral norm. (I'd prefer to do it for both eventually.)
So far I have found that for the Frobenius norm the problem is closely related to the orthogonal Procrustes problem. Since the spectral and frobenius norm are invariant under left or right unitary multiplication we can assume $A=Sigma_A$. If we further take $U_B=I$ or $V_B=I$ then the result flows from the linked wiki.
Using a similar approach to the wiki I have shown that for the Frobenius norm it is equivalent to show that
$$
tr(U Sigma_A V Sigma_B) leq tr(Sigma_A Sigma_B)
$$
for any unitaries $U$ and $V$, where $tr$ is the trace.
I have had less success working with the spectral norm, but generated several million matrix pairs across chosen values of $n,m,r$ and did not find a counter example.
I did show the bound holds in the rank one case.
linear-algebra
asked Jan 24 at 15:35
EricEric
3819
$endgroup$
add a comment |
$begingroup$
Let $A,B in mathbb{C}^{n times m}$ be rank $r$ matrices and let
$$
A=U_A Sigma_A V_A^* quad quad quad B=U_B Sigma_B V_B^*
$$
be the singular value decompositions for $A$ and $B$, and diagonal entries of $Sigma_A$ and $Sigma_B$ are ordered from largest to smallest
I would like to show
$$
|A-B| geq |Sigma_A-Sigma_B|
$$
where $|cdot |$ is the Frobenius norm or the spectral norm. (I'd prefer to do it for both eventually.)
So far I have found that for the Frobenius norm the problem is closely related to the orthogonal Procrustes problem. Since the spectral and frobenius norm are invariant under left or right unitary multiplication we can assume $A=Sigma_A$. If we further take $U_B=I$ or $V_B=I$ then the result flows from the linked wiki.
Using a similar approach to the wiki I have shown that for the Frobenius norm it is equivalent to show that
$$
tr(U Sigma_A V Sigma_B) leq tr(Sigma_A Sigma_B)
$$
for any unitaries $U$ and $V$, where $tr$ is the trace.
I have had less success working with the spectral norm, but generated several million matrix pairs across chosen values of $n,m,r$ and did not find a counter example.
I did show the bound holds in the rank one case.
linear-algebra
asked Jan 24 at 15:35
EricEric
3819
$endgroup$
$begingroup$
Presumably you're using the convention in SVD that the singular values are listed in decreasing order. Otherwise you could have $A=B$ but $Sigma_A ne Sigma_B$.
$endgroup$
– Robert Israel
Jan 24 at 15:46
$begingroup$
Yes, singular values are ordered here. I'll edit for clarity
$endgroup$
– Eric
Jan 24 at 15:51
$begingroup$
@Eric: Were you able to solve this? I have also shown that $ | A - B |_F geq | Sigma_A - Sigma_B |_F$, but stuck on the spectral norm.
$endgroup$
– VHarisop
Feb 12 at 4:01
$begingroup$
@VHarisop Unfortunately I have not managed to solve it for the spectral norm. The frob norm is good enough form my setting, so I not thinking about it much anymore, although I ideally think about it sometimes. I'll post here if I figure it out at some point. I'd certainly still be interested in seeing a solution if you think of one.
$endgroup$
– Eric
Feb 13 at 9:24
add a comment |
$begingroup$
Let $A,B in mathbb{C}^{n times m}$ be rank $r$ matrices and let
$$
A=U_A Sigma_A V_A^* quad quad quad B=U_B Sigma_B V_B^*
$$
be the singular value decompositions for $A$ and $B$, and diagonal entries of $Sigma_A$ and $Sigma_B$ are ordered from largest to smallest
I would like to show
$$
|A-B| geq |Sigma_A-Sigma_B|
$$
where $|cdot |$ is the Frobenius norm or the spectral norm. (I'd prefer to do it for both eventually.)
So far I have found that for the Frobenius norm the problem is closely related to the orthogonal Procrustes problem. Since the spectral and frobenius norm are invariant under left or right unitary multiplication we can assume $A=Sigma_A$. If we further take $U_B=I$ or $V_B=I$ then the result flows from the linked wiki.
Using a similar approach to the wiki I have shown that for the Frobenius norm it is equivalent to show that
$$
tr(U Sigma_A V Sigma_B) leq tr(Sigma_A Sigma_B)
$$
for any unitaries $U$ and $V$, where $tr$ is the trace.
I have had less success working with the spectral norm, but generated several million matrix pairs across chosen values of $n,m,r$ and did not find a counter example.
I did show the bound holds in the rank one case.
linear-algebra
asked Jan 24 at 15:35
EricEric
3819
$endgroup$
Let $A,B in mathbb{C}^{n times m}$ be rank $r$ matrices and let
$$
A=U_A Sigma_A V_A^* quad quad quad B=U_B Sigma_B V_B^*
$$
be the singular value decompositions for $A$ and $B$, and diagonal entries of $Sigma_A$ and $Sigma_B$ are ordered from largest to smallest
I would like to show
$$
|A-B| geq |Sigma_A-Sigma_B|
$$
where $|cdot |$ is the Frobenius norm or the spectral norm. (I'd prefer to do it for both eventually.)
So far I have found that for the Frobenius norm the problem is closely related to the orthogonal Procrustes problem. Since the spectral and frobenius norm are invariant under left or right unitary multiplication we can assume $A=Sigma_A$. If we further take $U_B=I$ or $V_B=I$ then the result flows from the linked wiki.
Using a similar approach to the wiki I have shown that for the Frobenius norm it is equivalent to show that
$$
tr(U Sigma_A V Sigma_B) leq tr(Sigma_A Sigma_B)
$$
for any unitaries $U$ and $V$, where $tr$ is the trace.
I have had less success working with the spectral norm, but generated several million matrix pairs across chosen values of $n,m,r$ and did not find a counter example.
I did show the bound holds in the rank one case.
linear-algebra
linear-algebra
asked Jan 24 at 15:35
EricEric
3819
asked Jan 24 at 15:35
EricEric
3819
edited Jan 24 at 15:53
Eric
asked Jan 24 at 15:35
EricEric
3819
asked Jan 24 at 15:35
EricEric
3819
asked Jan 24 at 15:35
EricEric
3819
3819
$begingroup$
Presumably you're using the convention in SVD that the singular values are listed in decreasing order. Otherwise you could have $A=B$ but $Sigma_A ne Sigma_B$.
$endgroup$
– Robert Israel
Jan 24 at 15:46
$begingroup$
Yes, singular values are ordered here. I'll edit for clarity
$endgroup$
– Eric
Jan 24 at 15:51
$begingroup$
@Eric: Were you able to solve this? I have also shown that $ | A - B |_F geq | Sigma_A - Sigma_B |_F$, but stuck on the spectral norm.
$endgroup$
– VHarisop
Feb 12 at 4:01
$begingroup$
@VHarisop Unfortunately I have not managed to solve it for the spectral norm. The frob norm is good enough form my setting, so I not thinking about it much anymore, although I ideally think about it sometimes. I'll post here if I figure it out at some point. I'd certainly still be interested in seeing a solution if you think of one.
$endgroup$
– Eric
Feb 13 at 9:24
add a comment |
$begingroup$
Presumably you're using the convention in SVD that the singular values are listed in decreasing order. Otherwise you could have $A=B$ but $Sigma_A ne Sigma_B$.
$endgroup$
– Robert Israel
Jan 24 at 15:46
$begingroup$
Yes, singular values are ordered here. I'll edit for clarity
$endgroup$
– Eric
Jan 24 at 15:51
$begingroup$
@Eric: Were you able to solve this? I have also shown that $ | A - B |_F geq | Sigma_A - Sigma_B |_F$, but stuck on the spectral norm.
$endgroup$
– VHarisop
Feb 12 at 4:01
$begingroup$
@VHarisop Unfortunately I have not managed to solve it for the spectral norm. The frob norm is good enough form my setting, so I not thinking about it much anymore, although I ideally think about it sometimes. I'll post here if I figure it out at some point. I'd certainly still be interested in seeing a solution if you think of one.
$endgroup$
– Eric
Feb 13 at 9:24
$begingroup$
Presumably you're using the convention in SVD that the singular values are listed in decreasing order. Otherwise you could have $A=B$ but $Sigma_A ne Sigma_B$.
$endgroup$
– Robert Israel
Jan 24 at 15:46
$begingroup$
Presumably you're using the convention in SVD that the singular values are listed in decreasing order. Otherwise you could have $A=B$ but $Sigma_A ne Sigma_B$.
$endgroup$
– Robert Israel
Jan 24 at 15:46
$begingroup$
Yes, singular values are ordered here. I'll edit for clarity
$endgroup$
– Eric
Jan 24 at 15:51
$begingroup$
Yes, singular values are ordered here. I'll edit for clarity
$endgroup$
– Eric
Jan 24 at 15:51
$begingroup$
@Eric: Were you able to solve this? I have also shown that $ | A - B |_F geq | Sigma_A - Sigma_B |_F$, but stuck on the spectral norm.
$endgroup$
– VHarisop
Feb 12 at 4:01
$begingroup$
@Eric: Were you able to solve this? I have also shown that $ | A - B |_F geq | Sigma_A - Sigma_B |_F$, but stuck on the spectral norm.
$endgroup$
– VHarisop
Feb 12 at 4:01
$begingroup$
@VHarisop Unfortunately I have not managed to solve it for the spectral norm. The frob norm is good enough form my setting, so I not thinking about it much anymore, although I ideally think about it sometimes. I'll post here if I figure it out at some point. I'd certainly still be interested in seeing a solution if you think of one.
$endgroup$
– Eric
Feb 13 at 9:24
$begingroup$
@VHarisop Unfortunately I have not managed to solve it for the spectral norm. The frob norm is good enough form my setting, so I not thinking about it much anymore, although I ideally think about it sometimes. I'll post here if I figure it out at some point. I'd certainly still be interested in seeing a solution if you think of one.
$endgroup$
– Eric
Feb 13 at 9:24
add a comment |
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%2f3086000%2flower-bound-for-distance-between-matrices-from-singular-values%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%2f3086000%2flower-bound-for-distance-between-matrices-from-singular-values%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$
Presumably you're using the convention in SVD that the singular values are listed in decreasing order. Otherwise you could have $A=B$ but $Sigma_A ne Sigma_B$.
$endgroup$
– Robert Israel
Jan 24 at 15:46
$begingroup$
Yes, singular values are ordered here. I'll edit for clarity
$endgroup$
– Eric
Jan 24 at 15:51
$begingroup$
@Eric: Were you able to solve this? I have also shown that $ | A - B |_F geq | Sigma_A - Sigma_B |_F$, but stuck on the spectral norm.
$endgroup$
– VHarisop
Feb 12 at 4:01
$begingroup$
@VHarisop Unfortunately I have not managed to solve it for the spectral norm. The frob norm is good enough form my setting, so I not thinking about it much anymore, although I ideally think about it sometimes. I'll post here if I figure it out at some point. I'd certainly still be interested in seeing a solution if you think of one.
$endgroup$
– Eric
Feb 13 at 9:24