Can an upperbound constraint on the squared Frobenius norm of a matrix be expressed as a linear matrix...
$begingroup$
Is it possible to express an inequality constraint on the squared Frobenius norm of a matrix $X$:
$$|X|_F^2 = mathop{tr}( X^T X ) le t$$
as a linear matrix inequality?
I want to say that it's:
$$left[begin{array}{cc} I & X \ X^T & tIend{array}right] succcurlyeq 0$$
but I've lost confidence that this is correct since the Schur complement would be $tI - X^TX succcurlyeq 0 $ and I can't figure how the trace gets in there.
trace lmis matrix-norms
$endgroup$
add a comment |
$begingroup$
Is it possible to express an inequality constraint on the squared Frobenius norm of a matrix $X$:
$$|X|_F^2 = mathop{tr}( X^T X ) le t$$
as a linear matrix inequality?
I want to say that it's:
$$left[begin{array}{cc} I & X \ X^T & tIend{array}right] succcurlyeq 0$$
but I've lost confidence that this is correct since the Schur complement would be $tI - X^TX succcurlyeq 0 $ and I can't figure how the trace gets in there.
trace lmis matrix-norms
$endgroup$
$begingroup$
Does your round greater equal sign stand for determinant? If so than what you wrote does not work for 2 by 2 matrices (unless I made a computation error somewhere).
$endgroup$
– quarague
Jan 9 at 9:14
$begingroup$
I intended $M succcurlyeq 0$ to mean $M$ is positive semi-definite.
$endgroup$
– Alec Jacobson
Jan 9 at 15:51
$begingroup$
Positive semidefinite is equivalent to eigenvalues greater equal zero. I think that doesn't even work for 1 by 1 matrices.
$endgroup$
– quarague
Jan 9 at 16:22
1
$begingroup$
what doesn't work for 1by1? The Schur complement in that case says $t - x^2 succcurlyeq 0$ or $c (t -x^2) c ge 0, forall c$ which simply means $(t -x^2)ge 0$ which in this case is the same as $mathop{tr}(x^2) = x^2 le t$.
$endgroup$
– Alec Jacobson
Jan 9 at 18:38
add a comment |
$begingroup$
Is it possible to express an inequality constraint on the squared Frobenius norm of a matrix $X$:
$$|X|_F^2 = mathop{tr}( X^T X ) le t$$
as a linear matrix inequality?
I want to say that it's:
$$left[begin{array}{cc} I & X \ X^T & tIend{array}right] succcurlyeq 0$$
but I've lost confidence that this is correct since the Schur complement would be $tI - X^TX succcurlyeq 0 $ and I can't figure how the trace gets in there.
trace lmis matrix-norms
$endgroup$
Is it possible to express an inequality constraint on the squared Frobenius norm of a matrix $X$:
$$|X|_F^2 = mathop{tr}( X^T X ) le t$$
as a linear matrix inequality?
I want to say that it's:
$$left[begin{array}{cc} I & X \ X^T & tIend{array}right] succcurlyeq 0$$
but I've lost confidence that this is correct since the Schur complement would be $tI - X^TX succcurlyeq 0 $ and I can't figure how the trace gets in there.
trace lmis matrix-norms
trace lmis matrix-norms
asked Jan 9 at 5:14
Alec JacobsonAlec Jacobson
270111
270111
$begingroup$
Does your round greater equal sign stand for determinant? If so than what you wrote does not work for 2 by 2 matrices (unless I made a computation error somewhere).
$endgroup$
– quarague
Jan 9 at 9:14
$begingroup$
I intended $M succcurlyeq 0$ to mean $M$ is positive semi-definite.
$endgroup$
– Alec Jacobson
Jan 9 at 15:51
$begingroup$
Positive semidefinite is equivalent to eigenvalues greater equal zero. I think that doesn't even work for 1 by 1 matrices.
$endgroup$
– quarague
Jan 9 at 16:22
1
$begingroup$
what doesn't work for 1by1? The Schur complement in that case says $t - x^2 succcurlyeq 0$ or $c (t -x^2) c ge 0, forall c$ which simply means $(t -x^2)ge 0$ which in this case is the same as $mathop{tr}(x^2) = x^2 le t$.
$endgroup$
– Alec Jacobson
Jan 9 at 18:38
add a comment |
$begingroup$
Does your round greater equal sign stand for determinant? If so than what you wrote does not work for 2 by 2 matrices (unless I made a computation error somewhere).
$endgroup$
– quarague
Jan 9 at 9:14
$begingroup$
I intended $M succcurlyeq 0$ to mean $M$ is positive semi-definite.
$endgroup$
– Alec Jacobson
Jan 9 at 15:51
$begingroup$
Positive semidefinite is equivalent to eigenvalues greater equal zero. I think that doesn't even work for 1 by 1 matrices.
$endgroup$
– quarague
Jan 9 at 16:22
1
$begingroup$
what doesn't work for 1by1? The Schur complement in that case says $t - x^2 succcurlyeq 0$ or $c (t -x^2) c ge 0, forall c$ which simply means $(t -x^2)ge 0$ which in this case is the same as $mathop{tr}(x^2) = x^2 le t$.
$endgroup$
– Alec Jacobson
Jan 9 at 18:38
$begingroup$
Does your round greater equal sign stand for determinant? If so than what you wrote does not work for 2 by 2 matrices (unless I made a computation error somewhere).
$endgroup$
– quarague
Jan 9 at 9:14
$begingroup$
Does your round greater equal sign stand for determinant? If so than what you wrote does not work for 2 by 2 matrices (unless I made a computation error somewhere).
$endgroup$
– quarague
Jan 9 at 9:14
$begingroup$
I intended $M succcurlyeq 0$ to mean $M$ is positive semi-definite.
$endgroup$
– Alec Jacobson
Jan 9 at 15:51
$begingroup$
I intended $M succcurlyeq 0$ to mean $M$ is positive semi-definite.
$endgroup$
– Alec Jacobson
Jan 9 at 15:51
$begingroup$
Positive semidefinite is equivalent to eigenvalues greater equal zero. I think that doesn't even work for 1 by 1 matrices.
$endgroup$
– quarague
Jan 9 at 16:22
$begingroup$
Positive semidefinite is equivalent to eigenvalues greater equal zero. I think that doesn't even work for 1 by 1 matrices.
$endgroup$
– quarague
Jan 9 at 16:22
1
1
$begingroup$
what doesn't work for 1by1? The Schur complement in that case says $t - x^2 succcurlyeq 0$ or $c (t -x^2) c ge 0, forall c$ which simply means $(t -x^2)ge 0$ which in this case is the same as $mathop{tr}(x^2) = x^2 le t$.
$endgroup$
– Alec Jacobson
Jan 9 at 18:38
$begingroup$
what doesn't work for 1by1? The Schur complement in that case says $t - x^2 succcurlyeq 0$ or $c (t -x^2) c ge 0, forall c$ which simply means $(t -x^2)ge 0$ which in this case is the same as $mathop{tr}(x^2) = x^2 le t$.
$endgroup$
– Alec Jacobson
Jan 9 at 18:38
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
There might be a compacter and more elegant way, but one way you can represent it as LMI's is by using intermediate values for each diagonal term of $X^top X$. These can be calculated using
$$
Y_i = X,e_i
$$
with $e_i$ a vector with the $i$th element equal to one and the rest zeros (so $Y_i$ is the $i$th column of $X$), such that $Y_i^top Y_i$ is the $i$th diagonal term of $X^top X$. Then using the Schur complement you can write for every diagonal term an LMI for $Y_i^top Y_i leq alpha_i$, namely
$$
begin{bmatrix}
I & Y_i \ Y_i^top & alpha_i
end{bmatrix} succeq 0,
$$
with $alpha_i in mathbb{R}$. Now a bound for $|X|_F^2$ can be found by summing all $alpha_i$, which should be smaller or equal to $t$
$$
sum alpha_i leq t,
$$
which is also a linear inequality.
By using an intermediate LMI for $X^top X$ you might also be able to write $X^top X preceq M$, with $M = M^top$, as
$$
begin{bmatrix}
I & X \ X^top & M
end{bmatrix} succeq 0.
$$
An upper bound for $|X|_F^2$ would then be $text{Tr}(M)$, so adding the linear inequality $text{Tr}(M) leq t$ would make this system of LMI's equivalent to your problem. To show that $X^top X preceq M$ also implies that $text{Tr}(X^top X) leq text{Tr}(M)$ you can use that the trace of a matrix is equal to the sum of all its eigenvalues. Namely $X^top X preceq M$ is equivalent to $M - X^top X succeq 0$, thus $M - X^top X$ can only have non-negative eigenvalues and therefore $text{Tr}(M - X^top X)$ is the sum of these non-negative eigenvalues, which is also non-negative. The trace inequality $text{Tr}(X^top X) leq text{Tr}(M)$ is equivalent to $text{Tr}(M - X^top X) geq 0$ and in the previous sentence it was shown that it holds when $X^top X preceq M$, thus $text{Tr}(X^top X) leq text{Tr}(M)$ should hold in that case as well.
It can be noted that $M$ might add more degrees of freedom than all $alpha_i$ so might or might not be an attractive alternative of writing the problem as LMI's.
$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%2f3067103%2fcan-an-upperbound-constraint-on-the-squared-frobenius-norm-of-a-matrix-be-expres%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
There might be a compacter and more elegant way, but one way you can represent it as LMI's is by using intermediate values for each diagonal term of $X^top X$. These can be calculated using
$$
Y_i = X,e_i
$$
with $e_i$ a vector with the $i$th element equal to one and the rest zeros (so $Y_i$ is the $i$th column of $X$), such that $Y_i^top Y_i$ is the $i$th diagonal term of $X^top X$. Then using the Schur complement you can write for every diagonal term an LMI for $Y_i^top Y_i leq alpha_i$, namely
$$
begin{bmatrix}
I & Y_i \ Y_i^top & alpha_i
end{bmatrix} succeq 0,
$$
with $alpha_i in mathbb{R}$. Now a bound for $|X|_F^2$ can be found by summing all $alpha_i$, which should be smaller or equal to $t$
$$
sum alpha_i leq t,
$$
which is also a linear inequality.
By using an intermediate LMI for $X^top X$ you might also be able to write $X^top X preceq M$, with $M = M^top$, as
$$
begin{bmatrix}
I & X \ X^top & M
end{bmatrix} succeq 0.
$$
An upper bound for $|X|_F^2$ would then be $text{Tr}(M)$, so adding the linear inequality $text{Tr}(M) leq t$ would make this system of LMI's equivalent to your problem. To show that $X^top X preceq M$ also implies that $text{Tr}(X^top X) leq text{Tr}(M)$ you can use that the trace of a matrix is equal to the sum of all its eigenvalues. Namely $X^top X preceq M$ is equivalent to $M - X^top X succeq 0$, thus $M - X^top X$ can only have non-negative eigenvalues and therefore $text{Tr}(M - X^top X)$ is the sum of these non-negative eigenvalues, which is also non-negative. The trace inequality $text{Tr}(X^top X) leq text{Tr}(M)$ is equivalent to $text{Tr}(M - X^top X) geq 0$ and in the previous sentence it was shown that it holds when $X^top X preceq M$, thus $text{Tr}(X^top X) leq text{Tr}(M)$ should hold in that case as well.
It can be noted that $M$ might add more degrees of freedom than all $alpha_i$ so might or might not be an attractive alternative of writing the problem as LMI's.
$endgroup$
add a comment |
$begingroup$
There might be a compacter and more elegant way, but one way you can represent it as LMI's is by using intermediate values for each diagonal term of $X^top X$. These can be calculated using
$$
Y_i = X,e_i
$$
with $e_i$ a vector with the $i$th element equal to one and the rest zeros (so $Y_i$ is the $i$th column of $X$), such that $Y_i^top Y_i$ is the $i$th diagonal term of $X^top X$. Then using the Schur complement you can write for every diagonal term an LMI for $Y_i^top Y_i leq alpha_i$, namely
$$
begin{bmatrix}
I & Y_i \ Y_i^top & alpha_i
end{bmatrix} succeq 0,
$$
with $alpha_i in mathbb{R}$. Now a bound for $|X|_F^2$ can be found by summing all $alpha_i$, which should be smaller or equal to $t$
$$
sum alpha_i leq t,
$$
which is also a linear inequality.
By using an intermediate LMI for $X^top X$ you might also be able to write $X^top X preceq M$, with $M = M^top$, as
$$
begin{bmatrix}
I & X \ X^top & M
end{bmatrix} succeq 0.
$$
An upper bound for $|X|_F^2$ would then be $text{Tr}(M)$, so adding the linear inequality $text{Tr}(M) leq t$ would make this system of LMI's equivalent to your problem. To show that $X^top X preceq M$ also implies that $text{Tr}(X^top X) leq text{Tr}(M)$ you can use that the trace of a matrix is equal to the sum of all its eigenvalues. Namely $X^top X preceq M$ is equivalent to $M - X^top X succeq 0$, thus $M - X^top X$ can only have non-negative eigenvalues and therefore $text{Tr}(M - X^top X)$ is the sum of these non-negative eigenvalues, which is also non-negative. The trace inequality $text{Tr}(X^top X) leq text{Tr}(M)$ is equivalent to $text{Tr}(M - X^top X) geq 0$ and in the previous sentence it was shown that it holds when $X^top X preceq M$, thus $text{Tr}(X^top X) leq text{Tr}(M)$ should hold in that case as well.
It can be noted that $M$ might add more degrees of freedom than all $alpha_i$ so might or might not be an attractive alternative of writing the problem as LMI's.
$endgroup$
add a comment |
$begingroup$
There might be a compacter and more elegant way, but one way you can represent it as LMI's is by using intermediate values for each diagonal term of $X^top X$. These can be calculated using
$$
Y_i = X,e_i
$$
with $e_i$ a vector with the $i$th element equal to one and the rest zeros (so $Y_i$ is the $i$th column of $X$), such that $Y_i^top Y_i$ is the $i$th diagonal term of $X^top X$. Then using the Schur complement you can write for every diagonal term an LMI for $Y_i^top Y_i leq alpha_i$, namely
$$
begin{bmatrix}
I & Y_i \ Y_i^top & alpha_i
end{bmatrix} succeq 0,
$$
with $alpha_i in mathbb{R}$. Now a bound for $|X|_F^2$ can be found by summing all $alpha_i$, which should be smaller or equal to $t$
$$
sum alpha_i leq t,
$$
which is also a linear inequality.
By using an intermediate LMI for $X^top X$ you might also be able to write $X^top X preceq M$, with $M = M^top$, as
$$
begin{bmatrix}
I & X \ X^top & M
end{bmatrix} succeq 0.
$$
An upper bound for $|X|_F^2$ would then be $text{Tr}(M)$, so adding the linear inequality $text{Tr}(M) leq t$ would make this system of LMI's equivalent to your problem. To show that $X^top X preceq M$ also implies that $text{Tr}(X^top X) leq text{Tr}(M)$ you can use that the trace of a matrix is equal to the sum of all its eigenvalues. Namely $X^top X preceq M$ is equivalent to $M - X^top X succeq 0$, thus $M - X^top X$ can only have non-negative eigenvalues and therefore $text{Tr}(M - X^top X)$ is the sum of these non-negative eigenvalues, which is also non-negative. The trace inequality $text{Tr}(X^top X) leq text{Tr}(M)$ is equivalent to $text{Tr}(M - X^top X) geq 0$ and in the previous sentence it was shown that it holds when $X^top X preceq M$, thus $text{Tr}(X^top X) leq text{Tr}(M)$ should hold in that case as well.
It can be noted that $M$ might add more degrees of freedom than all $alpha_i$ so might or might not be an attractive alternative of writing the problem as LMI's.
$endgroup$
There might be a compacter and more elegant way, but one way you can represent it as LMI's is by using intermediate values for each diagonal term of $X^top X$. These can be calculated using
$$
Y_i = X,e_i
$$
with $e_i$ a vector with the $i$th element equal to one and the rest zeros (so $Y_i$ is the $i$th column of $X$), such that $Y_i^top Y_i$ is the $i$th diagonal term of $X^top X$. Then using the Schur complement you can write for every diagonal term an LMI for $Y_i^top Y_i leq alpha_i$, namely
$$
begin{bmatrix}
I & Y_i \ Y_i^top & alpha_i
end{bmatrix} succeq 0,
$$
with $alpha_i in mathbb{R}$. Now a bound for $|X|_F^2$ can be found by summing all $alpha_i$, which should be smaller or equal to $t$
$$
sum alpha_i leq t,
$$
which is also a linear inequality.
By using an intermediate LMI for $X^top X$ you might also be able to write $X^top X preceq M$, with $M = M^top$, as
$$
begin{bmatrix}
I & X \ X^top & M
end{bmatrix} succeq 0.
$$
An upper bound for $|X|_F^2$ would then be $text{Tr}(M)$, so adding the linear inequality $text{Tr}(M) leq t$ would make this system of LMI's equivalent to your problem. To show that $X^top X preceq M$ also implies that $text{Tr}(X^top X) leq text{Tr}(M)$ you can use that the trace of a matrix is equal to the sum of all its eigenvalues. Namely $X^top X preceq M$ is equivalent to $M - X^top X succeq 0$, thus $M - X^top X$ can only have non-negative eigenvalues and therefore $text{Tr}(M - X^top X)$ is the sum of these non-negative eigenvalues, which is also non-negative. The trace inequality $text{Tr}(X^top X) leq text{Tr}(M)$ is equivalent to $text{Tr}(M - X^top X) geq 0$ and in the previous sentence it was shown that it holds when $X^top X preceq M$, thus $text{Tr}(X^top X) leq text{Tr}(M)$ should hold in that case as well.
It can be noted that $M$ might add more degrees of freedom than all $alpha_i$ so might or might not be an attractive alternative of writing the problem as LMI's.
edited Jan 10 at 16:54
answered Jan 10 at 15:26
Kwin van der VeenKwin van der Veen
5,6402828
5,6402828
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%2f3067103%2fcan-an-upperbound-constraint-on-the-squared-frobenius-norm-of-a-matrix-be-expres%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$
Does your round greater equal sign stand for determinant? If so than what you wrote does not work for 2 by 2 matrices (unless I made a computation error somewhere).
$endgroup$
– quarague
Jan 9 at 9:14
$begingroup$
I intended $M succcurlyeq 0$ to mean $M$ is positive semi-definite.
$endgroup$
– Alec Jacobson
Jan 9 at 15:51
$begingroup$
Positive semidefinite is equivalent to eigenvalues greater equal zero. I think that doesn't even work for 1 by 1 matrices.
$endgroup$
– quarague
Jan 9 at 16:22
1
$begingroup$
what doesn't work for 1by1? The Schur complement in that case says $t - x^2 succcurlyeq 0$ or $c (t -x^2) c ge 0, forall c$ which simply means $(t -x^2)ge 0$ which in this case is the same as $mathop{tr}(x^2) = x^2 le t$.
$endgroup$
– Alec Jacobson
Jan 9 at 18:38