Nonlinear approximation by piecewise constants and the expectation of the error
$begingroup$
Suppose $Omega=[0,1]$ and $f$ is continuous, monotonic, and of bounded variation on $Omega$ with $M:= text{Var}_Omega(f).$
Let $| cdot|:=| cdot|_{L_infty(Omega)}.$ Let $T={0=t_0,...,t_n=1}$ be the uniform partition of the range of $f,a_k$ is the average of the function values at the endpoints on $[f^{-1}(t_{k-1}),f^{-1}(t_k)],$ and $S_n(x):=a_k,xin[f^{-1}(t_{k-1}),f^{-1}(t_k)),k=1,...,n.$ Then there is a theorem says that$$|f-S_n|le M/2n.$$
The above theorem uses the uniform partition of the range. Now if we use a random partition of the range of $f$ and assume the partition points $t_i sim U(0,1), $ where $i=1,..,n-1.$ Can we get the result $E(| f-S_n|)le C/n$ for some constant $C$? How to prove or disprove it? I have trouble expressing the expectation explicitly.
I showed that the expectation of the length of each subinterval is $1/n.$ But I am not sure if the result is useful.
functional-analysis analysis probability-distributions numerical-methods approximation
asked Jan 10 at 20:54
XYZXYZ
30718
$endgroup$
|
show 3 more comments
$begingroup$
Suppose $Omega=[0,1]$ and $f$ is continuous, monotonic, and of bounded variation on $Omega$ with $M:= text{Var}_Omega(f).$
Let $| cdot|:=| cdot|_{L_infty(Omega)}.$ Let $T={0=t_0,...,t_n=1}$ be the uniform partition of the range of $f,a_k$ is the average of the function values at the endpoints on $[f^{-1}(t_{k-1}),f^{-1}(t_k)],$ and $S_n(x):=a_k,xin[f^{-1}(t_{k-1}),f^{-1}(t_k)),k=1,...,n.$ Then there is a theorem says that$$|f-S_n|le M/2n.$$
The above theorem uses the uniform partition of the range. Now if we use a random partition of the range of $f$ and assume the partition points $t_i sim U(0,1), $ where $i=1,..,n-1.$ Can we get the result $E(| f-S_n|)le C/n$ for some constant $C$? How to prove or disprove it? I have trouble expressing the expectation explicitly.
I showed that the expectation of the length of each subinterval is $1/n.$ But I am not sure if the result is useful.
functional-analysis analysis probability-distributions numerical-methods approximation
asked Jan 10 at 20:54
XYZXYZ
30718
$endgroup$
$begingroup$
I don't entirely understand how $S_n$ is constructed when $f$ isn't injective. Is it that wherever $t_{k-1}<f(x)<t_k$, $S_n(x)=frac{t_{k-1}+t_k}{2}$? Or do you take the median operation in the domain instead, so that the partition of the range induces a partition of the domain and then you approximate $f$ on that partition of the domain using the midpoint rule?
$endgroup$
– Ian
Jan 10 at 21:06
$begingroup$
(Also, I guess the domain and range of $f$ are both $[0,1]$? This isn't clear from what you wrote.)
$endgroup$
– Ian
Jan 10 at 21:09
$begingroup$
@Ian Thank you very much. I already changed the problem. $f$ is monotonic.
$endgroup$
– XYZ
Jan 10 at 22:00
$begingroup$
OK. So is "the median value" $f$ at the median, or the average of the function values at the endpoints? It seems like it must be the latter because the former would not give your result (consider $n=1$ and $f(x)=x^N$ for some large $N$).
$endgroup$
– Ian
Jan 10 at 22:15
$begingroup$
@Ian. Yes, thank you very much for your suggestion. Also, I changed the statement that I want to prove.
$endgroup$
– XYZ
Jan 10 at 22:32
|
show 3 more comments
$begingroup$
Suppose $Omega=[0,1]$ and $f$ is continuous, monotonic, and of bounded variation on $Omega$ with $M:= text{Var}_Omega(f).$
Let $| cdot|:=| cdot|_{L_infty(Omega)}.$ Let $T={0=t_0,...,t_n=1}$ be the uniform partition of the range of $f,a_k$ is the average of the function values at the endpoints on $[f^{-1}(t_{k-1}),f^{-1}(t_k)],$ and $S_n(x):=a_k,xin[f^{-1}(t_{k-1}),f^{-1}(t_k)),k=1,...,n.$ Then there is a theorem says that$$|f-S_n|le M/2n.$$
The above theorem uses the uniform partition of the range. Now if we use a random partition of the range of $f$ and assume the partition points $t_i sim U(0,1), $ where $i=1,..,n-1.$ Can we get the result $E(| f-S_n|)le C/n$ for some constant $C$? How to prove or disprove it? I have trouble expressing the expectation explicitly.
I showed that the expectation of the length of each subinterval is $1/n.$ But I am not sure if the result is useful.
functional-analysis analysis probability-distributions numerical-methods approximation
asked Jan 10 at 20:54
XYZXYZ
30718
$endgroup$
Suppose $Omega=[0,1]$ and $f$ is continuous, monotonic, and of bounded variation on $Omega$ with $M:= text{Var}_Omega(f).$
Let $| cdot|:=| cdot|_{L_infty(Omega)}.$ Let $T={0=t_0,...,t_n=1}$ be the uniform partition of the range of $f,a_k$ is the average of the function values at the endpoints on $[f^{-1}(t_{k-1}),f^{-1}(t_k)],$ and $S_n(x):=a_k,xin[f^{-1}(t_{k-1}),f^{-1}(t_k)),k=1,...,n.$ Then there is a theorem says that$$|f-S_n|le M/2n.$$
The above theorem uses the uniform partition of the range. Now if we use a random partition of the range of $f$ and assume the partition points $t_i sim U(0,1), $ where $i=1,..,n-1.$ Can we get the result $E(| f-S_n|)le C/n$ for some constant $C$? How to prove or disprove it? I have trouble expressing the expectation explicitly.
I showed that the expectation of the length of each subinterval is $1/n.$ But I am not sure if the result is useful.
functional-analysis analysis probability-distributions numerical-methods approximation
functional-analysis analysis probability-distributions numerical-methods approximation
asked Jan 10 at 20:54
XYZXYZ
30718
asked Jan 10 at 20:54
XYZXYZ
30718
edited Jan 10 at 22:40
XYZ
asked Jan 10 at 20:54
XYZXYZ
30718
asked Jan 10 at 20:54
XYZXYZ
30718
asked Jan 10 at 20:54
XYZXYZ
30718
30718
$begingroup$
I don't entirely understand how $S_n$ is constructed when $f$ isn't injective. Is it that wherever $t_{k-1}<f(x)<t_k$, $S_n(x)=frac{t_{k-1}+t_k}{2}$? Or do you take the median operation in the domain instead, so that the partition of the range induces a partition of the domain and then you approximate $f$ on that partition of the domain using the midpoint rule?
$endgroup$
– Ian
Jan 10 at 21:06
$begingroup$
(Also, I guess the domain and range of $f$ are both $[0,1]$? This isn't clear from what you wrote.)
$endgroup$
– Ian
Jan 10 at 21:09
$begingroup$
@Ian Thank you very much. I already changed the problem. $f$ is monotonic.
$endgroup$
– XYZ
Jan 10 at 22:00
$begingroup$
OK. So is "the median value" $f$ at the median, or the average of the function values at the endpoints? It seems like it must be the latter because the former would not give your result (consider $n=1$ and $f(x)=x^N$ for some large $N$).
$endgroup$
– Ian
Jan 10 at 22:15
$begingroup$
@Ian. Yes, thank you very much for your suggestion. Also, I changed the statement that I want to prove.
$endgroup$
– XYZ
Jan 10 at 22:32
|
show 3 more comments
$begingroup$
I don't entirely understand how $S_n$ is constructed when $f$ isn't injective. Is it that wherever $t_{k-1}<f(x)<t_k$, $S_n(x)=frac{t_{k-1}+t_k}{2}$? Or do you take the median operation in the domain instead, so that the partition of the range induces a partition of the domain and then you approximate $f$ on that partition of the domain using the midpoint rule?
$endgroup$
– Ian
Jan 10 at 21:06
$begingroup$
(Also, I guess the domain and range of $f$ are both $[0,1]$? This isn't clear from what you wrote.)
$endgroup$
– Ian
Jan 10 at 21:09
$begingroup$
@Ian Thank you very much. I already changed the problem. $f$ is monotonic.
$endgroup$
– XYZ
Jan 10 at 22:00
$begingroup$
OK. So is "the median value" $f$ at the median, or the average of the function values at the endpoints? It seems like it must be the latter because the former would not give your result (consider $n=1$ and $f(x)=x^N$ for some large $N$).
$endgroup$
– Ian
Jan 10 at 22:15
$begingroup$
@Ian. Yes, thank you very much for your suggestion. Also, I changed the statement that I want to prove.
$endgroup$
– XYZ
Jan 10 at 22:32
$begingroup$
I don't entirely understand how $S_n$ is constructed when $f$ isn't injective. Is it that wherever $t_{k-1}<f(x)<t_k$, $S_n(x)=frac{t_{k-1}+t_k}{2}$? Or do you take the median operation in the domain instead, so that the partition of the range induces a partition of the domain and then you approximate $f$ on that partition of the domain using the midpoint rule?
$endgroup$
– Ian
Jan 10 at 21:06
$begingroup$
I don't entirely understand how $S_n$ is constructed when $f$ isn't injective. Is it that wherever $t_{k-1}<f(x)<t_k$, $S_n(x)=frac{t_{k-1}+t_k}{2}$? Or do you take the median operation in the domain instead, so that the partition of the range induces a partition of the domain and then you approximate $f$ on that partition of the domain using the midpoint rule?
$endgroup$
– Ian
Jan 10 at 21:06
$begingroup$
(Also, I guess the domain and range of $f$ are both $[0,1]$? This isn't clear from what you wrote.)
$endgroup$
– Ian
Jan 10 at 21:09
$begingroup$
(Also, I guess the domain and range of $f$ are both $[0,1]$? This isn't clear from what you wrote.)
$endgroup$
– Ian
Jan 10 at 21:09
$begingroup$
@Ian Thank you very much. I already changed the problem. $f$ is monotonic.
$endgroup$
– XYZ
Jan 10 at 22:00
$begingroup$
@Ian Thank you very much. I already changed the problem. $f$ is monotonic.
$endgroup$
– XYZ
Jan 10 at 22:00
$begingroup$
OK. So is "the median value" $f$ at the median, or the average of the function values at the endpoints? It seems like it must be the latter because the former would not give your result (consider $n=1$ and $f(x)=x^N$ for some large $N$).
$endgroup$
– Ian
Jan 10 at 22:15
$begingroup$
OK. So is "the median value" $f$ at the median, or the average of the function values at the endpoints? It seems like it must be the latter because the former would not give your result (consider $n=1$ and $f(x)=x^N$ for some large $N$).
$endgroup$
– Ian
Jan 10 at 22:15
$begingroup$
@Ian. Yes, thank you very much for your suggestion. Also, I changed the statement that I want to prove.
$endgroup$
– XYZ
Jan 10 at 22:32
$begingroup$
@Ian. Yes, thank you very much for your suggestion. Also, I changed the statement that I want to prove.
$endgroup$
– XYZ
Jan 10 at 22:32
|
show 3 more comments
0
active
oldest
votes
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%2f3069159%2fnonlinear-approximation-by-piecewise-constants-and-the-expectation-of-the-error%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
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%2f3069159%2fnonlinear-approximation-by-piecewise-constants-and-the-expectation-of-the-error%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$
I don't entirely understand how $S_n$ is constructed when $f$ isn't injective. Is it that wherever $t_{k-1}<f(x)<t_k$, $S_n(x)=frac{t_{k-1}+t_k}{2}$? Or do you take the median operation in the domain instead, so that the partition of the range induces a partition of the domain and then you approximate $f$ on that partition of the domain using the midpoint rule?
$endgroup$
– Ian
Jan 10 at 21:06
$begingroup$
(Also, I guess the domain and range of $f$ are both $[0,1]$? This isn't clear from what you wrote.)
$endgroup$
– Ian
Jan 10 at 21:09
$begingroup$
@Ian Thank you very much. I already changed the problem. $f$ is monotonic.
$endgroup$
– XYZ
Jan 10 at 22:00
$begingroup$
OK. So is "the median value" $f$ at the median, or the average of the function values at the endpoints? It seems like it must be the latter because the former would not give your result (consider $n=1$ and $f(x)=x^N$ for some large $N$).
$endgroup$
– Ian
Jan 10 at 22:15
$begingroup$
@Ian. Yes, thank you very much for your suggestion. Also, I changed the statement that I want to prove.
$endgroup$
– XYZ
Jan 10 at 22:32