Mixing
Little-o meaning in equation
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
I am completely new to little-o notation, I came across it in a lecture about algorithmically approaching a function minimum:
$$
f(x^n+1) = f(x^n) + nabla f(x^n ) cdot (x^n+1 − x^n) + o( | x^n+1 − x^n | )
= f(x^n) + t nabla f(x^n ) cdot d^n + o(t)
$$
where t is a chosen length (larger $t$ makes for larger steps, but possibly less direct).
To try to understand this, I searched and found this simple explanation:
$$
f(x) = o(g(x)), textas xto x_0
$$
is equivalent to $lim_xto x_0 f(x)/g(x) = 0$;
pdf link
This explanation seems clear in itself, but I'm struggling to link it to the equation from my lecture notes. Can I rearrange the equation like this?
$$
f(x^n+1) - f(x^n) - t nabla f(x^n ) cdot d^n = o(t)
$$
Implying that:
lim (of what variable as it goes to what value??) $[f(x^n+1 ) - f(x^n ) - t nabla f(x^n ) cdot d^n]/t = 0$
There seems to be no indication of what variable/limit the o() is referring to in the notes. Should this be obvious?
Edit: Despite the answer below, I still have no idea how to interpret the above equation (and similar ones) from my lecture notes. From my perspective there seems to be a lack of information. If anyone has other answers please post them and I'll flag whichever answer makes this clearer for me.
limits optimization algorithms approximation
asked Jul 23 at 5:57
Elliott Smith
84
add a comment |Â
up vote
1
down vote
favorite
I am completely new to little-o notation, I came across it in a lecture about algorithmically approaching a function minimum:
$$
f(x^n+1) = f(x^n) + nabla f(x^n ) cdot (x^n+1 − x^n) + o( | x^n+1 − x^n | )
= f(x^n) + t nabla f(x^n ) cdot d^n + o(t)
$$
where t is a chosen length (larger $t$ makes for larger steps, but possibly less direct).
To try to understand this, I searched and found this simple explanation:
$$
f(x) = o(g(x)), textas xto x_0
$$
is equivalent to $lim_xto x_0 f(x)/g(x) = 0$;
pdf link
This explanation seems clear in itself, but I'm struggling to link it to the equation from my lecture notes. Can I rearrange the equation like this?
$$
f(x^n+1) - f(x^n) - t nabla f(x^n ) cdot d^n = o(t)
$$
Implying that:
lim (of what variable as it goes to what value??) $[f(x^n+1 ) - f(x^n ) - t nabla f(x^n ) cdot d^n]/t = 0$
There seems to be no indication of what variable/limit the o() is referring to in the notes. Should this be obvious?
Edit: Despite the answer below, I still have no idea how to interpret the above equation (and similar ones) from my lecture notes. From my perspective there seems to be a lack of information. If anyone has other answers please post them and I'll flag whichever answer makes this clearer for me.
limits optimization algorithms approximation
asked Jul 23 at 5:57
Elliott Smith
84
As long as we recognize that $x^n+1 = x^n + t d^n$, your rearrangement is ok, and you can write $lim_t to 0 left(f(x^n+1) - f(x^n) - t nabla f(x^n) cdot d^n right)/t = 0$.
– littleO
Jul 23 at 6:10
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
I am completely new to little-o notation, I came across it in a lecture about algorithmically approaching a function minimum:
$$
f(x^n+1) = f(x^n) + nabla f(x^n ) cdot (x^n+1 − x^n) + o( | x^n+1 − x^n | )
= f(x^n) + t nabla f(x^n ) cdot d^n + o(t)
$$
where t is a chosen length (larger $t$ makes for larger steps, but possibly less direct).
To try to understand this, I searched and found this simple explanation:
$$
f(x) = o(g(x)), textas xto x_0
$$
is equivalent to $lim_xto x_0 f(x)/g(x) = 0$;
pdf link
This explanation seems clear in itself, but I'm struggling to link it to the equation from my lecture notes. Can I rearrange the equation like this?
$$
f(x^n+1) - f(x^n) - t nabla f(x^n ) cdot d^n = o(t)
$$
Implying that:
lim (of what variable as it goes to what value??) $[f(x^n+1 ) - f(x^n ) - t nabla f(x^n ) cdot d^n]/t = 0$
There seems to be no indication of what variable/limit the o() is referring to in the notes. Should this be obvious?
Edit: Despite the answer below, I still have no idea how to interpret the above equation (and similar ones) from my lecture notes. From my perspective there seems to be a lack of information. If anyone has other answers please post them and I'll flag whichever answer makes this clearer for me.
limits optimization algorithms approximation
asked Jul 23 at 5:57
Elliott Smith
84
I am completely new to little-o notation, I came across it in a lecture about algorithmically approaching a function minimum:
$$
f(x^n+1) = f(x^n) + nabla f(x^n ) cdot (x^n+1 − x^n) + o( | x^n+1 − x^n | )
= f(x^n) + t nabla f(x^n ) cdot d^n + o(t)
$$
where t is a chosen length (larger $t$ makes for larger steps, but possibly less direct).
To try to understand this, I searched and found this simple explanation:
$$
f(x) = o(g(x)), textas xto x_0
$$
is equivalent to $lim_xto x_0 f(x)/g(x) = 0$;
pdf link
This explanation seems clear in itself, but I'm struggling to link it to the equation from my lecture notes. Can I rearrange the equation like this?
$$
f(x^n+1) - f(x^n) - t nabla f(x^n ) cdot d^n = o(t)
$$
Implying that:
lim (of what variable as it goes to what value??) $[f(x^n+1 ) - f(x^n ) - t nabla f(x^n ) cdot d^n]/t = 0$
There seems to be no indication of what variable/limit the o() is referring to in the notes. Should this be obvious?
Edit: Despite the answer below, I still have no idea how to interpret the above equation (and similar ones) from my lecture notes. From my perspective there seems to be a lack of information. If anyone has other answers please post them and I'll flag whichever answer makes this clearer for me.
limits optimization algorithms approximation
asked Jul 23 at 5:57
Elliott Smith
84
edited Jul 31 at 2:54
asked Jul 23 at 5:57
Elliott Smith
84
asked Jul 23 at 5:57
Elliott Smith
84
asked Jul 23 at 5:57
Elliott Smith
84
84
As long as we recognize that $x^n+1 = x^n + t d^n$, your rearrangement is ok, and you can write $lim_t to 0 left(f(x^n+1) - f(x^n) - t nabla f(x^n) cdot d^n right)/t = 0$.
– littleO
Jul 23 at 6:10
add a comment |Â
As long as we recognize that $x^n+1 = x^n + t d^n$, your rearrangement is ok, and you can write $lim_t to 0 left(f(x^n+1) - f(x^n) - t nabla f(x^n) cdot d^n right)/t = 0$.
– littleO
Jul 23 at 6:10
As long as we recognize that $x^n+1 = x^n + t d^n$, your rearrangement is ok, and you can write $lim_t to 0 left(f(x^n+1) - f(x^n) - t nabla f(x^n) cdot d^n right)/t = 0$.
– littleO
Jul 23 at 6:10
As long as we recognize that $x^n+1 = x^n + t d^n$, your rearrangement is ok, and you can write $lim_t to 0 left(f(x^n+1) - f(x^n) - t nabla f(x^n) cdot d^n right)/t = 0$.
– littleO
Jul 23 at 6:10
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
0
down vote
accepted
So you have:
$$f(x^n+1)=f(x^n)+t nabla f(x^n) cdot d^n + o(t).$$
This means exactly that in some implicitly defined limit, $fracf(x^n+1)-f(x^n)-tnabla f(x^n) cdot d^nt to 0$. The relevant limit here is as $t to 0$. There isn't really a general rule to determine that, so when things might not be clear, it should be specified explicitly, rather than left to context. But here it is clear because this relationship is just giving the error estimate for the linear approximation of $f$ near $x^n$, going in the direction $d^n$.
answered Jul 31 at 3:07
Ian
65k24681
add a comment |Â
up vote
1
down vote
It means that in the expression
$$f(x^n+1) = f(x^n) + t nabla f(x^n ) cdot d^n + o(t)$$
$o(t)$ indicates something going to zero faster than $t$, that is
$$o(t)=tcdotomega(t)$$
with $omega(t) to 0$ and therefore
$$lim_tto 0 fracf(x^n+1 ) - f(x^n ) - t nabla f(x^n ) cdot d^nt = lim_tto 0 ,omega(t)=0$$
answered Jul 23 at 6:16
gimusi
65.2k73583
Thanks gimusi. How did you know that the relevant variable is t? and that the limit is considered for t approaching 0? Why not another dependent variable? or perhaps an independent one where the function being compared to approaches 0 when the independent variable approaches some value? Perhaps I haven't provided enough information about the problem?
– Elliott Smith
Jul 23 at 8:13
@ElliottSmith I've given a general interpretation for the meaning of $o(t)$ without any specific insight to the particular context. From the given we have $t=||x^n+1-x^n||to 0$ and for the definition of $o(t)$ that is the relevant variable.
– gimusi
Jul 23 at 8:22
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
accepted
So you have:
$$f(x^n+1)=f(x^n)+t nabla f(x^n) cdot d^n + o(t).$$
This means exactly that in some implicitly defined limit, $fracf(x^n+1)-f(x^n)-tnabla f(x^n) cdot d^nt to 0$. The relevant limit here is as $t to 0$. There isn't really a general rule to determine that, so when things might not be clear, it should be specified explicitly, rather than left to context. But here it is clear because this relationship is just giving the error estimate for the linear approximation of $f$ near $x^n$, going in the direction $d^n$.
answered Jul 31 at 3:07
Ian
65k24681
add a comment |Â
up vote
0
down vote
accepted
So you have:
$$f(x^n+1)=f(x^n)+t nabla f(x^n) cdot d^n + o(t).$$
This means exactly that in some implicitly defined limit, $fracf(x^n+1)-f(x^n)-tnabla f(x^n) cdot d^nt to 0$. The relevant limit here is as $t to 0$. There isn't really a general rule to determine that, so when things might not be clear, it should be specified explicitly, rather than left to context. But here it is clear because this relationship is just giving the error estimate for the linear approximation of $f$ near $x^n$, going in the direction $d^n$.
answered Jul 31 at 3:07
Ian
65k24681
add a comment |Â
up vote
0
down vote
accepted
up vote
0
down vote
accepted
So you have:
$$f(x^n+1)=f(x^n)+t nabla f(x^n) cdot d^n + o(t).$$
This means exactly that in some implicitly defined limit, $fracf(x^n+1)-f(x^n)-tnabla f(x^n) cdot d^nt to 0$. The relevant limit here is as $t to 0$. There isn't really a general rule to determine that, so when things might not be clear, it should be specified explicitly, rather than left to context. But here it is clear because this relationship is just giving the error estimate for the linear approximation of $f$ near $x^n$, going in the direction $d^n$.
answered Jul 31 at 3:07
Ian
65k24681
So you have:
$$f(x^n+1)=f(x^n)+t nabla f(x^n) cdot d^n + o(t).$$
This means exactly that in some implicitly defined limit, $fracf(x^n+1)-f(x^n)-tnabla f(x^n) cdot d^nt to 0$. The relevant limit here is as $t to 0$. There isn't really a general rule to determine that, so when things might not be clear, it should be specified explicitly, rather than left to context. But here it is clear because this relationship is just giving the error estimate for the linear approximation of $f$ near $x^n$, going in the direction $d^n$.
answered Jul 31 at 3:07
Ian
65k24681
answered Jul 31 at 3:07
Ian
65k24681
answered Jul 31 at 3:07
Ian
65k24681
answered Jul 31 at 3:07
Ian
65k24681
65k24681
add a comment |Â
add a comment |Â
up vote
1
down vote
It means that in the expression
$$f(x^n+1) = f(x^n) + t nabla f(x^n ) cdot d^n + o(t)$$
$o(t)$ indicates something going to zero faster than $t$, that is
$$o(t)=tcdotomega(t)$$
with $omega(t) to 0$ and therefore
$$lim_tto 0 fracf(x^n+1 ) - f(x^n ) - t nabla f(x^n ) cdot d^nt = lim_tto 0 ,omega(t)=0$$
answered Jul 23 at 6:16
gimusi
65.2k73583
Thanks gimusi. How did you know that the relevant variable is t? and that the limit is considered for t approaching 0? Why not another dependent variable? or perhaps an independent one where the function being compared to approaches 0 when the independent variable approaches some value? Perhaps I haven't provided enough information about the problem?
– Elliott Smith
Jul 23 at 8:13
@ElliottSmith I've given a general interpretation for the meaning of $o(t)$ without any specific insight to the particular context. From the given we have $t=||x^n+1-x^n||to 0$ and for the definition of $o(t)$ that is the relevant variable.
– gimusi
Jul 23 at 8:22
add a comment |Â
up vote
1
down vote
It means that in the expression
$$f(x^n+1) = f(x^n) + t nabla f(x^n ) cdot d^n + o(t)$$
$o(t)$ indicates something going to zero faster than $t$, that is
$$o(t)=tcdotomega(t)$$
with $omega(t) to 0$ and therefore
$$lim_tto 0 fracf(x^n+1 ) - f(x^n ) - t nabla f(x^n ) cdot d^nt = lim_tto 0 ,omega(t)=0$$
answered Jul 23 at 6:16
gimusi
65.2k73583
Thanks gimusi. How did you know that the relevant variable is t? and that the limit is considered for t approaching 0? Why not another dependent variable? or perhaps an independent one where the function being compared to approaches 0 when the independent variable approaches some value? Perhaps I haven't provided enough information about the problem?
– Elliott Smith
Jul 23 at 8:13
@ElliottSmith I've given a general interpretation for the meaning of $o(t)$ without any specific insight to the particular context. From the given we have $t=||x^n+1-x^n||to 0$ and for the definition of $o(t)$ that is the relevant variable.
– gimusi
Jul 23 at 8:22
add a comment |Â
up vote
1
down vote
up vote
1
down vote
It means that in the expression
$$f(x^n+1) = f(x^n) + t nabla f(x^n ) cdot d^n + o(t)$$
$o(t)$ indicates something going to zero faster than $t$, that is
$$o(t)=tcdotomega(t)$$
with $omega(t) to 0$ and therefore
$$lim_tto 0 fracf(x^n+1 ) - f(x^n ) - t nabla f(x^n ) cdot d^nt = lim_tto 0 ,omega(t)=0$$
answered Jul 23 at 6:16
gimusi
65.2k73583
It means that in the expression
$$f(x^n+1) = f(x^n) + t nabla f(x^n ) cdot d^n + o(t)$$
$o(t)$ indicates something going to zero faster than $t$, that is
$$o(t)=tcdotomega(t)$$
with $omega(t) to 0$ and therefore
$$lim_tto 0 fracf(x^n+1 ) - f(x^n ) - t nabla f(x^n ) cdot d^nt = lim_tto 0 ,omega(t)=0$$
answered Jul 23 at 6:16
gimusi
65.2k73583
answered Jul 23 at 6:16
gimusi
65.2k73583
answered Jul 23 at 6:16
gimusi
65.2k73583
answered Jul 23 at 6:16
gimusi
65.2k73583
65.2k73583
Thanks gimusi. How did you know that the relevant variable is t? and that the limit is considered for t approaching 0? Why not another dependent variable? or perhaps an independent one where the function being compared to approaches 0 when the independent variable approaches some value? Perhaps I haven't provided enough information about the problem?
– Elliott Smith
Jul 23 at 8:13
@ElliottSmith I've given a general interpretation for the meaning of $o(t)$ without any specific insight to the particular context. From the given we have $t=||x^n+1-x^n||to 0$ and for the definition of $o(t)$ that is the relevant variable.
– gimusi
Jul 23 at 8:22
add a comment |Â
Thanks gimusi. How did you know that the relevant variable is t? and that the limit is considered for t approaching 0? Why not another dependent variable? or perhaps an independent one where the function being compared to approaches 0 when the independent variable approaches some value? Perhaps I haven't provided enough information about the problem?
– Elliott Smith
Jul 23 at 8:13
@ElliottSmith I've given a general interpretation for the meaning of $o(t)$ without any specific insight to the particular context. From the given we have $t=||x^n+1-x^n||to 0$ and for the definition of $o(t)$ that is the relevant variable.
– gimusi
Jul 23 at 8:22
Thanks gimusi. How did you know that the relevant variable is t? and that the limit is considered for t approaching 0? Why not another dependent variable? or perhaps an independent one where the function being compared to approaches 0 when the independent variable approaches some value? Perhaps I haven't provided enough information about the problem?
– Elliott Smith
Jul 23 at 8:13
Thanks gimusi. How did you know that the relevant variable is t? and that the limit is considered for t approaching 0? Why not another dependent variable? or perhaps an independent one where the function being compared to approaches 0 when the independent variable approaches some value? Perhaps I haven't provided enough information about the problem?
– Elliott Smith
Jul 23 at 8:13
@ElliottSmith I've given a general interpretation for the meaning of $o(t)$ without any specific insight to the particular context. From the given we have $t=||x^n+1-x^n||to 0$ and for the definition of $o(t)$ that is the relevant variable.
– gimusi
Jul 23 at 8:22
@ElliottSmith I've given a general interpretation for the meaning of $o(t)$ without any specific insight to the particular context. From the given we have $t=||x^n+1-x^n||to 0$ and for the definition of $o(t)$ that is the relevant variable.
– gimusi
Jul 23 at 8:22
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2860050%2flittle-o-meaning-in-equation%23new-answer', 'question_page');
);
Post as a guest
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
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
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
As long as we recognize that $x^n+1 = x^n + t d^n$, your rearrangement is ok, and you can write $lim_t to 0 left(f(x^n+1) - f(x^n) - t nabla f(x^n) cdot d^n right)/t = 0$.
– littleO
Jul 23 at 6:10