Mixing
How to formulate $min |X-z^Tmathbf{1}^T|$ as a least-squares problem?
$begingroup$
Suppose $X in mathbb{R}^{mtimes n}$, i.e., there are $n$ columns. Some of columns of $X$ are known, some of columns of $X$ are unknown (variables). Suppose I have $$min_{x,z} |X-zmathbf{1}^T|^2_2$$
where $zin mathbb{R}^{m}, mathbf{1}in mathbb{R}^n$. So the optimization variables are those unknown columns $x$ and $z$.
How to show that this can be written as a least-squares problem? And what is the (geometric) meaning of $z$?
Please advise. Thanks!
convex-optimization linear-programming least-squares
edited Jan 19 at 9:38
Rodrigo de Azevedo
13k41959
asked Oct 19 '18 at 18:37
DennyDenny
31729
$endgroup$
add a comment |
$begingroup$
Suppose $X in mathbb{R}^{mtimes n}$, i.e., there are $n$ columns. Some of columns of $X$ are known, some of columns of $X$ are unknown (variables). Suppose I have $$min_{x,z} |X-zmathbf{1}^T|^2_2$$
where $zin mathbb{R}^{m}, mathbf{1}in mathbb{R}^n$. So the optimization variables are those unknown columns $x$ and $z$.
How to show that this can be written as a least-squares problem? And what is the (geometric) meaning of $z$?
Please advise. Thanks!
convex-optimization linear-programming least-squares
edited Jan 19 at 9:38
Rodrigo de Azevedo
13k41959
asked Oct 19 '18 at 18:37
DennyDenny
31729
$endgroup$
1
$begingroup$
This isn't a least-squares problem for the standard interpretation of $|cdot|_2$ for matrices—the induced 2-norm; i.e., the spectral norm. It is if you change it to $|cdot|_F$, the Frobenius norm.
$endgroup$
– Michael Grant
Oct 19 '18 at 20:24
$begingroup$
@MichaelGrant Thanks, I will check this. If that is a Frobenius norm, how to transform that to a least-squares problem? a hint please and thanks!
$endgroup$
– Denny
Oct 19 '18 at 20:31
1
$begingroup$
I believe mathreadler is on the right track already. By converting the problem to a vector, it is valid to use the 2-norm.
$endgroup$
– Michael Grant
Oct 19 '18 at 20:32
$begingroup$
I see what you meant now. ;) Yes it will work for this problem too.
$endgroup$
– mathreadler
Oct 22 '18 at 13:49
add a comment |
$begingroup$
Suppose $X in mathbb{R}^{mtimes n}$, i.e., there are $n$ columns. Some of columns of $X$ are known, some of columns of $X$ are unknown (variables). Suppose I have $$min_{x,z} |X-zmathbf{1}^T|^2_2$$
where $zin mathbb{R}^{m}, mathbf{1}in mathbb{R}^n$. So the optimization variables are those unknown columns $x$ and $z$.
How to show that this can be written as a least-squares problem? And what is the (geometric) meaning of $z$?
Please advise. Thanks!
convex-optimization linear-programming least-squares
edited Jan 19 at 9:38
Rodrigo de Azevedo
13k41959
asked Oct 19 '18 at 18:37
DennyDenny
31729
$endgroup$
Suppose $X in mathbb{R}^{mtimes n}$, i.e., there are $n$ columns. Some of columns of $X$ are known, some of columns of $X$ are unknown (variables). Suppose I have $$min_{x,z} |X-zmathbf{1}^T|^2_2$$
where $zin mathbb{R}^{m}, mathbf{1}in mathbb{R}^n$. So the optimization variables are those unknown columns $x$ and $z$.
How to show that this can be written as a least-squares problem? And what is the (geometric) meaning of $z$?
Please advise. Thanks!
convex-optimization linear-programming least-squares
convex-optimization linear-programming least-squares
edited Jan 19 at 9:38
Rodrigo de Azevedo
13k41959
asked Oct 19 '18 at 18:37
DennyDenny
31729
edited Jan 19 at 9:38
Rodrigo de Azevedo
13k41959
asked Oct 19 '18 at 18:37
DennyDenny
31729
edited Jan 19 at 9:38
Rodrigo de Azevedo
13k41959
edited Jan 19 at 9:38
Rodrigo de Azevedo
13k41959
edited Jan 19 at 9:38
Rodrigo de Azevedo
13k41959
13k41959
asked Oct 19 '18 at 18:37
DennyDenny
31729
asked Oct 19 '18 at 18:37
DennyDenny
31729
asked Oct 19 '18 at 18:37
DennyDenny
31729
31729
1
$begingroup$
This isn't a least-squares problem for the standard interpretation of $|cdot|_2$ for matrices—the induced 2-norm; i.e., the spectral norm. It is if you change it to $|cdot|_F$, the Frobenius norm.
$endgroup$
– Michael Grant
Oct 19 '18 at 20:24
$begingroup$
@MichaelGrant Thanks, I will check this. If that is a Frobenius norm, how to transform that to a least-squares problem? a hint please and thanks!
$endgroup$
– Denny
Oct 19 '18 at 20:31
1
$begingroup$
I believe mathreadler is on the right track already. By converting the problem to a vector, it is valid to use the 2-norm.
$endgroup$
– Michael Grant
Oct 19 '18 at 20:32
$begingroup$
I see what you meant now. ;) Yes it will work for this problem too.
$endgroup$
– mathreadler
Oct 22 '18 at 13:49
add a comment |
1
$begingroup$
This isn't a least-squares problem for the standard interpretation of $|cdot|_2$ for matrices—the induced 2-norm; i.e., the spectral norm. It is if you change it to $|cdot|_F$, the Frobenius norm.
$endgroup$
– Michael Grant
Oct 19 '18 at 20:24
$begingroup$
@MichaelGrant Thanks, I will check this. If that is a Frobenius norm, how to transform that to a least-squares problem? a hint please and thanks!
$endgroup$
– Denny
Oct 19 '18 at 20:31
1
$begingroup$
I believe mathreadler is on the right track already. By converting the problem to a vector, it is valid to use the 2-norm.
$endgroup$
– Michael Grant
Oct 19 '18 at 20:32
$begingroup$
I see what you meant now. ;) Yes it will work for this problem too.
$endgroup$
– mathreadler
Oct 22 '18 at 13:49
1
1
$begingroup$
This isn't a least-squares problem for the standard interpretation of $|cdot|_2$ for matrices—the induced 2-norm; i.e., the spectral norm. It is if you change it to $|cdot|_F$, the Frobenius norm.
$endgroup$
– Michael Grant
Oct 19 '18 at 20:24
$begingroup$
This isn't a least-squares problem for the standard interpretation of $|cdot|_2$ for matrices—the induced 2-norm; i.e., the spectral norm. It is if you change it to $|cdot|_F$, the Frobenius norm.
$endgroup$
– Michael Grant
Oct 19 '18 at 20:24
$begingroup$
@MichaelGrant Thanks, I will check this. If that is a Frobenius norm, how to transform that to a least-squares problem? a hint please and thanks!
$endgroup$
– Denny
Oct 19 '18 at 20:31
$begingroup$
@MichaelGrant Thanks, I will check this. If that is a Frobenius norm, how to transform that to a least-squares problem? a hint please and thanks!
$endgroup$
– Denny
Oct 19 '18 at 20:31
1
1
$begingroup$
I believe mathreadler is on the right track already. By converting the problem to a vector, it is valid to use the 2-norm.
$endgroup$
– Michael Grant
Oct 19 '18 at 20:32
$begingroup$
I believe mathreadler is on the right track already. By converting the problem to a vector, it is valid to use the 2-norm.
$endgroup$
– Michael Grant
Oct 19 '18 at 20:32
$begingroup$
I see what you meant now. ;) Yes it will work for this problem too.
$endgroup$
– mathreadler
Oct 22 '18 at 13:49
$begingroup$
I see what you meant now. ;) Yes it will work for this problem too.
$endgroup$
– mathreadler
Oct 22 '18 at 13:49
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
First vectorize $X$ and $z$ together in some way, for example $$text{vec}(X,z) = [text{vec}(X),text{vec}(z)]^T$$I will assume this vectorization (first orders all elements of $X$ and then all elements of $z$). Then build
$$A=[M_I,M_{-1^T}]$$
Where $M$ is matrix representation of "multiplied with" subscript.
Here you can use Kronecker products to your help.
Now you want to minimize
$$|A text{vec}(X,z)|_2^2$$
To encode the $X$ values being known, just add a term like this:
$$|C(text{vec}(X,z)-p)|_2^2$$
Where $C$ is diagonal matrix encoding which values are known (large positive values if known, $epsilon>0$ otherwise), and $p$ vector contains those values.
answered Oct 19 '18 at 19:27
mathreadlermathreadler
15k72263
$endgroup$
$begingroup$
I am still confused about $M_I$ and $M_{-1^T}$. And should the last line be $|A-vec(X,z)|_2^2$? In my original problem, some columns of $X$ are known, some unknown; how do you deal with this in your answer? Thanks!
$endgroup$
– Denny
Oct 19 '18 at 19:40
$begingroup$
The $A$ matrix will automatically do the - between $X$ and $z$ term when you multiply with it. Ok I will add info for X values being known.
$endgroup$
– mathreadler
Oct 19 '18 at 19:53
$begingroup$
You say for the X values being known, add that term. Where do you add that term?
$endgroup$
– Denny
Oct 19 '18 at 20:21
$begingroup$
@Denny it was unlucky formulation. I rewrote the sentence.
$endgroup$
– mathreadler
Oct 19 '18 at 20:39
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%2f2962434%2fhow-to-formulate-min-x-zt-mathbf1t-as-a-least-squares-problem%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$
First vectorize $X$ and $z$ together in some way, for example $$text{vec}(X,z) = [text{vec}(X),text{vec}(z)]^T$$I will assume this vectorization (first orders all elements of $X$ and then all elements of $z$). Then build
$$A=[M_I,M_{-1^T}]$$
Where $M$ is matrix representation of "multiplied with" subscript.
Here you can use Kronecker products to your help.
Now you want to minimize
$$|A text{vec}(X,z)|_2^2$$
To encode the $X$ values being known, just add a term like this:
$$|C(text{vec}(X,z)-p)|_2^2$$
Where $C$ is diagonal matrix encoding which values are known (large positive values if known, $epsilon>0$ otherwise), and $p$ vector contains those values.
answered Oct 19 '18 at 19:27
mathreadlermathreadler
15k72263
$endgroup$
$begingroup$
I am still confused about $M_I$ and $M_{-1^T}$. And should the last line be $|A-vec(X,z)|_2^2$? In my original problem, some columns of $X$ are known, some unknown; how do you deal with this in your answer? Thanks!
$endgroup$
– Denny
Oct 19 '18 at 19:40
$begingroup$
The $A$ matrix will automatically do the - between $X$ and $z$ term when you multiply with it. Ok I will add info for X values being known.
$endgroup$
– mathreadler
Oct 19 '18 at 19:53
$begingroup$
You say for the X values being known, add that term. Where do you add that term?
$endgroup$
– Denny
Oct 19 '18 at 20:21
$begingroup$
@Denny it was unlucky formulation. I rewrote the sentence.
$endgroup$
– mathreadler
Oct 19 '18 at 20:39
add a comment |
$begingroup$
First vectorize $X$ and $z$ together in some way, for example $$text{vec}(X,z) = [text{vec}(X),text{vec}(z)]^T$$I will assume this vectorization (first orders all elements of $X$ and then all elements of $z$). Then build
$$A=[M_I,M_{-1^T}]$$
Where $M$ is matrix representation of "multiplied with" subscript.
Here you can use Kronecker products to your help.
Now you want to minimize
$$|A text{vec}(X,z)|_2^2$$
To encode the $X$ values being known, just add a term like this:
$$|C(text{vec}(X,z)-p)|_2^2$$
Where $C$ is diagonal matrix encoding which values are known (large positive values if known, $epsilon>0$ otherwise), and $p$ vector contains those values.
answered Oct 19 '18 at 19:27
mathreadlermathreadler
15k72263
$endgroup$
$begingroup$
I am still confused about $M_I$ and $M_{-1^T}$. And should the last line be $|A-vec(X,z)|_2^2$? In my original problem, some columns of $X$ are known, some unknown; how do you deal with this in your answer? Thanks!
$endgroup$
– Denny
Oct 19 '18 at 19:40
$begingroup$
The $A$ matrix will automatically do the - between $X$ and $z$ term when you multiply with it. Ok I will add info for X values being known.
$endgroup$
– mathreadler
Oct 19 '18 at 19:53
$begingroup$
You say for the X values being known, add that term. Where do you add that term?
$endgroup$
– Denny
Oct 19 '18 at 20:21
$begingroup$
@Denny it was unlucky formulation. I rewrote the sentence.
$endgroup$
– mathreadler
Oct 19 '18 at 20:39
add a comment |
$begingroup$
First vectorize $X$ and $z$ together in some way, for example $$text{vec}(X,z) = [text{vec}(X),text{vec}(z)]^T$$I will assume this vectorization (first orders all elements of $X$ and then all elements of $z$). Then build
$$A=[M_I,M_{-1^T}]$$
Where $M$ is matrix representation of "multiplied with" subscript.
Here you can use Kronecker products to your help.
Now you want to minimize
$$|A text{vec}(X,z)|_2^2$$
To encode the $X$ values being known, just add a term like this:
$$|C(text{vec}(X,z)-p)|_2^2$$
Where $C$ is diagonal matrix encoding which values are known (large positive values if known, $epsilon>0$ otherwise), and $p$ vector contains those values.
answered Oct 19 '18 at 19:27
mathreadlermathreadler
15k72263
$endgroup$
First vectorize $X$ and $z$ together in some way, for example $$text{vec}(X,z) = [text{vec}(X),text{vec}(z)]^T$$I will assume this vectorization (first orders all elements of $X$ and then all elements of $z$). Then build
$$A=[M_I,M_{-1^T}]$$
Where $M$ is matrix representation of "multiplied with" subscript.
Here you can use Kronecker products to your help.
Now you want to minimize
$$|A text{vec}(X,z)|_2^2$$
To encode the $X$ values being known, just add a term like this:
$$|C(text{vec}(X,z)-p)|_2^2$$
Where $C$ is diagonal matrix encoding which values are known (large positive values if known, $epsilon>0$ otherwise), and $p$ vector contains those values.
answered Oct 19 '18 at 19:27
mathreadlermathreadler
15k72263
edited Oct 20 '18 at 7:06
answered Oct 19 '18 at 19:27
mathreadlermathreadler
15k72263
answered Oct 19 '18 at 19:27
mathreadlermathreadler
15k72263
answered Oct 19 '18 at 19:27
mathreadlermathreadler
15k72263
15k72263
$begingroup$
I am still confused about $M_I$ and $M_{-1^T}$. And should the last line be $|A-vec(X,z)|_2^2$? In my original problem, some columns of $X$ are known, some unknown; how do you deal with this in your answer? Thanks!
$endgroup$
– Denny
Oct 19 '18 at 19:40
$begingroup$
The $A$ matrix will automatically do the - between $X$ and $z$ term when you multiply with it. Ok I will add info for X values being known.
$endgroup$
– mathreadler
Oct 19 '18 at 19:53
$begingroup$
You say for the X values being known, add that term. Where do you add that term?
$endgroup$
– Denny
Oct 19 '18 at 20:21
$begingroup$
@Denny it was unlucky formulation. I rewrote the sentence.
$endgroup$
– mathreadler
Oct 19 '18 at 20:39
add a comment |
$begingroup$
I am still confused about $M_I$ and $M_{-1^T}$. And should the last line be $|A-vec(X,z)|_2^2$? In my original problem, some columns of $X$ are known, some unknown; how do you deal with this in your answer? Thanks!
$endgroup$
– Denny
Oct 19 '18 at 19:40
$begingroup$
The $A$ matrix will automatically do the - between $X$ and $z$ term when you multiply with it. Ok I will add info for X values being known.
$endgroup$
– mathreadler
Oct 19 '18 at 19:53
$begingroup$
You say for the X values being known, add that term. Where do you add that term?
$endgroup$
– Denny
Oct 19 '18 at 20:21
$begingroup$
@Denny it was unlucky formulation. I rewrote the sentence.
$endgroup$
– mathreadler
Oct 19 '18 at 20:39
$begingroup$
I am still confused about $M_I$ and $M_{-1^T}$. And should the last line be $|A-vec(X,z)|_2^2$? In my original problem, some columns of $X$ are known, some unknown; how do you deal with this in your answer? Thanks!
$endgroup$
– Denny
Oct 19 '18 at 19:40
$begingroup$
I am still confused about $M_I$ and $M_{-1^T}$. And should the last line be $|A-vec(X,z)|_2^2$? In my original problem, some columns of $X$ are known, some unknown; how do you deal with this in your answer? Thanks!
$endgroup$
– Denny
Oct 19 '18 at 19:40
$begingroup$
The $A$ matrix will automatically do the - between $X$ and $z$ term when you multiply with it. Ok I will add info for X values being known.
$endgroup$
– mathreadler
Oct 19 '18 at 19:53
$begingroup$
The $A$ matrix will automatically do the - between $X$ and $z$ term when you multiply with it. Ok I will add info for X values being known.
$endgroup$
– mathreadler
Oct 19 '18 at 19:53
$begingroup$
You say for the X values being known, add that term. Where do you add that term?
$endgroup$
– Denny
Oct 19 '18 at 20:21
$begingroup$
You say for the X values being known, add that term. Where do you add that term?
$endgroup$
– Denny
Oct 19 '18 at 20:21
$begingroup$
@Denny it was unlucky formulation. I rewrote the sentence.
$endgroup$
– mathreadler
Oct 19 '18 at 20:39
$begingroup$
@Denny it was unlucky formulation. I rewrote the sentence.
$endgroup$
– mathreadler
Oct 19 '18 at 20:39
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%2f2962434%2fhow-to-formulate-min-x-zt-mathbf1t-as-a-least-squares-problem%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$
This isn't a least-squares problem for the standard interpretation of $|cdot|_2$ for matrices—the induced 2-norm; i.e., the spectral norm. It is if you change it to $|cdot|_F$, the Frobenius norm.
$endgroup$
– Michael Grant
Oct 19 '18 at 20:24
$begingroup$
@MichaelGrant Thanks, I will check this. If that is a Frobenius norm, how to transform that to a least-squares problem? a hint please and thanks!
$endgroup$
– Denny
Oct 19 '18 at 20:31
1
$begingroup$
I believe mathreadler is on the right track already. By converting the problem to a vector, it is valid to use the 2-norm.
$endgroup$
– Michael Grant
Oct 19 '18 at 20:32
$begingroup$
I see what you meant now. ;) Yes it will work for this problem too.
$endgroup$
– mathreadler
Oct 22 '18 at 13:49