How do we know we're maximizing the Lagrangian objective function in PCA?
$begingroup$
In Principal Component Analysis, we start with $m$ observations $x_1,dots,x_m$, each of which is an $n$-dimensional vector. Assume we have centered the data; that is, we have subtracted the variable means from each observation. To project each observation into a $1$-dimensional subspace while maximizing sample variance, we want to compute a unit length basis vector, call it $v$. So we get the constrained problem
$$
mathop{arg,max}limits_{v},frac{1}{m}sum_{i=1}^{m}leftlVertlangle x_i,vrangle vrightrVert
$$
$$
text{subject to }v^Tv=1
$$
After some computations, this becomes
$$
mathop{arg,max}limits_{v},frac{1}{m}sum_{i=1}^{m}v^TCv
$$
$$
text{subject to }v^Tv=1
$$
where $C$ is the covariance matrix of the data. Then the Lagrangian objective function is
$$
mathcal{L}(v,lambda)=v^TCv-lambda(v^Tv-1)
$$
If we start taking partial derivatives of $mathcal{L}$, setting these to zero, etc, how do we know that we are maximizing $mathcal{L}$? Do we need to check that the Hessian is negative definite? Even then, I think that only guarantees a local maximum?
optimization lagrange-multiplier
asked Dec 4 '18 at 17:38
waynemystirwaynemystir
475
$endgroup$
add a comment |
$begingroup$
In Principal Component Analysis, we start with $m$ observations $x_1,dots,x_m$, each of which is an $n$-dimensional vector. Assume we have centered the data; that is, we have subtracted the variable means from each observation. To project each observation into a $1$-dimensional subspace while maximizing sample variance, we want to compute a unit length basis vector, call it $v$. So we get the constrained problem
$$
mathop{arg,max}limits_{v},frac{1}{m}sum_{i=1}^{m}leftlVertlangle x_i,vrangle vrightrVert
$$
$$
text{subject to }v^Tv=1
$$
After some computations, this becomes
$$
mathop{arg,max}limits_{v},frac{1}{m}sum_{i=1}^{m}v^TCv
$$
$$
text{subject to }v^Tv=1
$$
where $C$ is the covariance matrix of the data. Then the Lagrangian objective function is
$$
mathcal{L}(v,lambda)=v^TCv-lambda(v^Tv-1)
$$
If we start taking partial derivatives of $mathcal{L}$, setting these to zero, etc, how do we know that we are maximizing $mathcal{L}$? Do we need to check that the Hessian is negative definite? Even then, I think that only guarantees a local maximum?
optimization lagrange-multiplier
asked Dec 4 '18 at 17:38
waynemystirwaynemystir
475
$endgroup$
add a comment |
$begingroup$
In Principal Component Analysis, we start with $m$ observations $x_1,dots,x_m$, each of which is an $n$-dimensional vector. Assume we have centered the data; that is, we have subtracted the variable means from each observation. To project each observation into a $1$-dimensional subspace while maximizing sample variance, we want to compute a unit length basis vector, call it $v$. So we get the constrained problem
$$
mathop{arg,max}limits_{v},frac{1}{m}sum_{i=1}^{m}leftlVertlangle x_i,vrangle vrightrVert
$$
$$
text{subject to }v^Tv=1
$$
After some computations, this becomes
$$
mathop{arg,max}limits_{v},frac{1}{m}sum_{i=1}^{m}v^TCv
$$
$$
text{subject to }v^Tv=1
$$
where $C$ is the covariance matrix of the data. Then the Lagrangian objective function is
$$
mathcal{L}(v,lambda)=v^TCv-lambda(v^Tv-1)
$$
If we start taking partial derivatives of $mathcal{L}$, setting these to zero, etc, how do we know that we are maximizing $mathcal{L}$? Do we need to check that the Hessian is negative definite? Even then, I think that only guarantees a local maximum?
optimization lagrange-multiplier
asked Dec 4 '18 at 17:38
waynemystirwaynemystir
475
$endgroup$
In Principal Component Analysis, we start with $m$ observations $x_1,dots,x_m$, each of which is an $n$-dimensional vector. Assume we have centered the data; that is, we have subtracted the variable means from each observation. To project each observation into a $1$-dimensional subspace while maximizing sample variance, we want to compute a unit length basis vector, call it $v$. So we get the constrained problem
$$
mathop{arg,max}limits_{v},frac{1}{m}sum_{i=1}^{m}leftlVertlangle x_i,vrangle vrightrVert
$$
$$
text{subject to }v^Tv=1
$$
After some computations, this becomes
$$
mathop{arg,max}limits_{v},frac{1}{m}sum_{i=1}^{m}v^TCv
$$
$$
text{subject to }v^Tv=1
$$
where $C$ is the covariance matrix of the data. Then the Lagrangian objective function is
$$
mathcal{L}(v,lambda)=v^TCv-lambda(v^Tv-1)
$$
If we start taking partial derivatives of $mathcal{L}$, setting these to zero, etc, how do we know that we are maximizing $mathcal{L}$? Do we need to check that the Hessian is negative definite? Even then, I think that only guarantees a local maximum?
optimization lagrange-multiplier
optimization lagrange-multiplier
asked Dec 4 '18 at 17:38
waynemystirwaynemystir
475
asked Dec 4 '18 at 17:38
waynemystirwaynemystir
475
asked Dec 4 '18 at 17:38
waynemystirwaynemystir
475
asked Dec 4 '18 at 17:38
waynemystirwaynemystir
475
asked Dec 4 '18 at 17:38
waynemystirwaynemystir
475
475
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Define $K:=frac{C+C^T}{2}-lambda I$. Note that $mathcal{L}=v^T Kv+lambda$ is a quadratic, so if $K$ is definite the local turning point, which solves $Kv=0$ from the first derivative of $mathcal{L}$, is also a global extremum. I've written the coefficient as a symmetric real matrix so it's diagonalisable, viz. $mathcal{L}=sum_i K_{ii}v_i^2+lambda$. In our choice of basis $Kv=0$ simplifies to $K_{ii}ne 0implies v_i=0$. This maximises $mathcal{L}$ provided each of the eigenvalues $K_{ii}$ is at most $0$. Indeed, the solution is for $lambda$ to be the largest eigenvalue of $frac{C+C^T}{2}$, with $v$ a unit eigenvector corresponding to $lambda$; then $K$ has $0$ as an eigenvalue, but no positive eigenvalues.
edited Dec 4 '18 at 20:48
waynemystir
475
answered Dec 4 '18 at 17:51
J.G.J.G.
24.6k22539
$endgroup$
$begingroup$
Thank you. Why is the local turning point a global extremum if $K$ is definite? Why does diagonalisability give an obvious result? Which vector space?
$endgroup$
– waynemystir
Dec 4 '18 at 18:11
$begingroup$
@waynemystir Hopefully my edit makes it clearer.
$endgroup$
– J.G.
Dec 4 '18 at 18:28
$begingroup$
I'm confused. What is $V$ or $V_i$? A vector and component? Is $K$ the coefficient? So you diagonalised $K$ and rewrote $mathcal{L}$ relative to this change of basis? Why does the stationary point solve $KV=0$?
$endgroup$
– waynemystir
Dec 4 '18 at 18:40
$begingroup$
@waynemystir I hope my latest edit is even clearer. $v_i$ is indeed a component of $v$.
$endgroup$
– J.G.
Dec 4 '18 at 18:46
$begingroup$
Why is the solution for $lambda$ to be the largest eigenvalue of $frac{C+C^T}{2}$? Taking partials, I see $lambda$ is an eigenvalue. But why does it need to be the largest? The equation $mathcal{L}(v,lambda)=v^TCv-lambda(v^Tv-1)=v^TCv=v^Tlambda v=lambda$ only tells us that $mathcal{L}$ attains the eigenvalue $lambda$. This equation doesn't reveal that it's the largest one.
$endgroup$
– waynemystir
Dec 5 '18 at 0:19
|
show 4 more comments
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%2f3025885%2fhow-do-we-know-were-maximizing-the-lagrangian-objective-function-in-pca%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$
Define $K:=frac{C+C^T}{2}-lambda I$. Note that $mathcal{L}=v^T Kv+lambda$ is a quadratic, so if $K$ is definite the local turning point, which solves $Kv=0$ from the first derivative of $mathcal{L}$, is also a global extremum. I've written the coefficient as a symmetric real matrix so it's diagonalisable, viz. $mathcal{L}=sum_i K_{ii}v_i^2+lambda$. In our choice of basis $Kv=0$ simplifies to $K_{ii}ne 0implies v_i=0$. This maximises $mathcal{L}$ provided each of the eigenvalues $K_{ii}$ is at most $0$. Indeed, the solution is for $lambda$ to be the largest eigenvalue of $frac{C+C^T}{2}$, with $v$ a unit eigenvector corresponding to $lambda$; then $K$ has $0$ as an eigenvalue, but no positive eigenvalues.
edited Dec 4 '18 at 20:48
waynemystir
475
answered Dec 4 '18 at 17:51
J.G.J.G.
24.6k22539
$endgroup$
$begingroup$
Thank you. Why is the local turning point a global extremum if $K$ is definite? Why does diagonalisability give an obvious result? Which vector space?
$endgroup$
– waynemystir
Dec 4 '18 at 18:11
$begingroup$
@waynemystir Hopefully my edit makes it clearer.
$endgroup$
– J.G.
Dec 4 '18 at 18:28
$begingroup$
I'm confused. What is $V$ or $V_i$? A vector and component? Is $K$ the coefficient? So you diagonalised $K$ and rewrote $mathcal{L}$ relative to this change of basis? Why does the stationary point solve $KV=0$?
$endgroup$
– waynemystir
Dec 4 '18 at 18:40
$begingroup$
@waynemystir I hope my latest edit is even clearer. $v_i$ is indeed a component of $v$.
$endgroup$
– J.G.
Dec 4 '18 at 18:46
$begingroup$
Why is the solution for $lambda$ to be the largest eigenvalue of $frac{C+C^T}{2}$? Taking partials, I see $lambda$ is an eigenvalue. But why does it need to be the largest? The equation $mathcal{L}(v,lambda)=v^TCv-lambda(v^Tv-1)=v^TCv=v^Tlambda v=lambda$ only tells us that $mathcal{L}$ attains the eigenvalue $lambda$. This equation doesn't reveal that it's the largest one.
$endgroup$
– waynemystir
Dec 5 '18 at 0:19
|
show 4 more comments
$begingroup$
Define $K:=frac{C+C^T}{2}-lambda I$. Note that $mathcal{L}=v^T Kv+lambda$ is a quadratic, so if $K$ is definite the local turning point, which solves $Kv=0$ from the first derivative of $mathcal{L}$, is also a global extremum. I've written the coefficient as a symmetric real matrix so it's diagonalisable, viz. $mathcal{L}=sum_i K_{ii}v_i^2+lambda$. In our choice of basis $Kv=0$ simplifies to $K_{ii}ne 0implies v_i=0$. This maximises $mathcal{L}$ provided each of the eigenvalues $K_{ii}$ is at most $0$. Indeed, the solution is for $lambda$ to be the largest eigenvalue of $frac{C+C^T}{2}$, with $v$ a unit eigenvector corresponding to $lambda$; then $K$ has $0$ as an eigenvalue, but no positive eigenvalues.
edited Dec 4 '18 at 20:48
waynemystir
475
answered Dec 4 '18 at 17:51
J.G.J.G.
24.6k22539
$endgroup$
$begingroup$
Thank you. Why is the local turning point a global extremum if $K$ is definite? Why does diagonalisability give an obvious result? Which vector space?
$endgroup$
– waynemystir
Dec 4 '18 at 18:11
$begingroup$
@waynemystir Hopefully my edit makes it clearer.
$endgroup$
– J.G.
Dec 4 '18 at 18:28
$begingroup$
I'm confused. What is $V$ or $V_i$? A vector and component? Is $K$ the coefficient? So you diagonalised $K$ and rewrote $mathcal{L}$ relative to this change of basis? Why does the stationary point solve $KV=0$?
$endgroup$
– waynemystir
Dec 4 '18 at 18:40
$begingroup$
@waynemystir I hope my latest edit is even clearer. $v_i$ is indeed a component of $v$.
$endgroup$
– J.G.
Dec 4 '18 at 18:46
$begingroup$
Why is the solution for $lambda$ to be the largest eigenvalue of $frac{C+C^T}{2}$? Taking partials, I see $lambda$ is an eigenvalue. But why does it need to be the largest? The equation $mathcal{L}(v,lambda)=v^TCv-lambda(v^Tv-1)=v^TCv=v^Tlambda v=lambda$ only tells us that $mathcal{L}$ attains the eigenvalue $lambda$. This equation doesn't reveal that it's the largest one.
$endgroup$
– waynemystir
Dec 5 '18 at 0:19
|
show 4 more comments
$begingroup$
Define $K:=frac{C+C^T}{2}-lambda I$. Note that $mathcal{L}=v^T Kv+lambda$ is a quadratic, so if $K$ is definite the local turning point, which solves $Kv=0$ from the first derivative of $mathcal{L}$, is also a global extremum. I've written the coefficient as a symmetric real matrix so it's diagonalisable, viz. $mathcal{L}=sum_i K_{ii}v_i^2+lambda$. In our choice of basis $Kv=0$ simplifies to $K_{ii}ne 0implies v_i=0$. This maximises $mathcal{L}$ provided each of the eigenvalues $K_{ii}$ is at most $0$. Indeed, the solution is for $lambda$ to be the largest eigenvalue of $frac{C+C^T}{2}$, with $v$ a unit eigenvector corresponding to $lambda$; then $K$ has $0$ as an eigenvalue, but no positive eigenvalues.
edited Dec 4 '18 at 20:48
waynemystir
475
answered Dec 4 '18 at 17:51
J.G.J.G.
24.6k22539
$endgroup$
Define $K:=frac{C+C^T}{2}-lambda I$. Note that $mathcal{L}=v^T Kv+lambda$ is a quadratic, so if $K$ is definite the local turning point, which solves $Kv=0$ from the first derivative of $mathcal{L}$, is also a global extremum. I've written the coefficient as a symmetric real matrix so it's diagonalisable, viz. $mathcal{L}=sum_i K_{ii}v_i^2+lambda$. In our choice of basis $Kv=0$ simplifies to $K_{ii}ne 0implies v_i=0$. This maximises $mathcal{L}$ provided each of the eigenvalues $K_{ii}$ is at most $0$. Indeed, the solution is for $lambda$ to be the largest eigenvalue of $frac{C+C^T}{2}$, with $v$ a unit eigenvector corresponding to $lambda$; then $K$ has $0$ as an eigenvalue, but no positive eigenvalues.
edited Dec 4 '18 at 20:48
waynemystir
475
answered Dec 4 '18 at 17:51
J.G.J.G.
24.6k22539
edited Dec 4 '18 at 20:48
waynemystir
475
edited Dec 4 '18 at 20:48
waynemystir
475
edited Dec 4 '18 at 20:48
waynemystir
475
475
answered Dec 4 '18 at 17:51
J.G.J.G.
24.6k22539
answered Dec 4 '18 at 17:51
J.G.J.G.
24.6k22539
answered Dec 4 '18 at 17:51
J.G.J.G.
24.6k22539
24.6k22539
$begingroup$
Thank you. Why is the local turning point a global extremum if $K$ is definite? Why does diagonalisability give an obvious result? Which vector space?
$endgroup$
– waynemystir
Dec 4 '18 at 18:11
$begingroup$
@waynemystir Hopefully my edit makes it clearer.
$endgroup$
– J.G.
Dec 4 '18 at 18:28
$begingroup$
I'm confused. What is $V$ or $V_i$? A vector and component? Is $K$ the coefficient? So you diagonalised $K$ and rewrote $mathcal{L}$ relative to this change of basis? Why does the stationary point solve $KV=0$?
$endgroup$
– waynemystir
Dec 4 '18 at 18:40
$begingroup$
@waynemystir I hope my latest edit is even clearer. $v_i$ is indeed a component of $v$.
$endgroup$
– J.G.
Dec 4 '18 at 18:46
$begingroup$
Why is the solution for $lambda$ to be the largest eigenvalue of $frac{C+C^T}{2}$? Taking partials, I see $lambda$ is an eigenvalue. But why does it need to be the largest? The equation $mathcal{L}(v,lambda)=v^TCv-lambda(v^Tv-1)=v^TCv=v^Tlambda v=lambda$ only tells us that $mathcal{L}$ attains the eigenvalue $lambda$. This equation doesn't reveal that it's the largest one.
$endgroup$
– waynemystir
Dec 5 '18 at 0:19
|
show 4 more comments
$begingroup$
Thank you. Why is the local turning point a global extremum if $K$ is definite? Why does diagonalisability give an obvious result? Which vector space?
$endgroup$
– waynemystir
Dec 4 '18 at 18:11
$begingroup$
@waynemystir Hopefully my edit makes it clearer.
$endgroup$
– J.G.
Dec 4 '18 at 18:28
$begingroup$
I'm confused. What is $V$ or $V_i$? A vector and component? Is $K$ the coefficient? So you diagonalised $K$ and rewrote $mathcal{L}$ relative to this change of basis? Why does the stationary point solve $KV=0$?
$endgroup$
– waynemystir
Dec 4 '18 at 18:40
$begingroup$
@waynemystir I hope my latest edit is even clearer. $v_i$ is indeed a component of $v$.
$endgroup$
– J.G.
Dec 4 '18 at 18:46
$begingroup$
Why is the solution for $lambda$ to be the largest eigenvalue of $frac{C+C^T}{2}$? Taking partials, I see $lambda$ is an eigenvalue. But why does it need to be the largest? The equation $mathcal{L}(v,lambda)=v^TCv-lambda(v^Tv-1)=v^TCv=v^Tlambda v=lambda$ only tells us that $mathcal{L}$ attains the eigenvalue $lambda$. This equation doesn't reveal that it's the largest one.
$endgroup$
– waynemystir
Dec 5 '18 at 0:19
$begingroup$
Thank you. Why is the local turning point a global extremum if $K$ is definite? Why does diagonalisability give an obvious result? Which vector space?
$endgroup$
– waynemystir
Dec 4 '18 at 18:11
$begingroup$
Thank you. Why is the local turning point a global extremum if $K$ is definite? Why does diagonalisability give an obvious result? Which vector space?
$endgroup$
– waynemystir
Dec 4 '18 at 18:11
$begingroup$
@waynemystir Hopefully my edit makes it clearer.
$endgroup$
– J.G.
Dec 4 '18 at 18:28
$begingroup$
@waynemystir Hopefully my edit makes it clearer.
$endgroup$
– J.G.
Dec 4 '18 at 18:28
$begingroup$
I'm confused. What is $V$ or $V_i$? A vector and component? Is $K$ the coefficient? So you diagonalised $K$ and rewrote $mathcal{L}$ relative to this change of basis? Why does the stationary point solve $KV=0$?
$endgroup$
– waynemystir
Dec 4 '18 at 18:40
$begingroup$
I'm confused. What is $V$ or $V_i$? A vector and component? Is $K$ the coefficient? So you diagonalised $K$ and rewrote $mathcal{L}$ relative to this change of basis? Why does the stationary point solve $KV=0$?
$endgroup$
– waynemystir
Dec 4 '18 at 18:40
$begingroup$
@waynemystir I hope my latest edit is even clearer. $v_i$ is indeed a component of $v$.
$endgroup$
– J.G.
Dec 4 '18 at 18:46
$begingroup$
@waynemystir I hope my latest edit is even clearer. $v_i$ is indeed a component of $v$.
$endgroup$
– J.G.
Dec 4 '18 at 18:46
$begingroup$
Why is the solution for $lambda$ to be the largest eigenvalue of $frac{C+C^T}{2}$? Taking partials, I see $lambda$ is an eigenvalue. But why does it need to be the largest? The equation $mathcal{L}(v,lambda)=v^TCv-lambda(v^Tv-1)=v^TCv=v^Tlambda v=lambda$ only tells us that $mathcal{L}$ attains the eigenvalue $lambda$. This equation doesn't reveal that it's the largest one.
$endgroup$
– waynemystir
Dec 5 '18 at 0:19
$begingroup$
Why is the solution for $lambda$ to be the largest eigenvalue of $frac{C+C^T}{2}$? Taking partials, I see $lambda$ is an eigenvalue. But why does it need to be the largest? The equation $mathcal{L}(v,lambda)=v^TCv-lambda(v^Tv-1)=v^TCv=v^Tlambda v=lambda$ only tells us that $mathcal{L}$ attains the eigenvalue $lambda$. This equation doesn't reveal that it's the largest one.
$endgroup$
– waynemystir
Dec 5 '18 at 0:19
|
show 4 more comments
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%2f3025885%2fhow-do-we-know-were-maximizing-the-lagrangian-objective-function-in-pca%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
