Lipschitz constant of a Matrix Valued Function$sqrt{x}$ isn't Lipschitz functionFind a Lipschitz constant for...
How to tell a function to use the default argument values?
Why would the Red Woman birth a shadow if she worshipped the Lord of the Light?
Examples of smooth manifolds admitting inbetween one and a continuum of complex structures
What method can I use to design a dungeon difficult enough that the PCs can't make it through without killing them?
How can I deal with my CEO asking me to hire someone with a higher salary than me, a co-founder?
Should I cover my bicycle overnight while bikepacking?
Im going to France and my passport expires June 19th
Arrow those variables!
How seriously should I take size and weight limits of hand luggage?
Intersection Puzzle
Is it logically or scientifically possible to artificially send energy to the body?
Forgetting the musical notes while performing in concert
What is a romance in Latin?
Size of subfigure fitting its content (tikzpicture)
Plagiarism or not?
Personal Teleportation: From Rags to Riches
Can we compute the area of a quadrilateral with one right angle when we only know the lengths of any three sides?
How much of data wrangling is a data scientist's job?
Why is consensus so controversial in Britain?
Expand and Contract
When is человек used as the word man instead of человек
Determining Impedance With An Antenna Analyzer
Alternative to sending password over mail?
Is it acceptable for a professor to tell male students to not think that they are smarter than female students?
Lipschitz constant of a Matrix Valued Function
$sqrt{x}$ isn't Lipschitz functionFind a Lipschitz constant for a quadratic function restricted to a ballRelation between local lipschitz constant and global lipschitz constantLipschitz constant of a vector valued functionBest constant for Lipschitz continuous gradient functionLipschitz constant. How to show this inequality?Lipschitz function with non-lipschitz derivativeHow to prove the following function is not Lipschitz continuous?Coordinate Lipschitz constant vs standard Lipschitz constantWhat does the Lipschitz constant tell us?
$begingroup$
Consider the function $H(w) = sum_{i=1}^n f(w^T x_i) x_i x_i^T $, where $win mathbb{R}^d$, $forall i$: $x_i in mathbb{R}^d$, and $f: mathbb{R} to [0,1]$. Further, know $|f'(y)| leq 1$ for all $yin mathbb{R}$. Note, $d > n$ is possible.
What is the Lipschitz constant for this function, i.e. for which $M$ the following inequality is true?
$|H(w) - H(w') |_{op,2} leq M |w- w'|_2$ for all $w,w'in mathbb{R}^d$
functional-analysis lipschitz-functions
asked Mar 18 at 19:39
Soumya BasuSoumya Basu
598
$endgroup$
add a comment |
$begingroup$
Consider the function $H(w) = sum_{i=1}^n f(w^T x_i) x_i x_i^T $, where $win mathbb{R}^d$, $forall i$: $x_i in mathbb{R}^d$, and $f: mathbb{R} to [0,1]$. Further, know $|f'(y)| leq 1$ for all $yin mathbb{R}$. Note, $d > n$ is possible.
What is the Lipschitz constant for this function, i.e. for which $M$ the following inequality is true?
$|H(w) - H(w') |_{op,2} leq M |w- w'|_2$ for all $w,w'in mathbb{R}^d$
functional-analysis lipschitz-functions
asked Mar 18 at 19:39
Soumya BasuSoumya Basu
598
$endgroup$
$begingroup$
An estimate is easy to make, I doubt that there is a clean exact value without additional assumptions?
$endgroup$
– copper.hat
Mar 18 at 20:35
$begingroup$
I am not looking for an exact tight value here and will be satisfied with non-trivial estimates. However, what kind of additional assumptions do you need for a clean value?
$endgroup$
– Soumya Basu
Mar 18 at 23:50
$begingroup$
Do you know that $|f'(y)| le 1$ or just $f'(y) le 1$?
$endgroup$
– copper.hat
Mar 19 at 0:55
add a comment |
$begingroup$
Consider the function $H(w) = sum_{i=1}^n f(w^T x_i) x_i x_i^T $, where $win mathbb{R}^d$, $forall i$: $x_i in mathbb{R}^d$, and $f: mathbb{R} to [0,1]$. Further, know $|f'(y)| leq 1$ for all $yin mathbb{R}$. Note, $d > n$ is possible.
What is the Lipschitz constant for this function, i.e. for which $M$ the following inequality is true?
$|H(w) - H(w') |_{op,2} leq M |w- w'|_2$ for all $w,w'in mathbb{R}^d$
functional-analysis lipschitz-functions
asked Mar 18 at 19:39
Soumya BasuSoumya Basu
598
$endgroup$
Consider the function $H(w) = sum_{i=1}^n f(w^T x_i) x_i x_i^T $, where $win mathbb{R}^d$, $forall i$: $x_i in mathbb{R}^d$, and $f: mathbb{R} to [0,1]$. Further, know $|f'(y)| leq 1$ for all $yin mathbb{R}$. Note, $d > n$ is possible.
What is the Lipschitz constant for this function, i.e. for which $M$ the following inequality is true?
$|H(w) - H(w') |_{op,2} leq M |w- w'|_2$ for all $w,w'in mathbb{R}^d$
functional-analysis lipschitz-functions
functional-analysis lipschitz-functions
asked Mar 18 at 19:39
Soumya BasuSoumya Basu
598
asked Mar 18 at 19:39
Soumya BasuSoumya Basu
598
edited Mar 19 at 16:56
Soumya Basu
asked Mar 18 at 19:39
Soumya BasuSoumya Basu
598
asked Mar 18 at 19:39
Soumya BasuSoumya Basu
598
asked Mar 18 at 19:39
Soumya BasuSoumya Basu
598
598
$begingroup$
An estimate is easy to make, I doubt that there is a clean exact value without additional assumptions?
$endgroup$
– copper.hat
Mar 18 at 20:35
$begingroup$
I am not looking for an exact tight value here and will be satisfied with non-trivial estimates. However, what kind of additional assumptions do you need for a clean value?
$endgroup$
– Soumya Basu
Mar 18 at 23:50
$begingroup$
Do you know that $|f'(y)| le 1$ or just $f'(y) le 1$?
$endgroup$
– copper.hat
Mar 19 at 0:55
add a comment |
$begingroup$
An estimate is easy to make, I doubt that there is a clean exact value without additional assumptions?
$endgroup$
– copper.hat
Mar 18 at 20:35
$begingroup$
I am not looking for an exact tight value here and will be satisfied with non-trivial estimates. However, what kind of additional assumptions do you need for a clean value?
$endgroup$
– Soumya Basu
Mar 18 at 23:50
$begingroup$
Do you know that $|f'(y)| le 1$ or just $f'(y) le 1$?
$endgroup$
– copper.hat
Mar 19 at 0:55
$begingroup$
An estimate is easy to make, I doubt that there is a clean exact value without additional assumptions?
$endgroup$
– copper.hat
Mar 18 at 20:35
$begingroup$
An estimate is easy to make, I doubt that there is a clean exact value without additional assumptions?
$endgroup$
– copper.hat
Mar 18 at 20:35
$begingroup$
I am not looking for an exact tight value here and will be satisfied with non-trivial estimates. However, what kind of additional assumptions do you need for a clean value?
$endgroup$
– Soumya Basu
Mar 18 at 23:50
$begingroup$
I am not looking for an exact tight value here and will be satisfied with non-trivial estimates. However, what kind of additional assumptions do you need for a clean value?
$endgroup$
– Soumya Basu
Mar 18 at 23:50
$begingroup$
Do you know that $|f'(y)| le 1$ or just $f'(y) le 1$?
$endgroup$
– copper.hat
Mar 19 at 0:55
$begingroup$
Do you know that $|f'(y)| le 1$ or just $f'(y) le 1$?
$endgroup$
– copper.hat
Mar 19 at 0:55
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
If you know that $|f'(x)| le 1$, then you can quickly obtain the following estimate
using the mean value theorem.
$H(w)-H(w') = sum_i (f(x_i^T w)-f(x_i^Tw')) x_i x_i^T$, hence
$|H(w)-H(w')| le sum_i |x_i^T (w-w')| | x_i x_i^T| $, and
so $L=sum_i |x_i|^3$ is one estimate.
answered Mar 19 at 15:10
copper.hatcopper.hat
128k561161
$endgroup$
$begingroup$
The bound $|f'(x)< 1|$ is alright. However, the above estimate will result in M = O(n), which is not quite satisfactory. Is there any way to bound it in terms of the spectral radius of $sum_i x_i x_i^T$?
$endgroup$
– Soumya Basu
Mar 19 at 16:59
$begingroup$
I'm not sure what you mean by an $O(n)$ bound.
$endgroup$
– copper.hat
Mar 19 at 18:00
$begingroup$
I mean $sum_{i=1}^{n}|x_i|^3 = O(n)$.
$endgroup$
– Soumya Basu
Mar 19 at 20:55
$begingroup$
I still really don't understand what you mean. The norm of $sum_k x_k x_k^T$ could be $ge Kn$ for some positive $K$.
$endgroup$
– copper.hat
Mar 19 at 21:01
$begingroup$
I see your point. I think it was my mistake. I will check how the bounds translate in my setting. To be really precise, I am interested in bounding M using the eigenvalues of the matrix $sum_i x_ix_i^T$ and maybe $max_i |x_i|$. Indeed, the eigenvalue can be large.
$endgroup$
– Soumya Basu
Mar 20 at 16:13
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%2f3153217%2flipschitz-constant-of-a-matrix-valued-function%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$
If you know that $|f'(x)| le 1$, then you can quickly obtain the following estimate
using the mean value theorem.
$H(w)-H(w') = sum_i (f(x_i^T w)-f(x_i^Tw')) x_i x_i^T$, hence
$|H(w)-H(w')| le sum_i |x_i^T (w-w')| | x_i x_i^T| $, and
so $L=sum_i |x_i|^3$ is one estimate.
answered Mar 19 at 15:10
copper.hatcopper.hat
128k561161
$endgroup$
$begingroup$
The bound $|f'(x)< 1|$ is alright. However, the above estimate will result in M = O(n), which is not quite satisfactory. Is there any way to bound it in terms of the spectral radius of $sum_i x_i x_i^T$?
$endgroup$
– Soumya Basu
Mar 19 at 16:59
$begingroup$
I'm not sure what you mean by an $O(n)$ bound.
$endgroup$
– copper.hat
Mar 19 at 18:00
$begingroup$
I mean $sum_{i=1}^{n}|x_i|^3 = O(n)$.
$endgroup$
– Soumya Basu
Mar 19 at 20:55
$begingroup$
I still really don't understand what you mean. The norm of $sum_k x_k x_k^T$ could be $ge Kn$ for some positive $K$.
$endgroup$
– copper.hat
Mar 19 at 21:01
$begingroup$
I see your point. I think it was my mistake. I will check how the bounds translate in my setting. To be really precise, I am interested in bounding M using the eigenvalues of the matrix $sum_i x_ix_i^T$ and maybe $max_i |x_i|$. Indeed, the eigenvalue can be large.
$endgroup$
– Soumya Basu
Mar 20 at 16:13
add a comment |
$begingroup$
If you know that $|f'(x)| le 1$, then you can quickly obtain the following estimate
using the mean value theorem.
$H(w)-H(w') = sum_i (f(x_i^T w)-f(x_i^Tw')) x_i x_i^T$, hence
$|H(w)-H(w')| le sum_i |x_i^T (w-w')| | x_i x_i^T| $, and
so $L=sum_i |x_i|^3$ is one estimate.
answered Mar 19 at 15:10
copper.hatcopper.hat
128k561161
$endgroup$
$begingroup$
The bound $|f'(x)< 1|$ is alright. However, the above estimate will result in M = O(n), which is not quite satisfactory. Is there any way to bound it in terms of the spectral radius of $sum_i x_i x_i^T$?
$endgroup$
– Soumya Basu
Mar 19 at 16:59
$begingroup$
I'm not sure what you mean by an $O(n)$ bound.
$endgroup$
– copper.hat
Mar 19 at 18:00
$begingroup$
I mean $sum_{i=1}^{n}|x_i|^3 = O(n)$.
$endgroup$
– Soumya Basu
Mar 19 at 20:55
$begingroup$
I still really don't understand what you mean. The norm of $sum_k x_k x_k^T$ could be $ge Kn$ for some positive $K$.
$endgroup$
– copper.hat
Mar 19 at 21:01
$begingroup$
I see your point. I think it was my mistake. I will check how the bounds translate in my setting. To be really precise, I am interested in bounding M using the eigenvalues of the matrix $sum_i x_ix_i^T$ and maybe $max_i |x_i|$. Indeed, the eigenvalue can be large.
$endgroup$
– Soumya Basu
Mar 20 at 16:13
add a comment |
$begingroup$
If you know that $|f'(x)| le 1$, then you can quickly obtain the following estimate
using the mean value theorem.
$H(w)-H(w') = sum_i (f(x_i^T w)-f(x_i^Tw')) x_i x_i^T$, hence
$|H(w)-H(w')| le sum_i |x_i^T (w-w')| | x_i x_i^T| $, and
so $L=sum_i |x_i|^3$ is one estimate.
answered Mar 19 at 15:10
copper.hatcopper.hat
128k561161
$endgroup$
If you know that $|f'(x)| le 1$, then you can quickly obtain the following estimate
using the mean value theorem.
$H(w)-H(w') = sum_i (f(x_i^T w)-f(x_i^Tw')) x_i x_i^T$, hence
$|H(w)-H(w')| le sum_i |x_i^T (w-w')| | x_i x_i^T| $, and
so $L=sum_i |x_i|^3$ is one estimate.
answered Mar 19 at 15:10
copper.hatcopper.hat
128k561161
answered Mar 19 at 15:10
copper.hatcopper.hat
128k561161
answered Mar 19 at 15:10
copper.hatcopper.hat
128k561161
answered Mar 19 at 15:10
copper.hatcopper.hat
128k561161
128k561161
$begingroup$
The bound $|f'(x)< 1|$ is alright. However, the above estimate will result in M = O(n), which is not quite satisfactory. Is there any way to bound it in terms of the spectral radius of $sum_i x_i x_i^T$?
$endgroup$
– Soumya Basu
Mar 19 at 16:59
$begingroup$
I'm not sure what you mean by an $O(n)$ bound.
$endgroup$
– copper.hat
Mar 19 at 18:00
$begingroup$
I mean $sum_{i=1}^{n}|x_i|^3 = O(n)$.
$endgroup$
– Soumya Basu
Mar 19 at 20:55
$begingroup$
I still really don't understand what you mean. The norm of $sum_k x_k x_k^T$ could be $ge Kn$ for some positive $K$.
$endgroup$
– copper.hat
Mar 19 at 21:01
$begingroup$
I see your point. I think it was my mistake. I will check how the bounds translate in my setting. To be really precise, I am interested in bounding M using the eigenvalues of the matrix $sum_i x_ix_i^T$ and maybe $max_i |x_i|$. Indeed, the eigenvalue can be large.
$endgroup$
– Soumya Basu
Mar 20 at 16:13
add a comment |
$begingroup$
The bound $|f'(x)< 1|$ is alright. However, the above estimate will result in M = O(n), which is not quite satisfactory. Is there any way to bound it in terms of the spectral radius of $sum_i x_i x_i^T$?
$endgroup$
– Soumya Basu
Mar 19 at 16:59
$begingroup$
I'm not sure what you mean by an $O(n)$ bound.
$endgroup$
– copper.hat
Mar 19 at 18:00
$begingroup$
I mean $sum_{i=1}^{n}|x_i|^3 = O(n)$.
$endgroup$
– Soumya Basu
Mar 19 at 20:55
$begingroup$
I still really don't understand what you mean. The norm of $sum_k x_k x_k^T$ could be $ge Kn$ for some positive $K$.
$endgroup$
– copper.hat
Mar 19 at 21:01
$begingroup$
I see your point. I think it was my mistake. I will check how the bounds translate in my setting. To be really precise, I am interested in bounding M using the eigenvalues of the matrix $sum_i x_ix_i^T$ and maybe $max_i |x_i|$. Indeed, the eigenvalue can be large.
$endgroup$
– Soumya Basu
Mar 20 at 16:13
$begingroup$
The bound $|f'(x)< 1|$ is alright. However, the above estimate will result in M = O(n), which is not quite satisfactory. Is there any way to bound it in terms of the spectral radius of $sum_i x_i x_i^T$?
$endgroup$
– Soumya Basu
Mar 19 at 16:59
$begingroup$
The bound $|f'(x)< 1|$ is alright. However, the above estimate will result in M = O(n), which is not quite satisfactory. Is there any way to bound it in terms of the spectral radius of $sum_i x_i x_i^T$?
$endgroup$
– Soumya Basu
Mar 19 at 16:59
$begingroup$
I'm not sure what you mean by an $O(n)$ bound.
$endgroup$
– copper.hat
Mar 19 at 18:00
$begingroup$
I'm not sure what you mean by an $O(n)$ bound.
$endgroup$
– copper.hat
Mar 19 at 18:00
$begingroup$
I mean $sum_{i=1}^{n}|x_i|^3 = O(n)$.
$endgroup$
– Soumya Basu
Mar 19 at 20:55
$begingroup$
I mean $sum_{i=1}^{n}|x_i|^3 = O(n)$.
$endgroup$
– Soumya Basu
Mar 19 at 20:55
$begingroup$
I still really don't understand what you mean. The norm of $sum_k x_k x_k^T$ could be $ge Kn$ for some positive $K$.
$endgroup$
– copper.hat
Mar 19 at 21:01
$begingroup$
I still really don't understand what you mean. The norm of $sum_k x_k x_k^T$ could be $ge Kn$ for some positive $K$.
$endgroup$
– copper.hat
Mar 19 at 21:01
$begingroup$
I see your point. I think it was my mistake. I will check how the bounds translate in my setting. To be really precise, I am interested in bounding M using the eigenvalues of the matrix $sum_i x_ix_i^T$ and maybe $max_i |x_i|$. Indeed, the eigenvalue can be large.
$endgroup$
– Soumya Basu
Mar 20 at 16:13
$begingroup$
I see your point. I think it was my mistake. I will check how the bounds translate in my setting. To be really precise, I am interested in bounding M using the eigenvalues of the matrix $sum_i x_ix_i^T$ and maybe $max_i |x_i|$. Indeed, the eigenvalue can be large.
$endgroup$
– Soumya Basu
Mar 20 at 16:13
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%2f3153217%2flipschitz-constant-of-a-matrix-valued-function%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$
An estimate is easy to make, I doubt that there is a clean exact value without additional assumptions?
$endgroup$
– copper.hat
Mar 18 at 20:35
$begingroup$
I am not looking for an exact tight value here and will be satisfied with non-trivial estimates. However, what kind of additional assumptions do you need for a clean value?
$endgroup$
– Soumya Basu
Mar 18 at 23:50
$begingroup$
Do you know that $|f'(y)| le 1$ or just $f'(y) le 1$?
$endgroup$
– copper.hat
Mar 19 at 0:55