Dtjytyk

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?

0

1

$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

share|cite|improve this question

edited Mar 19 at 16:56

Soumya Basu

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 | 

0

1

$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

share|cite|improve this question

edited Mar 19 at 16:56

Soumya Basu

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

share|cite|improve this question

edited Mar 19 at 16:56

Soumya Basu

asked Mar 18 at 19:39

Soumya BasuSoumya Basu

598

$endgroup$

share|cite|improve this question

edited Mar 19 at 16:56

Soumya Basu

asked Mar 18 at 19:39

Soumya BasuSoumya Basu

598

share|cite|improve this question

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

1 Answer
1

active

oldest

votes

0

$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.

share|cite|improve this answer

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
});


}
});

draft saved

draft discarded

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

Name

Email

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

Name

Email

Required, but never shown

0

$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.

share|cite|improve this answer

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 | 

0

$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.

share|cite|improve this answer

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.

share|cite|improve this answer

answered Mar 19 at 15:10

copper.hatcopper.hat

128k561161

$endgroup$

share|cite|improve this answer

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