text:
Spectral Singularity in confined PT symmetric optical potential    [PDF]

Anjana Sinha, R. Roychoudhury
We present an analytical study for the scattering amplitudes (Reflection |R| and Transmission |T|), of the periodic PT symmetric optical potential V(x) = W_0 cos^2 x + i W_0 V_0 sin 2x confined within the region 0 < x < L, embedded in a homogeneous medium having uniform potential W_0. The confining length L is considered to be some multiple of the period D. We give some new and interesting results. Scattering is observed to be normal (|T|^2 \leq 1, |R|^2 \leq 1) for V_0 < 0.5, when the above potential can be mapped to a Hermitian potential by a similarity transformation. However, |R|^2 and |T|^2 do not necessarily add up to unity. Beyond this point (V_0 > 0.5) scattering is found to be anomalous (|T|^2, |R|^2 not necessarily \leq 1). Additionally, in this parameter regime of V_0, one observes infinite number of spectral singularities E_{SS} at different values of V_0. Furthermore, for L = 2n \pi, the transition point V_0 = 0.5 shows unidirectional invisibility with zero reflection when the beam is incident from the absorptive side (Im[V(x)] < 0) but finite reflection when the beam is incident from the emissive side (Im[V(x)] > 0), transmission being identically unity in both cases.
View original: http://arxiv.org/abs/1307.1844


text:
BREAKING NEWS
Periodic sequence

## Summary

In mathematics, a periodic sequence (sometimes called a cycle[citation needed]) is a sequence for which the same terms are repeated over and over:

a1, a2, ..., ap,  a1, a2, ..., ap,  a1, a2, ..., ap, ...[citation needed]

The number p of repeated terms is called the period (period).[1]

## Definition

A (purely) periodic sequence (with period p), or a p-periodic sequence, is a sequence a1, a2, a3, ... satisfying One size fits all

an+p = an

[2] for all values of n.[1][3][4][5][6] If a sequence is regarded as a function whose domain is the set of natural numbers, then a periodic sequence is simply a special type of periodic function.[citation needed] The smallest p for which a periodic sequence is p-periodic is called its least period[1][7] or exact period.[7][verification needed]

## Examples

Every constant function is 1-periodic.[5]

The sequence ${\displaystyle 1,2,1,2,1,2\dots }$  is periodic with least period 2.[3]

The sequence of digits in the decimal expansion of 1/7 is periodic with period 6:

${\displaystyle {\frac {1}{7}}=0.142857\,142857\,142857\,\ldots }$

More generally, the sequence of digits in the decimal expansion of any rational number is eventually periodic (see below).[8][verification needed]

The sequence of powers of −1 is periodic with period two:

${\displaystyle -1,1,-1,1,-1,1,\ldots }$

More generally, the sequence of powers of any root of unity is periodic. The same holds true for the powers of any element of finite order in a group.[citation needed]

A periodic point for a function f : XX is a point x whose orbit

${\displaystyle x,\,f(x),\,f(f(x)),\,f^{3}(x),\,f^{4}(x),\,\ldots }$

is a periodic sequence. Here, ${\displaystyle f^{n}(x)}$  means the n-fold composition of f applied to x.[7][verification needed] Periodic points are important in the theory of dynamical systems. Every function from a finite set to itself has a periodic point; cycle detection is the algorithmic problem of finding such a point.[citation needed]

## Identities

### Partial Sums

${\displaystyle \sum _{n=1}^{kp+m}a_{n}=k*\sum _{n=1}^{p}a_{n}+\sum _{n=1}^{m}a_{n}}$  Where k and m<p are natural numbers.[citation needed]

### Partial Products

${\displaystyle \prod _{n=1}^{kp+m}a_{n}=({\prod _{n=1}^{p}a_{n}})^{k}*\prod _{n=1}^{m}a_{n}}$  Where k and m<p are natural numbers.[citation needed]

## Periodic 0, 1 sequences

Any periodic sequence can be constructed by element-wise addition, subtraction, multiplication and division of periodic sequences consisting of zeros and ones. Periodic zero and one sequences can be expressed as sums of trigonometric functions:

${\displaystyle \sum _{k=1}^{1}\cos(-\pi {\frac {n(k-1)}{1}})/1=1,1,1,1,1,1,1,1,1...}$
${\displaystyle \sum _{k=1}^{2}\cos(2\pi {\frac {n(k-1)}{2}})/2=0,1,0,1,0,1,0,1,0...}$
${\displaystyle \sum _{k=1}^{3}\cos(2\pi {\frac {n(k-1)}{3}})/3=0,0,1,0,0,1,0,0,1,0,0,1,0,0,1...}$
${\displaystyle ...}$
${\displaystyle \sum _{k=1}^{N}\cos(2\pi {\frac {n(k-1)}{N}})/N=0,0,0...,1{\text{ sequence with period }}N}$ [citation needed][clarification needed]

## Generalizations

A sequence is eventually periodic if it can be made periodic by dropping some finite number of terms from the beginning. For example, the sequence of digits in the decimal expansion of 1/56 is eventually periodic:

1 / 56 = 0 . 0 1 7  8 5 7 1 4 2  8 5 7 1 4 2  8 5 7 1 4 2  ...[citation needed]

A sequence is ultimately periodic if it satisfies the condition ${\displaystyle a_{k+r}=a_{k}}$  for some r and sufficiently large k.[1]

A sequence is asymptotically periodic if its terms approach those of a periodic sequence. That is, the sequence x1x2x3, ... is asymptotically periodic if there exists a periodic sequence a1a2a3, ... for which

${\displaystyle \lim _{n\rightarrow \infty }x_{n}-a_{n}=0.}$ [5][9][10][verification needed]

For example, the sequence

1 / 3,  2 / 3,  1 / 4,  3 / 4,  1 / 5,  4 / 5,  ...

is asymptotically periodic, since its terms approach those of the periodic sequence 0, 1, 0, 1, 0, 1, ....[citation needed]

## References

1. ^ a b c d "Ultimately periodic sequence - Encyclopedia of Mathematics". encyclopediaofmath.org. 7 February 2011. Retrieved 13 August 2021.{{cite web}}: CS1 maint: url-status (link)
2. ^ John cDNA
3. ^ a b Weisstein, Eric W. "Periodic Sequence". mathworld.wolfram.com. Retrieved 2021-08-13.
4. ^ Bosma, Wieb. "Complexity of Periodic Sequences" (PDF). www.math.ru.nl. Retrieved 13 August 2021.{{cite web}}: CS1 maint: url-status (link)
5. ^ a b c Janglajew, Klara; Schmeidel, Ewa (2012-11-14). "Periodicity of solutions of nonhomogeneous linear difference equations". Advances in Difference Equations. 2012 (1): 195. doi:10.1186/1687-1847-2012-195. ISSN 1687-1847. S2CID 122892501.
6. ^ Menezes, Alfred J.; Oorschot, Paul C. van; Vanstone, Scott A. (2018-12-07). Handbook of Applied Cryptography. CRC Press. ISBN 978-0-429-88132-9.
7. ^ a b c Weisstein, Eric W. "Least Period". mathworld.wolfram.com. Retrieved 2021-08-13.
8. ^ Hosch, William L. (1 June 2018). "Rational number". Encyclopedia Britannica. Retrieved 13 August 2021.{{cite web}}: CS1 maint: url-status (link)
9. ^ Cheng, SuiSun (2017-09-29). New Developments in Difference Equations and Applications: Proceedings of the Third International Conference on Difference Equations. Routledge. ISBN 978-1-351-42880-4.
10. ^ Shlezinger, Nir; Todros, Koby (2019-01-01). "Performance analysis of LMS filters with non-Gaussian cyclostationary signals" (PDF). Signal Processing. 154: 260–271. arXiv:1708.00635. doi:10.1016/j.sigpro.2018.08.008. ISSN 0165-1684. S2CID 53521677.

format: plain


text:
# Tetration Forum

Full Version: Could be tetration if this integral converges
You're currently viewing a stripped down version of our content. View the full version with proper formatting.
Pages: 1 2 3 4 5
(05/04/2014, 09:06 PM)JmsNxn Wrote: [ -> ]As a note on a similar technique you are applying Mike but trying to keep the vibe much more fractional calculus'y (since it's what I am familiar with) We will try the following function:

$0 < \lambda$ We want $\lambda$ fairly small

$\beta(w) = \sum_{n=0}^\infty \frac{w^n}{n!(^n e)}$

We know that $|\beta(w)| < C e^{\kappa |w|}$ for $\kappa > 0$ because $\frac{1}{(^n e)} < C_\kappa \kappa^n$

So that $\Re(z) > 0$.

$F(-z) = \frac{1}{\Gamma(z)}\int_0^\infty e^{-\lambda x}\beta(-x)x^{z-1} \,dx$

This function should be smaller then tetration at natural values.

$F(n) = \sum_{j=0}^n \frac{n!(-\lambda)^{n-j}}{j!(n-j)!(^j e)}$

We would get the entire expression for $F(z)$ by Lemma 3 of my paper:

$F(z) = \frac{1}{\Gamma(-z)}(\sum_{n=0}^\infty F(n)\frac{(-1)^n}{n!(n-z)} + \int_1^\infty e^{-\lambda x} \beta(-x)x^{z-1}\,dx)$

Now F(z) will be susceptible to alot of the techniques I have in my belt involving fractional calculus. This Idea just popped into my head but I'm thinking working with a function like this will pull down the imaginary behaviour and pull down the real behaviour.

We also note that

$e^{F(z) }\approx F(z+1)$. Which again will be more obvious if you look at the paper, but it basically follows because:

$F(n) \approx (^n e)$

So is this $F$ supposed to approximate tetration if $\lambda$ is small? As if so, then it doesn't seem to be working for me. If I take $\lambda = 0.01$ and the integral upper bound at 2000, I get $F(1.5)$ as ~443444.33873479713260158296678612894384. Clearly, that can't be right -- it should be between $e$ and $e^e$ (if this is supposed to reproduce the Kneser tetrational then it should be ~5.1880309584291901006085359610758671512). It gets worse the smaller you make $\lambda$ -- i.e. it doesn't seem to converge. Also, picking values to put in that are near-natural numbers doesn't seem to work, either.
(05/05/2014, 01:00 AM)mike3 Wrote: [ -> ]
(05/04/2014, 03:28 PM)sheldonison Wrote: [ -> ]What are the values for F (0,1,2,3)?

$^0 e$, $^1 e$, $^2 e$, $^3 e$, ... .
Very nice. I didn't have time to figure out why F is "an entire interpolant" for tetration until this morning. This version behaves a little better at the real axis.
$F(z) = \sum_{n=0}^{\infty} e^{(^{n-1} e) (z - n + 1)} \frac{(-1)^n \sin(\pi z)}{\pi (z - n)}$

- Sheldon

(05/05/2014, 02:11 AM)mike3 Wrote: [ -> ]
(05/04/2014, 09:06 PM)JmsNxn Wrote: [ -> ]$F(n) = \sum_{j=0}^n \frac{n!(-\lambda)^{n-j}}{j!(n-j)!(^j e)}$

So is this $F$ supposed to approximate tetration if $\lambda$ is small? As if so, then it doesn't seem to be working for me. If I take $\lambda = 0.01$ and the integral upper bound at 2000, I get $F(1.5)$ as ~443444.33873479713260158296678612894384. Clearly, that can't be right -- it should be between $e$ and $e^e$ (if this is supposed to reproduce the Kneser tetrational then it should be ~5.1880309584291901006085359610758671512). It gets worse the smaller you make $\lambda$ -- i.e. it doesn't seem to converge. Also, picking values to put in that are near-natural numbers doesn't seem to work, either.
I'll note firstly that

$F(n) = \sum_{j=0}^n \frac{n!\lambda^{n-j}}{j!(n-j)!(^j e)}$

I accidentally added an extra negative. But that doesn't really affect convergence. I understand whats happening.

Hmm. That makes sense now that I think about it. I was hoping you could take lambda small but not too small and it wouldn't diverge too fast but because obviously $\lambda = 0$ diverges this doesn't happen. Maybe if you try $\lambda = 1$ I've done more research into this form of the operator so perhaps we can work with this one.

$F(n) = \sum_{j=0}^n \frac{(-1)^{n-j} n!}{j!(n-j)!(^j e)}$

I do have a nice result that will work for these operators that is slightly off topic but is related to continuum sums. If $\beta = \sum_{n=0}^\infty \frac{x^n}{n!(^n e)}$ is as before and $z \in \mathbb{C}$:

$\frac{d^{-z}}{dx^{-z}}|_{x=0} e^{x}\beta(-x)= F(-z) = \frac{1}{\G(z)}(\sum_{n=0}^\infty F(n) \frac{1}{n!(n+z)} + \int_1^\infty e^{-x}\beta(x)x^{z-1}\,dx)$

Quite fantabulously if $\bigtriangledown F(-z) = F(1-z) - F(-z)$ we get the really interesting result:

$\bigtriangledown^n F(-z) = \frac{d^{-z}}{dx^{-z}}|_{x=0} e^x \beta^{(n)}(x)$

And of course:

$[\bigtriangledown^n F(-z)]_{z=0} = \frac{1}{(^n e)}$

I'm a little fuzzy on the following but if we use a fractional iteration of $\bigtriangledown$ we can find a very nice interpolant of $(^n e)$. Since it's all using fractional calculus I have an impressionistic vision of how a similar proof of recursion would go (picking a certain fractional iteration of $\bigtriangledown$ I have in my mind and then using a similar contour integral technique).

I'm really intrigued by this idea but I think I have a more general result we need. I wonder if there exists a theorem in complex analysis on the following.

If $\phi(z)$ is holomorphic on $\Re(z) > -b$ does there exist some holomorphic function $\pi(z)\neq 0$ holomorphic on $\Re(z) > -b$ such that:

$|\pi(z)\phi(z)|, |\pi(z)\phi(z+1)| < C e^{\alpha |\Im(z)| + \rho|\Re(z)|}$ for $0 \le \alpha < \pi/2$ and $\rho \ge 0$

such that $\pi$ satisfies some conditions I'm not sure of yet. It cannot interpolate $\phi(n)$, it cannot interpolate the inverse and it cannot be a fair amount of obvious easy functions.
OMG. FOund a very nice theorem in complex analysis. I found it referenced in this paper.

http://algo.inria.fr/seminars/sem01-02/delabaere2.pdf

[4] Boas, Jr. (Ralph Philip). – Entire functions. – Academic Press, New York, 1954, x+276p.

It says that:
"In fact, if a and b are two [holomorphic] functions that are of exponential type α < π, if a(n) = b(n) for all
n ≥ 1, then a = b, due to a theorem by Carlson [4]."

THEREfore if:

$|\psi(z)|,|\phi(z)| < C e^{\alpha|\Im(z)| + \rho|\Re(z)|}$ for $0 \le \alpha < \pi/2$ and $0 \le \rho < \pi$

We know $\psi(n) = \phi(n)$ implies $\psi = \phi$!!!!!

This is a nice uniqueness result.
(05/05/2014, 06:18 PM)JmsNxn Wrote: [ -> ]OMG. FOund a very nice theorem in complex analysis. I found it referenced in this paper.

http://algo.inria.fr/seminars/sem01-02/delabaere2.pdf

[4] Boas, Jr. (Ralph Philip). – Entire functions. – Academic Press, New York, 1954, x+276p.

It says that:
"In fact, if a and b are two [holomorphic] functions that are of exponential type α < π, if a(n) = b(n) for all
n ≥ 1, then a = b, due to a theorem by Carlson [4]."

THEREfore if:

$|\psi(z)|,|\phi(z)| < C e^{\alpha|\Im(z)| + \rho|\Re(z)|}$ for $0 \le \alpha < \pi/2$ and $0 \le \rho < \pi$

We know $\psi(n) = \phi(n)$ implies $\psi = \phi$!!!!!

This is a nice uniqueness result.

Actually I think this has been said here before.
(05/05/2014, 04:27 PM)JmsNxn Wrote: [ -> ]
(05/05/2014, 02:11 AM)mike3 Wrote: [ -> ]
(05/04/2014, 09:06 PM)JmsNxn Wrote: [ -> ]$F(n) = \sum_{j=0}^n \frac{n!(-\lambda)^{n-j}}{j!(n-j)!(^j e)}$

So is this $F$ supposed to approximate tetration if $\lambda$ is small? As if so, then it doesn't seem to be working for me. If I take $\lambda = 0.01$ and the integral upper bound at 2000, I get $F(1.5)$ as ~443444.33873479713260158296678612894384. Clearly, that can't be right -- it should be between $e$ and $e^e$ (if this is supposed to reproduce the Kneser tetrational then it should be ~5.1880309584291901006085359610758671512). It gets worse the smaller you make $\lambda$ -- i.e. it doesn't seem to converge. Also, picking values to put in that are near-natural numbers doesn't seem to work, either.
I'll note firstly that

$F(n) = \sum_{j=0}^n \frac{n!\lambda^{n-j}}{j!(n-j)!(^j e)}$

I accidentally added an extra negative. But that doesn't really affect convergence. I understand whats happening.

Hmm. That makes sense now that I think about it. I was hoping you could take lambda small but not too small and it wouldn't diverge too fast but because obviously $\lambda = 0$ diverges this doesn't happen. Maybe if you try $\lambda = 1$ I've done more research into this form of the operator so perhaps we can work with this one.

$F(n) = \sum_{j=0}^n \frac{(-1)^{n-j} n!}{j!(n-j)!(^j e)}$

Well I tried this $F$ and the integral also didn't seem to converge. Trying $\lambda = 1$ yields a finite value but the recurrence $F(z+1) = \exp(F(z))$ does not appear to hold, nor are the values close to those of the Kneser tetrational.

I noticed your discussion after this point about the continuum sum thing and you mentioned about fractional iteration of the difference operator. This is why I was curious as to how the integral definition for the Weyl differintegral related to its definition for periodic functions. In particular, if $f(z)$ is periodic with period $2\pi$, we have a Fourier series

$f(z) = \sum_{n=-\infty}^{\infty} a_n e^{inz)$.

We assume $a_0 = 0$. Then,

$D^s f(z) = \sum_{n=-\infty}^{\infty} a_n (in)^s e^{inz}$.

This is the Weyl differintegral. Note that taking $s = -1$ yields the integral (though we have to drop the term at $n = 0$).

Similarly, for the finite difference operator,

$\Delta^s f(z) = \sum_{n=-\infty}^{\infty} a_n (e^{in} - 1)^s e^{inz}$.

Note that taking $s = -1$ yields the continuum sum (though, again, we have to drop the term at $n = 0$).

Now, if the first expression for the differintegral can be generalized to certain non-periodic holomorphic functions via an integral transform, can that also be done for the second? Is there a method to derive the integral transform from the given definition in the first case? If so, can it be generalized to the second?
(05/05/2014, 11:45 PM)mike3 Wrote: [ -> ]
(05/05/2014, 04:27 PM)JmsNxn Wrote: [ -> ]
(05/05/2014, 02:11 AM)mike3 Wrote: [ -> ]
(05/04/2014, 09:06 PM)JmsNxn Wrote: [ -> ]$F(n) = \sum_{j=0}^n \frac{n!(-\lambda)^{n-j}}{j!(n-j)!(^j e)}$

So is this $F$ supposed to approximate tetration if $\lambda$ is small? As if so, then it doesn't seem to be working for me. If I take $\lambda = 0.01$ and the integral upper bound at 2000, I get $F(1.5)$ as ~443444.33873479713260158296678612894384. Clearly, that can't be right -- it should be between $e$ and $e^e$ (if this is supposed to reproduce the Kneser tetrational then it should be ~5.1880309584291901006085359610758671512). It gets worse the smaller you make $\lambda$ -- i.e. it doesn't seem to converge. Also, picking values to put in that are near-natural numbers doesn't seem to work, either.
I'll note firstly that

$F(n) = \sum_{j=0}^n \frac{n!\lambda^{n-j}}{j!(n-j)!(^j e)}$

I accidentally added an extra negative. But that doesn't really affect convergence. I understand whats happening.

Hmm. That makes sense now that I think about it. I was hoping you could take lambda small but not too small and it wouldn't diverge too fast but because obviously $\lambda = 0$ diverges this doesn't happen. Maybe if you try $\lambda = 1$ I've done more research into this form of the operator so perhaps we can work with this one.

$F(n) = \sum_{j=0}^n \frac{(-1)^{n-j} n!}{j!(n-j)!(^j e)}$

Well I tried this $F$ and the integral also didn't seem to converge. Trying $\lambda = 1$ yields a finite value but the recurrence $F(z+1) = \exp(F(z))$ does not appear to hold, nor are the values close to those of the Kneser tetrational.

I noticed your discussion after this point about the continuum sum thing and you mentioned about fractional iteration of the difference operator. This is why I was curious as to how the integral definition for the Weyl differintegral related to its definition for periodic functions. In particular, if $f(z)$ is periodic with period $2\pi$, we have a Fourier series

$f(z) = \sum_{n=-\infty}^{\infty} a_n e^{inz)$.

We assume $a_0 = 0$. Then,

$D^s f(z) = \sum_{n=-\infty}^{\infty} a_n (in)^s e^{inz}$.

This is the Weyl differintegral. Note that taking $s = -1$ yields the integral (though we have to drop the term at $n = 0$).

Similarly, for the finite difference operator,

$\Delta^s f(z) = \sum_{n=-\infty}^{\infty} a_n (e^{in} - 1)^s e^{inz}$.

Note that taking $s = -1$ yields the continuum sum (though, again, we have to drop the term at $n = 0$).

Now, if the first expression for the differintegral can be generalized to certain non-periodic holomorphic functions via an integral transform, can that also be done for the second? Is there a method to derive the integral transform from the given definition in the first case? If so, can it be generalized to the second?

If I understand your question correctly the answer is yes to both questions. I'll write it out. Using the operators from my paper we can completely represent the iterated difference:

$F(z) =[\frac{d^{-z}}{dx^{-z}}e^x \beta(-x)]_{x=0}$

then:

$\bigtriangledown^s F(z) = [\frac{d^{-z}}{dx^{-z}}e^x \frac{d^s}{d(-x)^s}\beta(-x)]_{x=0}$

I'm working on writing this all up. So far all I have is a bunch of notes and papers compiled together unorganized.

Now for the first question, to work on these periodic functions define:

$[\frac{d^z}{dw^z} f(w)]_{w=0} = \frac{1}{\G(-z)} (\sum_{n=0} f^{(n)}(0) \frac{(-1)^n}n!(n-z)} + \int_1^\infty f(-x)x^{-z-1}\,dx)$

And then we can generate the differintegral using taylor series. now if $p(w) = \sum_{n=1} a_n e^{inw}$

then
$\frac{d^{-z}}{dw^{-z}} p(w) = \frac{i^{-z}}{\G(z)} \int_0^\infty p(w + ix)x^{z-1}\,dx$
(05/06/2014, 12:11 AM)JmsNxn Wrote: [ -> ]If I understand your question correctly the answer is yes to both questions. I'll write it out. Using the operators from my paper we can completely represent the iterated difference:

$F(z) =[\frac{d^{-z}}{dx^{-z}}e^x \beta(-x)]_{x=0}$

then:

$\bigtriangledown^s F(z) = [\frac{d^{-z}}{dx^{-z}}e^x \frac{d^s}{d(-x)^s}\beta(-x)]_{x=0}$

I'm working on writing this all up. So far all I have is a bunch of notes and papers compiled together unorganized.

And the fractional derivatives can be written using the formula for the Weyl differintegral, thus an integral transform. So how do you get $\beta(x)$ from $F(z)$?

(05/06/2014, 12:11 AM)JmsNxn Wrote: [ -> ]Now for the first question, to work on these periodic functions define:

$[\frac{d^z}{dw^z} f(w)]_{w=0} = \frac{1}{\G(-z)} (\sum_{n=0} f^{(n)}(0) \frac{(-1)^n}n!(n-z)} + \int_1^\infty f(-x)x^{-z-1}\,dx)$

And then we can generate the differintegral using taylor series. now if $p(w) = \sum_{n=1} a_n e^{inw}$

then
$\frac{d^{-z}}{dw^{-z}} p(w) = \frac{i^{-z}}{\G(z)} \int_0^\infty p(w + ix)x^{z-1}\,dx$

But I was wondering if it was possible to work in the other direction, starting with the definition for periodic functions and then expanding it to the integral-transform definition, and so if something similar could be done for the forward difference operator.
(05/06/2014, 06:50 AM)mike3 Wrote: [ -> ]And the fractional derivatives can be written using the formula for the Weyl differintegral, thus an integral transform. So how do you get $\beta(x)$ from $F(z)$?

$F(z) = \frac{1}{\G(z)} \int_0^\infty \beta(x)x^{z-1}\,dx$

$\beta(x) = \frac{1}{2 \pi i} \int_{\sigma - i \infty}^{\sigma + i \infty} \G(z)F(z)x^{-z}\,dx$

If these integrals are absolutely convergent in the strip $a < \Re(z) = \sigma < b$

(05/06/2014, 06:50 AM)mike3 Wrote: [ -> ]But I was wondering if it was possible to work in the other direction, starting with the definition for periodic functions and then expanding it to the integral-transform definition, and so if something similar could be done for the forward difference operator.

Ohhhh I see. Sorry I've never actually read many papers on the periodic definition of the weyl differintegral. I've only read papers by Erdelyi and some others and they always talk about the weyl differintegral starting from the transform that I use.

I'm certain something similar can be done to the forward difference operator. It won't look as elegant I think though.
(05/06/2014, 03:54 PM)JmsNxn Wrote: [ -> ]
(05/06/2014, 06:50 AM)mike3 Wrote: [ -> ]And the fractional derivatives can be written using the formula for the Weyl differintegral, thus an integral transform. So how do you get $\beta(x)$ from $F(z)$?

$F(z) = \frac{1}{\G(z)} \int_0^\infty \beta(x)x^{z-1}\,dx$

$\beta(x) = \frac{1}{2 \pi i} \int_{\sigma - i \infty}^{\sigma + i \infty} \G(z)F(z)x^{-z}\,dx$

If these integrals are absolutely convergent in the strip $a < \Re(z) = \sigma < b$

(05/06/2014, 06:50 AM)mike3 Wrote: [ -> ]But I was wondering if it was possible to work in the other direction, starting with the definition for periodic functions and then expanding it to the integral-transform definition, and so if something similar could be done for the forward difference operator.

Ohhhh I see. Sorry I've never actually read many papers on the periodic definition of the weyl differintegral. I've only read papers by Erdelyi and some others and they always talk about the weyl differintegral starting from the transform that I use.

I'm certain something similar can be done to the forward difference operator. It won't look as elegant I think though.

Is there a mistake in the above integrals? In the integral for $\beta(x)$, $x$ appears as both function argument and as dummy variable inside the integral. Do you mean $\beta(z)$? But if that's so, then what's the need for the integral -- the $\Gamma(z)$ and $F(z)$ do not depend on the integration variable and so come out, leaving you with only the integral of the power function, which can be solved explicitly?

Or do you mean

$\beta(z) = \frac{1}{2\pi i} \int_{\sigma - i \infty}^{\sigma + i \infty} \Gamma(x) F(x) x^{-z} dx$

?

Also, what about what I mentioned earlier with regard to the tetration integral not working?
Pages: 1 2 3 4 5


text:
# Prony’s method (Polyreference)

## Introduction

I am re-reviewing the bible-like book “Introduction to Modal Analysis,” which every Japanese vibration engineer has read at least once.

I would like to explain what I have learned in the re-review, showing the MATLAB code. This time, we will review from section 6.3.2, “Prony Method,” p. 367. The “poly-reference method” is an extension of the Prony method to the multipoint reference method. (also called “Vold’s method” since it was drafted by Vold).

The mode identification method with a function called modalfit, introduced in the Signal Processing Toolbox of MATLAB2017a, can also be solved by the “Prony method”. Please refer to MathWorks’ website for details. Incidentally, “FitMethod”=”lsce”, the default mode identification method of modalfit, is explained as the Prony method.

The following link is a summary to a description of vibration theory in English, if you are interested.

TopPage 振動騒音 研究所
MATLABとNVH(Noise, Vibration and Harshness)をこよなく愛する人生の先輩、それが私（MATLABパイセン）です。NVHを極めるにあたり、周辺の知識も網羅的に勉強することになり、その知識を共有すべく、本HPを運営しています。日本の製造業を応援すべく、機械エンジニアの「車輪の再開発」の防止と業務効率化の手助けをモットーに活動。専門である振動騒音工学や音響工学について、プログラムを示しながら解説。大学の授業よりもわかりやすく説明することを目指す。質問頂ければ、回答したいと思います。

## 6.3.2 Prony’s method

In previous articles, I have explained that FRFs and vibration shapes can be expressed as a superposition of modal characteristics (resonant frequencies & vibration modes, etc.). It is the concept of modal analysis. And extracting mode characteristics from FRF is called mode identification or curve fitteing.

The mode circle fitting (curve fitting) and half-width method were applicable only when the adjacent resonance frequencies are far enough apart, as in the red frequency band in Figure 1, and the system can be regarded as a one-degree-of-freedom system.

Figure 1 FRF

On the other hand, Prony’s method is a mode identification method for multi-degree-of-freedom systems. In other words, it is a method that can extract the mode characteristics of each resonance frequency even if it contains multiple resonance frequencies, such as the 0 to 100 Hz data in Figure 1.

From here, the explanation becomes a bit more technical.
Prony’s method is a method to estimate modal characteristics from impulse response data. Although it is possible to use time history data of the response of impact excitation with an impact hammer, etc., it is known that the signal-to-noise ratio is generally bad, and in many cases, data obtained by IFFT of FRF averaged over the number of measurements and then the data, converted back to impulse response, is used as input for the Prony’s method.

Since the impulse response can be expressed as a superposition of mode characteristics, it can be expressed as in Equation (6.52).

$$h(t)=\sum_{r=1}^{N} a_{r}(je^{λ_r t} – je^{λ_r^* t} ) \tag{6.52}$$

where λr is the eigenvalue, ωdr is the damped natural angular frequency, and σr is the modal damping factor, detailed in the equation below.

$$a_r=\frac{ Ω_r^2 }{2ω_{dr}K_r}, λ_r=-σ_r + jω_{dr}, λ_r^*=-σ_r – jω_{dr} \tag{6.51}$$

However, rather than the above equation, it is better to just remember that ar is the residu, λr is the eigenvalue, ωdr is the damped natural angular frequency, and σr is the modal damping rate.

Again, mode identification means finding the distn ar and eigenvalue λr.
There are various methods for mode identification, but they differ only in their approach to finding the abscissa ar and eigenvalue λr.

Since the data are discretized, equation (6.53) can be expressed in a discretized form for time t as in equation (6.54). Note that i is the data id. It is assumed that only n (n<N) of N are to be identified, rather than all N, the number of all resonance frequencies.

$$h(iΔt)=\sum_{r=1}^{n} a_{r}(e^{λ_r iΔt} – e^{λ_r^* iΔt} ) \tag{6.52}$$

Here, since the character expression is complicated, it is replaced by the following for simplicity.

$$x_r=e^{λ_r Δt}, x_r^*=e^{λ_r^* Δt} \tag{6.55}$$

Then it can be expressed as in equation (6.56).

$$h(iΔt)=\sum_{r=1}^{n} a_{r}(x_r^i + x_r^{i*} )=\sum_{r=1}^{n} real( 2a_{r}(x_r^i ) )=\sum_{r=1}^{2n} a_{r}(x_r^i ) \tag{6.56}$$

I think some of you may not understand the equation expansion of equation (6.56). Originally, the expansion was based on the assumption that n resonance frequencies are to be identified, but since it is more coherent to identify 2n resonance frequencies, the number of resonance frequencies is 2n.

You can manage to get to this point.
Equation (6.56) is just a repeated transformation of the equation, and as it is, we can’t extract the distnumber ar and eigenvalue λr, can we?

For now, let’s consider equation (6.56) in a simplified form, with n=2 and i=0,1,2,3,4.

$$h(0)=a_1 x_1^0 + a_2 x_2^0 + a_3 x_3^0 + a_4 x_4^0 \\ h(1)=a_1 x_1^1 + a_2 x_2^1+ a_3 x_3^1 + a_4 x_4^1 \\ h(2)=a_1 x_1^2 + a_2 x_2^2 + a_3 x_3^2 + a_4 x_4^2 \\ h(3)=a_1 x_1^3 + a_2 x_2^3 + a_3 x_3^3 + a_4 x_4^3 \\ h(4)=a_1 x_1^4 + a_2 x_2^4 + a_3 x_3^4 + a_4 x_4^4$$
$$\tag{6.56.0}$$

In this situation, we can’t extract the abstention number ar and eigenvalue λr, can we?

So, consider the following.

$$(x-x_1)(x-x_1^*)(x-x_2)(x-x_2^*) =0 \tag{6.57.3}$$

Since it is difficult to calculate by hand, we replace it with the following so that it can be solved by Maxima.

$$(x-a1)(x-c1)(x-a2)(x-c2) =0$$

Expanding the above equation, we get

$$x^4 \\ +(-c2-c1-a2-a1)x^3 \\ +(c1*c2+a2*c2+a1*c2+a2*c1+a1*c1+a1*a2)x^2 \\ +(-a2*c1*c2-a1*c1*c2-a1*a2*c2-a1*a2*c1)x \\ +a1*a2*c1*c2 =0$$
$$\tag{6.57.0}$$

Replace the above with the following. Note that b4=1 here.

$$b_4 x^4 \\ +b_3 x^3 \\ +b_2 x^2 \\ +b_1 x^1 \\ +b_0 x^0 =0$$
$$\tag{6.57.1}$$

Equation (6.57.1) is a generalization of equation (6.57).

$$\sum_{i=0}^{2n}b_i x^i =0 \tag{6.57}$$

Now we will consider how to extract the abstention number ar and the eigenvalue λr, comparing equations (6.56.0) and (6.57.1). For now, let us multiply both sides of equation (6.56.0) by bi.

$$b_0 h(0)=b_0 (a_1 x_1^0 + a_2 x_2^0 + a_3 x_3^0 + a_4 x_4^0) \\ b_1 h(1)=b_1 (a_1 x_1^1 + a_2 x_2^1+ a_3 x_3^1 + a_4 x_4^1) \\ b_2 h(2)=b_2 (a_1 x_1^2 + a_2 x_2^2 + a_3 x_3^2 + a_4 x_4^2) \\ b_3 h(3)=b_3 (a_1 x_1^3 + a_2 x_2^3 + a_3 x_3^3 + a_4 x_4^3) \\ b_4 h(4)=b_4 (a_1 x_1^4 + a_2 x_2^4 + a_3 x_3^4 + a_4 x_4^4)$$
$$\tag{6.60.0}$$

All of equation (6.60.0) can be added together and summarized as follows

$$\sum_{i=0}^{2*2}b_i h(i) = a_1 \sum_{i=0}^{2*2}b_i x_1^i +a_2 \sum_{i=0}^{2*2}b_i x_1^i +a_3 \sum_{i=0}^{2*2}b_i x_3^i +a_4 \sum_{i=0}^{2*2}b_i x_4^i \tag{6.60.1}$$

rom equation (6.57), equation (6.60) becomes equation (6.61.0).

$$\sum_{i=0}^{2*2}b_i h(i) = 0 \tag{6.61.0}$$

A slight variant of equation (6.61.0)

$$b_4 h(4) + \sum_{i=0}^{2*2-1}b_i h(i) = 0 \tag{6.61.1}$$

Here, b4=1, so the equation below holds.

$$-h(4) = \sum_{i=0}^{2*2-1}b_i h(i) \tag{6.62.0}$$

In the Introduction to Modal Analysis, there is a generalized explanation of the above. However, if you are a gory mode identification enthusiast like me, I would like to add a supplemental explanation that is a little different.

For example, suppose that the impulse response is as shown in Figure 2 with i = 0 to 2n-1 and the time history data is for 0.1 second.
Assuming a time resolution of 0.0001, the way to take 0.1 second of the impulse response is
0 to 0.1 second, or
0.0001 to 1.0001 seconds is also fine.

Therefore, a known method is to calculate b such that the error is minimized using a large number of 0.1 second data. Specifically, we solve as in Equations (6.62.1)-(6.62.3).

$$\left( \begin{array}{ccc} h(0) & \ldots & h(2n-1) \\ \vdots & \ddots & \vdots \\ h(2n-1) & \ldots & h(4n-2) \end{array} \right) \left( \begin{array}{c} b_0 \\ \vdots \\ b_{2n-1} \end{array} \right)= \left( \begin{array}{c} h(2n) \\ \vdots \\ h(4n-1) \end{array} \right) \tag{6.62.1}$$

Equation (6.62.2) is a simplified version of Eq(6.62.1).

$$Hb=y \tag{6.62.2}$$

Considering that y contains an error, equation (6.62.3) is the solution of b by the least-squares method.

$$b=(H^tH)^{-1} H^t y \tag{6.62.2}$$

Now you have obtained b.
Once b is obtained, solving the algebraic equation in Eq. (6.57) yields xr in Eq. (6.55).
From xr, we obtain the damped angular resonance frequency ωdr and the modal damping factor σr as in the equation below.

$$σ_r=-\frac{In|x_r|}{Δt} \tag{6.100.1}$$

$$ω_{dr}=\frac{1}{Δt}atan(\frac{imag(x_r)}{real(x_r)}) \tag{6.100.2}$$

Theoretical formulas up to the above may be found in modal analysis handbooks and other sources of modal identification.
However, the above theoretical equations alone cannot identify the mode characteristics. Rather, the Prony method requires the identification of a larger number of resonance frequencies. For example, a waveform with only two resonance frequencies excited is assumed to have 50 resonance frequencies by the Prony method to estimate the mode characteristics.
Therefore, it is necessary to extract the two that seem to be correct from the estimated 50. In some cases, the 50 may not have been estimated correctly in the first place. We need to make these judgments, but the indicators for making these judgments are not described in any commercially available reference book.

I would like to explain the above issues using examples.

## Example of MATLAB

#### Solution from eq(6.52) to eq(6.62.2)

Let us now solve the example problem in MATLAB.
Let us find the modal characteristics from the impulse response waveforms with resonance frequencies of 10Hz and 50Hz as shown in Figure 3. Note that the modal damping ratios are 5%@10Hz and 1%@50Hz.

Figure 3 Impulse response

Now, let’s make the waveform shown in Figure 4, and the MATLAB program will look like the following.

clear all;clc;close all;

j=sqrt(-1);
time=0:0.0001:1;

% % Example of time response vector X
freq1=10; omega1=freq1*2*pi;
freq2=50; omega2=freq2*2*pi;
zeta1=0.05; sgm1=zeta1*omega1;
zeta2=0.01; sgm2=zeta2*omega2;
phi1=0; phi2=0;
X=exp(-zeta1*omega1*time).*sin(omega1*time+phi1)......
+exp(-zeta2*omega2*time).*sin(omega2*time+phi2);

figure
plot(time,X)
xlabel('Time [s]')
ylabel('Ampli [mm]')

Now that we have created the impulse response waveform, let’s program it up to the Prony method equation (6.62.2). By the way, the program is as follows.

% Number of resonance frequencies N to be sought (the trick is to set a larger number for now)
% N-1 to be sought
N=10; n=N/2;

% % eq(6.62.1) H
H=zeros(2*n);
for ii1=1:2*n
H(ii1,:)=X(ii1:(ii1+2*n-1)).';
end

% % Right side of Eq. (6.62.1) (y-vector in Eq. (6.62.2))
y=-X(2*n+1:n*4).';

% % eq(6.62.2)
b=(H.'*H)(H'*y);

You have found b in equation (6.62.2).
From b, you can find the mode characteristic by finding x that satisfies equation (6.57).

#### Estimation of mode properties using “roots” MATLAB function (doesn’t work)

Now, here comes the hard part. How do we solve equation (6.57)?
MATLAB has a function “roots” to find the roots of polynomials.
Let’s try it here (as I mentioned earlier, this method does not work)

r = roots(b.'); %apply roots function to eq(6.57.3)......
% figure
% plot(real(r),imag(r),'.')
% axis equal
% grid on

omega_prony = angle(r)/time(2); %eq(6.100.2)
fn_prony = omega_prony/(2*pi);
sgm_prony = -log(abs(r))/time(2); %eq(6.100.1)
zeta_prony = sgm_prony./omega_prony;

The resonant frequency and mode damping ratio obtained by the above program are as follows

Figure 4 Obtained mode characteristics (resonant frequency and mode attenuation ratio)

Theoretical values are fn=10, 50; zeta=0.05, 0.01.
Since the Prony method requires a larger order to be identified, this example estimates 9 resonant frequencies and mode damping ratios, but I do not see any combination that matches the theoretical values.

If we increase the number of resonant frequencies to be estimated, we may find a combination that matches the theoretical value. (It is very likely that they will.) However, it is difficult to select the most plausible combination from a huge number of combinations of resonant frequencies and mode damping ratios. To begin with, we are estimating without prior information on how many resonance frequencies are included in the impulse response waveform, so we would like to have a criterion for selecting a combination.

This is the difficult part of mode identification. (This is where mode identification maniacs get hooked.)
Most of the theory of mode identification does not work well even if you program the theoretical equation as it is written in a paper or a reference book. In order to create a program, it is necessary to unravel the information hidden behind the theoretical equation.

#### Proposed Method

Again, once b is obtained, it is considered possible to extract the modal characteristics by finding xi that satisfies the equality in equation (6.57).

$$\sum_{i=0}^{2n}b_i x^i =0 \tag{6.57}$$

So what value is xi likely to be?
To begin with, xi was the following, right? (xr and xi are different orders of resonance, r-order or i-order.)

$$x_r=e^{λ_r Δt} \tag{6.55}$$

Also, λr is the following.
$$λ_r=-σ_r + jω_{dr} \tag{6.51}$$

Thus,

$$x_r=e^{(-σ_r + jω_{dr})Δt}=e^{(-ω_{dr}ζ + jω_{dr})Δt}$$

What is the realistic range of modal attenuation ratio ζ?
Empirically, it should be as follows
0<ζ<0.1

The next thing to consider is the range of resonant frequencies we want to find.
Since this is an example problem, we know the answer to the resonant frequency of the impulse response waveform.
However, (unless you have checked the spectrum in advance and have an estimate of the resonance frequency), you would not normally perform mode identification with the resonance frequency known.

When performing mode identification, the key point is to specify the frequency range you want to find and to limit the frequency range to be sought using the Prony method.
For example, in this example, let’s say you want to find resonance frequencies below 100 Hz. (Assume that you are solving without knowing the number of resonance frequencies in the impulse response waveform or the resonance frequencies themselves.)

In other words, the range where resonant frequencies are likely to exist is as follows.

0<fn<100
0<ωn<2*pi*100

Therefore, the range of ζ and ωn determines the range that x_r can also take.
In MATLAB, x (x_r is defined as x for search) is defined as follows.
Here, x is made to correspond to a change in ζ in the row direction and a change in ωn in the column direction.

We then find the left-hand side of Eq. (6.57).

fn_min=0;
fn_max=100;
zeta_min=0.00001; %モード減衰比が0になることはないので、限りなく小さくしておく
zeta_max=0.1;
dt=time(2);

fn_range=fn_min:0.5:fn_max;
wn_range=2*pi*fn_range;
zeta_range=linspace(zeta_min,zeta_max,1000);

x=exp((-zeta_range.'+j)*wn_range*dt);

Eq_6_57=1*x.^(2*n); %b_2n*x.^(2*n)
for ii1=1:2*n
Eq_6_57=Eq_6_57+b(ii1)*x.^(ii1-1); %式(6.57)
end

If we can find x such that Eq_6_57, the left side of Eq. (6.57), becomes 0, i.e., a minimum value, we can extract the modal characteristics that are consistent with the theoretical values.

The minimum value is considered to be obtained as follows.

% Determination and search for poles
surf_Eq_6_57 = abs(Eq_6_57);
surf_pole_logical = islocalmin(surf_Eq_6_57,1) & islocalmin(surf_Eq_6_57,2); % Finding the smallest point on a plane (matrix)

xr = x(surf_pole_logical); %pole

omega_prony = angle(xr)/dt; %eq(6.100.2)
fn_prony=omega_ans/(2*pi);
sgm_prony = -log(abs(xr))/dt; %eq(6.100.1)
zeta_prony = sgm_prony./omega_prony;

The results are as follows. The theoretical value is firmly obtained.

## MATLAB code (full ver.)

Check that the results of the resonance frequency and mode damping ratio estimation are correct when the amplitudes A1 and A2 are changed, etc.

clear all;clc;close all;

j=sqrt(-1);
time=0:0.0001:1;
dt=time(2);

% Number of resonance frequencies N to be sought (the trick is to set a larger number for now)
% N-1 to be sought
N=100; n=N/2;

% % Example of time response vector X
A1=1; freq1=10; omega1=freq1*2*pi;
A2=2; freq2=50; omega2=freq2*2*pi;
zeta1=0.05; sgm1=zeta1*omega1;
zeta2=0.01; sgm2=zeta2*omega2;
phi1=0; phi2=0;
X=A1*exp(-zeta1*omega1*time).*sin(omega1*time+phi1)......
+A2*exp(-zeta2*omega2*time).*sin(omega2*time+phi2);

figure
plot(time,X)
xlabel('Time [s]')
ylabel('Ampli [mm]')

% % eq(6.62.1) H
H=zeros(2*n);
for ii1=1:2*n
H(ii1,:)=X(ii1:(ii1+2*n-1)).';
end

% % Right side of eq.(6.62.1) (equation (6.62.2) y-vector)
y=-X(2*n+1:n*4).';

% % eq(6.62.2)
b=(H.'*H)(H'*y);

fn_min=0;
fn_max=100;
zeta_min=0.00001; % Keep the modal damping ratio as small as possible since it will never be zero.
zeta_max=0.1;

fn_range=fn_min:0.5:fn_max;
wn_range=2*pi*fn_range;
zeta_range=linspace(zeta_min,zeta_max,1000);

x=exp((-zeta_range.'+j)*wn_range*dt);

Eq_6_57=1*x.^(2*n); %b_2n*x.^(2*n)
for ii1=1:2*n
Eq_6_57=Eq_6_57+b(ii1)*x.^(ii1-1); %eq(6.57)
end

% Determination and search for poles
surf_Eq_6_57 = abs(Eq_6_57);
surf_pole_logical = islocalmin(surf_Eq_6_57,1) & islocalmin(surf_Eq_6_57,2); % 平面上（行列上）の極小点を探す

xr = x(surf_pole_logical); %pole

omega_prony = angle(xr)/dt; %eq(6.100.2)
fn_prony=omega_prony/(2*pi)
sgm_prony = -log(abs(xr))/dt; %eq(6.100.1)
zeta_prony = sgm_prony./omega_prony

MATLABパイセンが教える振動・騒音・音響・機械工学


text:
# Circulation problem

The circulation problem and its variants are a generalisation of network flow problems, with the added constraint of a lower bound on edge flows, and with flow conservation also being required for the source and sink (i.e. there are no special nodes). In variants of the problem, there are multiple commodities flowing through the network, and a cost on the flow.

## Definition

Given flow network ${\displaystyle G(V,E)}$ with:

${\displaystyle l(v,w)}$, lower bound on flow from node ${\displaystyle v}$ to node ${\displaystyle w}$,
${\displaystyle u(v,w)}$, upper bound on flow from node ${\displaystyle v}$ to node ${\displaystyle w}$,
${\displaystyle c(v,w)}$, cost of a unit of flow on ${\displaystyle (v,w)}$

and the constraints:

${\displaystyle l(v,w)\leq f(v,w)\leq u(v,w)}$,
${\displaystyle \sum _{w\in V}f(u,w)=0}$ (flow cannot appear or disappear in nodes).

Finding a flow assignment satisfying the constraints gives a solution to the given circulation problem.

In the minimum cost variant of the problem, minimize

${\displaystyle \sum _{(v,w)\in E}c(v,w)\cdot f(v,w).}$

### Multi-commodity circulation

In a multi-commodity circulation problem, you also need to keep track of the flow of the individual commodities:

 ${\displaystyle \,f_{i}(v,w)}$ The flow of commodity ${\displaystyle i}$ from ${\displaystyle v}$ to ${\displaystyle w}$. ${\displaystyle \,f(v,w)=\sum _{i}f_{i}(v,w)}$ The total flow.

There is also a lower bound on each flow of commodity.

 ${\displaystyle \,l_{i}(v,w)\leq f_{i}(v,w)}$

The conservation constraint must be upheld individually for the commodities:

${\displaystyle \ \sum _{w\in V}f_{i}(u,w)=0.}$

## Solution

For the circulation problem, many polynomial algorithms have been developed (e.g., Edmonds and Karp algorithm, 1972; Tarjan 1987-1988). Tardos found the first strongly polynomial algorithm.[1]

For the case of multiple commodities, the problem is NP-complete for integer flows.[2] For fractional flows, it is solvable in polynomial time, as one can formulate the problem as a linear program.

## Related problems

Below are given some problems, and how to solve them with the general circulation setup given above.

• Minimum cost multi-commodity circulation problem - Using all constraints given above.
• Minimum cost circulation problem - Use a single commodity
• Multi-commodity circulation - Solve without optimising cost.
• Simple circulation - Just use one commodity, and no cost.
• Multi-commodity flow - If ${\displaystyle K_{i}(s_{i},t_{i},d_{i})}$ denotes a demand of ${\displaystyle d_{i}}$ for commodity ${\displaystyle i}$ from ${\displaystyle s_{i}}$ to ${\displaystyle t_{i}}$, create an edge ${\displaystyle (t_{i},s_{i})}$ with ${\displaystyle l_{i}(t_{i},s_{i})=c(t_{i},s_{i})=d_{i}}$ for all commodities ${\displaystyle i}$. Let ${\displaystyle l_{i}(u,v)=0}$ for all other edges.
• Minimum cost multi-commodity flow problem - As above, but minimize the cost.
• Minimum cost flow problem - As above, with 1 commodity.
• Maximum flow problem - Set all costs to 0, and add an edge from the sink ${\displaystyle t}$ to the source ${\displaystyle s}$ with ${\displaystyle l(t,s)=0}$, ${\displaystyle u(t,s)=}$∞ and ${\displaystyle c(t,s)=-1}$.
• Minimum cost maximum flow problem - First find the maximum flow amount ${\displaystyle m}$. Then solve with ${\displaystyle l(t,s)=u(t,s)=m}$ and ${\displaystyle c(t,s)=0}$.
• Single-source shortest path - Let ${\displaystyle l(u,v)=0}$ and ${\displaystyle c(u,v)=1}$ for all edges in the graph, and add an edge ${\displaystyle (t,s)}$ with ${\displaystyle l(t,s)=c(t,s)=1}$ and ${\displaystyle a(t,s)=0}$.
• All-pairs shortest path - Let all capacities be unlimited, and find a flow of 1 for ${\displaystyle v(v-1)/2}$ commodities, one for each pair of nodes.

## References

1. ^ Éva Tardos. "A strongly polynomial minimum cost circulation algorithm". Combinatorica. 5: 247–255. doi:10.1007/BF02579369.
2. ^ S. Even and A. Itai and A. Shamir (1976). "On the complexity of time table and multi-commodity flow problems". SIAM Journal on Computing. SIAM. 5 (4): 691–703. doi:10.1137/0205048.


text:
# Homework Help: Sum from 0 to infinity of [3/[(n+1)(5^n)]](x-3)^n HELP

1. Apr 12, 2013

### Lo.Lee.Ta.

Sum from 0 to infinity of [3/[(n+1)(5^n)]](x-3)^n HELP :)

1.

Ʃ $\frac{3}{(n+1)(5^{n}}$*(x-3)n
n=0

2. The first question I had to answer was: What is f(3)?

I found the first 4 terms to be:

3, 3/10(x-3), 3/75(x-3)2, 3/189(x-3)3

So f(3) equals 3, I'm pretty sure.
Because all the other (except the 1st) cancel to equal 0.
3 + infinity zeros = 3

The second question asks me whether or not f(4) converges.

Well, that would be: 3 + (3/10)(1)1 + (3/75)(1)2+(3/189)(1)3 + ...

3 + increasingly small numbers = convergence

Is this the right way to think about it? Is this is correct, is there a better, perhaps faster way?

The third question asks whether or not f(8) converges.

That would be: 3 + (3/10)(5)1 + (3/75)(5)2 + (3/189)(5)3 + ...

= 3 + increasingly small numbers = convergence

...I don't think it's getting bigger very fast... It seems like it would take way too long for this to go to infinity. That's why I'm thinking it would converge...

The fourth question asks whether or not f(-2) converges.

That would be: 3 + (3/10)(5)1 + (3/75)(5)2 + ...

Yeah, this is the same as last time. So I say it converges again.

Now, the fifth question asks what the interval of convergence is for this power series.

To find this interval, I think I need to use the formula: an/an+1

$\frac{3(x-3)^{n}}{(n+1)5^{n}}$*$\frac{(n+2)(5^{n+1})}{3(x-3)^{n+1}}$

= $\frac{5(n+2)}{(n+1)(x-3)}$

Now, the next step is to take the limit, but in this form, I'll get ∞/∞.
I could do L'Hospital's Rule, but I think it might be easier if I rewrote the problem before I take the limit.

Hopefully, I'm not doing any illegal math moves... :/

$\frac{5}{(n+2)^{-1}(n+1)(x-3)}$

=$\frac{5}{n^{0}+n^{-1}+2n^{-1}+2{-1}(x-3)}$

= $\frac{5}{1 + 1/n + 1/2n + 1/2(x-3)}$

lim |$\frac{5}{1.5 + 1/n + 1/2n(x-3)}$|
n→∞

= |5/[(1.5 + 0 + 0)(x-3)]|

I CAN'T FIND THE GREATER THAN SYMBOL, so I'm using "∠"!

= -1 ∠ 10/3(x-3) ∠ 1

= -33/10 ∠ x ∠ 33/10

...So it is convergent between this interval... Which I'm pretty sure is WRONG!

That is too hideous of an answer to be correct. AND- it does not fit with my convergence answers from before!
33/10= 3.3

4 AND 8 lie outside of this interval. Something's wrong here... :/

Thanks :)

2. Apr 12, 2013

### Zondrina

Err lets start at the top.

You said f(3) = 3? Check that again.

3. Apr 13, 2013

### Lo.Lee.Ta.

Oh, yeah. Seems like the first term should really be 0. (0)0 I guess is 0? My calculator says error when I put that in. But should I say that's 0 or undefined or what?

Let me just write everything out.

$\frac{3}{(0+1)(5^{0})}$*(3-3)0 + $\frac{3}{(1+1)(5^{1})}$*(3-3)1 + $\frac{3}{(2+1)(5^{2})}$*(3-3)2+ $\frac{3}{(3+1)(5^{3})}$*(3-3)3

4. Apr 13, 2013

### Infrared

In this case 0^0 is 1, not zero since when n=0, you get your constant term. This should not be affected by your choice of x.
It isn't the best notation maybe but this is the case for all power series that have a constant term.

5. Apr 13, 2013

### Staff: Mentor

This is definitely NOT the right way to think about this. Using this logic, you would conclude that this series converges:
$$\sum_{n = 1}^{\infty}\frac{1}{n} = 1 + 1/2 + 1/3 + 1/4 + ... + 1/n + ...$$
Here you have 1 + "increasingly small numbers", but it's well known that this series (the harmonic series) diverges.

For this part of the problem, you have
$$f(4) = \sum_{n = 0}^{\infty}\frac{3}{(n + 1)5^n}1^n$$
Since 1n = 1 for each finite value of n, the above can be simplified to
$$f(4) = \sum_{n = 0}^{\infty}\frac{3}{(n + 1)5^n}$$
I'm sure you've worked with series of constants before now, so what theorems can you use to determine whether this series converges or diverges?
Most keyboards have the > symbol on the same key as the comma. Press SHIFT + , to get the > symbol.

Also, if you click Go Advanced on the lower right below the PF text entry area, an advanced menu bar opens across the top of the window, and a table of quick symbols appears at the right. This table as a number of symbols, including ≤, ≥ (which aren't usually available on keyboards), ≠, and other symbols.

6. Apr 13, 2013

### Lo.Lee.Ta.

Ʃ $\frac{3}{(n+1)(5^{n})}$*(x-3)n
n=0

Since n's are in the exponents, I would use the ratio/root test.
And this is a geometric series, right...?

Is it that the only way I can figure this out is to find the interval of convergence?

Once I find the interval of convergence, I can just see if f(4), f(8), etc. lie within that interval and converge?

Well, I did that below. I'm not sure if the answer is right... :/

Since I found the interval to be between -3.3 and 3.3, then I would say that f(3) converges, f(4) diverges, f(8) diverges, and f(-2) converges?

Thanks! :)

7. Apr 13, 2013

### Infrared

It is impossible for the convergence set to get (-3.3,3.3) with one or both of the endpoints possible added. There is a nice theorem that for any power series, the convergence set is centered at the center of the power series. (-3.3,3.3) is centered at zero while the power series is centered at 3. I got something else. (Hint: there is a reason why the question is asking about x=-2 and x=8).

Edit: Also, no, it is not geometric.

8. Apr 13, 2013

### Lo.Lee.Ta.

I just followed the an/an+1 formula to arriave at my answer...

Do you see anything wrong with my work that gave me the wrong interval of -3.3 to 3.3?

I don't see what's wrong here... :/

9. Apr 13, 2013

### Infrared

The ratio test considers $|\frac{a_{n+1}}{a_n}|$ as n becomes large (not the other way around) . Where the this is greater than one it diverges, less than one it converges, and inconclusive if it equals one. So when is $\lim_{n\rightarrow \infty} |{\frac{(x-3)(n+1)}{5(n+2)}}|$ less than one? What happens when it equals one?

10. Apr 13, 2013

### Lo.Lee.Ta.

Wow, that was dumb of me. O_O It's "an+1/an"! ugh.

okay, so now I have: $\frac{(x-3)(n+1)}{5(n+2)}$

Then I was thinking that maybe I should multiply the numerator and the denominator by 1/n because then I'll have:

lim $\frac{(x-3)(1 + 1/n)}{5(1 + 2/n)}$
n→∞

Now, there's no question that when I put in ∞ for n, the term will go to zero.

That leaves me with:

|$\frac{(x-3)}{5}$|< 1

-1 < $\frac{x-3}{5}$ < 1

-2 < x < 8

Hey! That's like the question! haha
So, I guess since the interval is only GREATER THAN -2 and LESS THAN 8, then f(-2) and f(8) diverge.

Is this right?

f(3) converges, f(4) converges, f(8) diverges, and f(-2) diverges.

Is it possible to have an interval between non-whole numbers?

If the expression equals 1, it's inconclusive; we have to do another test (integral test).

If the expression is greater than 1, it fails the test and is divergent, right?

Thanks! :)

11. Apr 13, 2013

### Infrared

How did you get that the series diverges for x=-2 and x=8? The test is inconclusive when the limit of the ratio is one, so you have to check these points manually. Yes, it is of course possible for the convergence set to be between two non-integers. What happens if you replace the 5 by a 5.1?

12. Apr 13, 2013

### Lo.Lee.Ta.

For my expression: |$\frac{(x-3)}{5}$| < 1

I'm trying to find for which values of x is my expression convergent (or less than 1).

-1 < $\frac{(x-3)}{5}$ < 1

-5 < x-3 < 5

-2 < x < 8

So, it says that when the x value is between -2 and 8, my expression is convergent.
Outside of that interval, it is divergent.

So, f(-2) is outside the interval, so I say it's divergent, etc.

...I don't really understand what you mean about having to check points manually... :/

I thought that when you have an expression with only 1 variable (not like the power series which has the an and the x), then you'd end up with a number at the end of the ratio test.

Then you see if that number is less than 1. If it is, then the entire expression converges.
If it isn't, the entire series diverges.
If it equals one, you've got to do the integral test.

Hmmm. :/ I thought that was the whole point of finding the interval- to know what x values make our expression converge...

Help. Thanks! :)

13. Apr 13, 2013

### Infrared

No, the ratio test works like this: If the ratio is less than one, it definitely converges,
If the ratio is equal to one, then the test is INCONCLUSIVE, if greater than one then it diverges.

14. Apr 13, 2013

### Lo.Lee.Ta.

Okay, so you say I should test each x value manually.

|$\frac{(x-3)}{5}$| < 1

f(3)= |$\frac{3-3}{5}$ < 1

$\frac{0}{5}$ = 0 < 1

This would converge.

f(4)= |$\frac{(4-3)}{5}$|

= |$\frac{1}{5}$| < 1

This would converge.

f(8)= |$\frac{8-3}{5}$|

= |$\frac{5}{5}$| = 1 is NOT less than 1

This might converge OR diverge.

f(-2)= |$\frac{-2-3}{5}$|

= |-5/5| = 1 is NOT less than 1

This might converge OR diverge.

Oh! THIS is why the points must be manually tested! I did not understand why before!
So now I need to do the integral test?

Last edited: Apr 13, 2013
15. Apr 13, 2013

### Infrared

You have to do another test, but there are other tests easier than the integral test. You will see that one of -2 and 8 will give you something diverges by comparison with harmonic series and the other will converge by alternating series test.

Edit: You don't have to check x=3 because that is safely inside your convergence set. It is just the endpoints that you need to do this for.
Also, you should not use 'f' to denote the ratio as it is already being used for the series itself.

Last edited: Apr 13, 2013
16. Apr 13, 2013

### SammyS

Staff Emeritus
@ Lo.Lee.Ta. ,

For what values of x, is the series an alternating series ?

17. Apr 13, 2013

### Lo.Lee.Ta.

AGH! The integral test seems like too much of a pain here!

Attempt to take integral of 3(x-3)3/[(n+1)(5n)]:

[(n5n + 5n)(3n(x-3)n-1*1) - (3(x-3)n)(n25n-1 + n5n-1)]/[(n+1)(5n)]2

I DO NOT WANT TO HAVE TO FIGURE THIS LONG INTEGRAL OUT! D=

Isn't there some other way that I can figure out if f(-2) and f(8) converge or diverge?!

18. Apr 13, 2013

### Infrared

19. Apr 13, 2013

### Lo.Lee.Ta.

Please check to see if my process is right! Thanks!

The expression will look like this when -2 is substituted for x:

$\frac{3(-2-3)^{n}}{(n+1)5^{n}}$

= $\frac{3(-5)^{n}}{(n+1)5^{n}}$

Because of that (-5)n, we have an alternating series. It will start negative, then +, -, ... etc.
(And- would the -5 be considered the r...?)

The two tests to see if an alternating series converges are:

1. an+1≤an

2. an (stuff without the r) goes to 0 as n approaches infinity.

The first situation is satisfied because a larger denominator results in a smaller fraction.

The second situation is also satisfied because:

an = 3/(n+1)5n

lim = 3/(large denominator) = 0
n→∞

I say, yes, it does converge at f(-2).

20. Apr 13, 2013

### Lo.Lee.Ta.

I am a bit confused as to how to test for f(8).

You say I am supposed to compare to a harmonic series.
How am I supposed to know what would be good to compare it to?

How would I decide if I should compare it to 1/(5n) or 1/(n+1) or 1/n, etc.?

A harmonic series is in the form 1/n, and we also have a 1/n in our expression. So I guess I'll compare it to that?

3(5)n/(n+1)5n ≤ 1/n

But this wouldn't even help us. Our expression has a bigger denominator, and therefore, is smaller than our comparison.
And our comparison diverges.

So what am I supposed to do??? D:

21. Apr 13, 2013

### SammyS

Staff Emeritus
$\displaystyle \frac{3\cdot 5^n}{(n+1)5^n}=\frac{3}{n+1}$

Does $\displaystyle \ 3\sum_{n=0}^{\infty}\frac{1}{n+1}\$ converge?

22. Apr 13, 2013

### Lo.Lee.Ta.

No, I think that would still diverge... And that comparison wouldn't help me either because it is greater than the original expression... =(

23. Apr 13, 2013

### SammyS

Staff Emeritus
$\displaystyle \sum_{n=0}^{\infty}\frac{1}{n+1}\$ is the same as $\displaystyle \sum_{n=1}^{\infty}\frac{1}{n}\ .$

Look at it term by term .

24. Apr 14, 2013

### Infrared

$\frac{3}{x+1} > \frac{1}{x}$ even if you were starting from the same inital x-value. And, even if it didn't, you did start both series by one, you still could use the limit comparison test.

25. Apr 14, 2013

### Lo.Lee.Ta.

Okay, I see that the an is divergent using the limit comparison test.

BUT HOW did you know to make the an equal only the 3/(x+1)???

Thanks! :)


text:
# [Tutor] pylab Failure

Kent Johnson kent37 at tds.net
Mon Oct 13 02:48:22 CEST 2008

On Sun, Oct 12, 2008 at 8:34 PM, Wayne Watson
<sierra_mtnview at sbcglobal.net> wrote:
> What's more likely run python/Tkinter with graphics than IDLE?

See my previous suggestions.

> I'm looking at py2exe right now, but that seems useful for a completed
> program. On that topic, I noticed that my Start->All Progs menu item now,
> possibly it was there before I installed p2exe, a Python2.4 item show a
> Command Line sub-item.

OK, choosing that will open a Python interpreter with a >>> prompt.
What happens if you type
import pylab
at the prompt? Please try that and copy and paste the results to an email.

> I've finally figured out to use the Start->Run to get at the python program.
> I just tried a slight variation on:
>
> C:\Python24\python \path\to\myprogram.py gets nowhere.

What happens when you try it? Please be specific. "gets nowhere"
doesn't tell me much.

> I copied the program int c:\pytho24. I don't seem to be able to copy the
> window, so I see pretty much what I had before, except it adds:
> Fatal Pyton error: Pystring_InterInPlace: strings only please! The rest is
> about the run time error.


text:
# What is “a general covariant formulation of newtonian mechanics”?

I am a little confused: I read that there are general covariant formulations of Newtonian mechanics (e.g. here). I always thought:

1) A theory is covariant with respect to a group of transformations if the form of those equations is conserved.

2) general covariance means not only transformations defined by arbitrary velocities between different systems, but also transformations defined by arbitrary accelerations conserve the form of such equations.

But in that case the principle of general relativity (the form of all physical laws must be conserved under arbitrary coordinate transformations) would not be unique to general relativity. Where is my error in reasoning, or stated differently which term do I misunderstand?

• Nothing stops you from making Newtonian mechanics covariant. We do it in crystallography all the time when we deal with non-orthogonal bases and their duals. Does it buy much for understanding? If it does, I am not aware of it. General coordinate transformations are handled by the Lagrange formalism, if needed, but an arbitrary coordinate transformation is of as little use in Newtonian mechanics as it is in GR. The important ones are problem specific and simplify the solution or highlight its symmetries/properties, which requires more than the ability to formulate a general transformation. – CuriousOne Jun 21 '16 at 22:49
• Indeed, the Lagrange formalism is the result of a general covariant formulation of Newtonian mechanics. – Lewis Miller Jun 21 '16 at 23:54
• Although not quite the same thing, there is a lovely discussion of a geometric formulation of Newtonian mechanics by Élie Cartan in Chapter 12 of Misner Thorne Wheeler "Gravitation". You'll be quite horrified at how awkward it is and how natural the Einstein field equations seem in comparison – WetSavannaAnimal Jun 30 '16 at 4:16

The development of general relativity has led to a lot of misconceptions about the significance of general covariance. It turns out that general covariance is a manifestation of a choice to represent a theory in terms of an underlying differentiable manifold.

Basically, if you define a theory in terms of the geometric structures native to a differentiable manifold (i.e. tangent spaces, tensor fields, connections, Lie derivatives, and all that jazz), the resulting theory will automatically be generally-covariant when expressed in coordinates (guaranteed by the manifold's atlas).

It turns out that most physical theories can be expressed in this language (e.g. symplectic manifolds in the case of Hamiltonian Mechanics) and can therefore be presented in a generally covariant form.

What turns out to be special(?) about the general theory of relativity is that space and time combine to form a (particular type of) Lorentzian manifold and that the metric tensor field on the manifold is correlated with the stuff occupying the manifold.

In other words, general covariance was not the central message of general relativity; it just seemed like it was because it was a novelty at the time, and a poorly understood one at that.

• Thanks a lot for you clear answer. But I have two remaining questions: 1) Is the difference between covariance and general-covariance that for general-covariance the group of transformations conserving the form of the physical laws must include accelerations also? 2) Is the general principle of relativity ("All systems of reference are equivalent with respect to the formulation of the fundamental laws of physics.") still unique to gr, since a general-covariant formulation of Newtonian mechanics would e.g. not give constant speed of light in all frames? Kind regards – DonkeyKong Jun 25 '16 at 12:07
• @DonkeyKong special-covariance is a necessary condition for a law to be invariant with respect to a group of transformations, whereas general-covariance is a necessary condition for a law to have an invariant form with respect to a (much larger) group of transformations. To have the same form does not mean the frames are equivalent. There could, for example, be a centrifugal force term in the general form of a law which happens to vanish in inertial coordinate systems but not in others. There is no "general principle of relativity". Einstein was wrong about that. – Physics Footnotes Jun 26 '16 at 12:45

This is not what I, and I would posit most physicists, understand as a physical treatment of what general covariance is in physics. General covariance is that the equations look the same in any coordinate frame - any meaning that the transformations can be any function. The only limitation is that the functions be differentiable, maybe n or infinite times (diffeomorphisms).

Newtonian mechanics has the Galilean group as its definition of covariance. It means transformations to inertial frames only. That is not general covariance in the way physics either works or is understood.

Possibly you can define mathematical contraptions that allows something more general, but it would be a mathematical technique, not a deep property of the physics. The Lagrange or Hamilton equations (which yes are more than contraptions but still no newer physics than Newtonian mechanics) may look the same if you change the p and q's to another coordinate system, but the equations of motion are different in non-inertial frames. The centrifugal and Coriolis forces are not real forces but appear in rotating coordinate frames. And yes, you do have relativity covariant (or Lorentz covariant in special relativity) but it is not space, it is 4D spacetime and a +/- 2 signature, and not 3D.

I saw the Wikipedia article, and for physicists also Landau and Lifshitz and Goldstein/etc, on Newtonian covariance and this is consistent. Wikipedia simply calls the Galilean group the covariance group. In physics we call it the symmetry group. In that article that the OP referred to it clearly says covariant for special relativity, but they say'Lorentz covariant'. Newtonian mechanics is similarly 'I Galilean covariant'. BTW, the article referred to by the OP is about philosophy of science, not about science.

Did some new physics that makes Newtonian mechanics generally covariant get discovered more than 200'years after Newton?

Or am I not understanding something you are trying to say? And if so, does it make any difference in physics and is it represented in accepted refereed physics journals?

By the way, in general relativity having the general covariance makes a difference. In radial normal coordinates the Schwarzchild metric has a singularity at the horizon. In Penrose or Kruskal coordinates it is seen that it is not, and in fact you can use them to understand the causal structure of black holes. Many other reasons. It is not for naught.

• +1; I'm sure you know this, but it is worth pointing out here because it re-emphasizes the point of your last paragraph: that we can switch between observers freely and and get nonsingular horizon behavior from one observer's standpoint and not from another has a physical meaning: that $\mathrm{d} t$ blows up as $\mathrm{d} \tau$ remains finite means that an object crossing the horizon takes forever as reckoned $\mathrm{d} t$ by a distant observer's clock, whereas its a perfectly straighforward, finite time process for the hapless soul plunging through. – WetSavannaAnimal Jun 30 '16 at 4:10
• I think we probably always need to call the Schwarzschild "singularity" at the horizon a "co-ordinate singularity" in this kind of discussion. Also a good tl;dr for your first paragraph: covariance with respect to an obviously highly restricted class of transformations is not "general" covariance, by definition; unless the class of transformation is very broad (e.g. diffeomorphism), it's downright misleading and a poor use of words to call something "generally covariant". – WetSavannaAnimal Jun 30 '16 at 4:13
• It generally tends to be used to mean that. It's a fine point, but anyway, yes, certainly diffeomorphism. – Bob Bee Jun 30 '16 at 4:16

As it is said in the article referred to in my post

we can take any theory and reformulate it so that it is covariant under any group of transformations we pick; the problem is not physical, it is merely a challenge to our mathematical ingenuity.

As @Lewis Miller pointed out the Lagrangian formulation of Newtonian mechanics is general-covariant, since the equations do not change their form under arbitrary coordinate transformations (also including accelerations).

As Bob Bee pointed out: general-covariance means that the transformations may be any function, whereas in (normal) covariance the group of transformations can be one of small cardinality with many restrictions (e.g. only permitting inertial frames).


text:
papers

Visual Discovery at Pinterest
Over the past three years Pinterest has experimented with several visual search and recommendation services, including Related Pins (2014), Similar Looks (2015), Flashlight (2016) and Lens (2017). This paper presents an overview of our visual discovery engine powering these services, and shares the rationales behind our technical and product decisions such as the use of object detection and interactive user interfaces. We conclude that this visual discovery engine significantly improves engagement in both search and recommendation tasks.
papers  ui  ux  object-recognition  neuralnets  recommender-systems  recommendations  pinterest  discovery
yesterday by tarakc02
How to read and understand a scientific paper: a guide for non-scientists
yeah, #1 - read intro not abstract ---- do this, this becomes really obvious after reading a few when the abstract still makes no sense to you, lol
papers  research  science  education  reference
2 days ago by teffalump
[1706.04601] Provable benefits of representation learning
There is general consensus that learning representations is useful for a variety of reasons, e.g. efficient use of labeled data (semi-supervised learning), transfer learning and understanding hidden structure of data. Popular techniques for representation learning include clustering, manifold learning, kernel-learning, autoencoders, Boltzmann machines, etc.
To study the relative merits of these techniques, it's essential to formalize the definition and goals of representation learning, so that they are all become instances of the same definition. This paper introduces such a formal framework that also formalizes the utility of learning the representation. It is related to previous Bayesian notions, but with some new twists. We show the usefulness of our framework by exhibiting simple and natural settings -- linear mixture models and loglinear models, where the power of representation learning can be formally shown. In these examples, representation learning can be performed provably and efficiently under plausible assumptions (despite being NP-hard), and furthermore: (i) it greatly reduces the need for labeled data (semi-supervised learning) and (ii) it allows solving classification tasks when simpler approaches like nearest neighbors require too much data (iii) it is more powerful than manifold learning methods.
2 days ago by mraginsky
[1707.05199] Online codes for analog signals
We revisit a classical scenario in communication theory: a source is generating a waveform which we sample at regular intervals; we wish to transform the signal in such a way as to minimize distortion in its reconstruction, despite noise. The transformation must be online (also called causal), in order to enable real-time signaling. The noise model we consider is adversarial $\ell_1$-bounded; this is the "atomic norm" convex relaxation of the standard adversary model in discrete-alphabet communications, namely sparsity (low Hamming weight). We require that our encoding not increase the power of the original signal.
In the "block coding" setting such encoding is possible due to the existence of large almost-Euclidean sections in $\ell_1$ spaces (established in the work of Dvoretzky, Milman, Ka\v{s}in, and Figiel, Lindenstrauss and Milman).
Our main result is that an analogous result is achievable even online. Equivalently, we show a "lower triangular" version of $\ell_1$ Dvoretzky theorems. In terms of communication, the result has the following form: If the signal is a stream of reals $x_1,\ldots$, one per unit time, which we encode causally into $\rho$ (a constant) reals per unit time (forming altogether an output stream $\mathcal{E}(x)$), and if the adversarial noise added to this encoded stream up to time $s$ is a vector $\vec{y}$, then at time $s$ the decoder's reconstruction of the input prefix $x_{[s]}$ is accurate in a time-weighted $\ell_2$ norm, to within $s^{-1/2+\delta}$ (any $\delta>0$) times the adversary's noise as measured in a time-weighted $\ell_1$ norm. The time-weighted decoding norm forces increasingly accurate reconstruction of the distant past, while the time-weighted noise norm permits only vanishing effect from noise in the distant past.
Encoding is linear, and decoding is performed by an LP analogous to those used in compressed sensing.
papers  to-read  random-matrices  communication  information-theory  analog-information-theory
2 days ago by mraginsky
[1703.03400] Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks
"We propose an algorithm for meta-learning that is model-agnostic, in the sense that it is compatible with any model trained with gradient descent and applicable to a variety of different learning problems, including classification, regression, and reinforcement learning. The goal of meta-learning is to train a model on a variety of learning tasks, such that it can solve new learning tasks using only a small number of training samples. In our approach, the parameters of the model are explicitly trained such that a small number of gradient steps with a small amount of training data from a new task will produce good generalization performance on that task. In effect, our method trains the model to be easy to fine-tune. We demonstrate that this approach leads to state-of-the-art performance on two few-shot image classification benchmarks, produces good results on few-shot regression, and accelerates fine-tuning for policy gradient reinforcement learning with neural network policies."
papers  meta-learning
2 days ago by arsyed
[1701.04079] Agent-Agnostic Human-in-the-Loop Reinforcement Learning
"Providing Reinforcement Learning agents with expert advice can dramatically improve various aspects of learning. Prior work has developed teaching protocols that enable agents to learn efficiently in complex environments; many of these methods tailor the teacher's guidance to agents with a particular representation or underlying learning scheme, offering effective but specialized teaching procedures. In this work, we explore protocol programs, an agent-agnostic schema for Human-in-the-Loop Reinforcement Learning. Our goal is to incorporate the beneficial properties of a human teacher into Reinforcement Learning without making strong assumptions about the inner workings of the agent. We show how to represent existing approaches such as action pruning, reward shaping, and training in simulation as special cases of our schema and conduct preliminary experiments on simple domains."
papers  reinforcement-learning  human-in-the-loop
2 days ago by arsyed
Stack-up-and-routing-optimization-by-understanding-micro-scale-PCB-effects.pdf
Stack-up and routing optimization by understanding micro-scale PCB effects
pcb  design  FR4  engineering  laminates  dielectric  materials  high-speed  papers
2 days ago by eriwst
[1706.00764] Hyperparameter Optimization: A Spectral Approach
"We give a simple, fast algorithm for hyperparameter optimization inspired by techniques from the analysis of Boolean functions. We focus on the high-dimensional regime where the canonical example is training a neural network with a large number of hyperparameters. The algorithm - an iterative application of compressed sensing techniques for orthogonal polynomials - requires only uniform sampling of the hyperparameters and is thus easily parallelizable. Experiments for training deep nets on Cifar-10 show that compared to state-of-the-art tools (e.g., Hyperband and Spearmint), our algorithm finds significantly improved solutions, in some cases matching what is attainable by hand-tuning. In terms of overall running time (i.e., time required to sample various settings of hyperparameters plus additional computation time), we are at least an order of magnitude faster than Hyperband and even more so compared to Bayesian Optimization. We also outperform Random Search 5X. Additionally, our method comes with provable guarantees and yields the first quasi-polynomial time algorithm for learning decision trees under the uniform distribution with polynomial sample complexity, the first improvement in over two decades."
papers  optimization  hyperparameter
2 days ago by arsyed
[1707.02476] Adversarial Examples, Uncertainty, and Transfer Testing Robustness in Gaussian Process Hybrid Deep Networks
"Deep neural networks (DNNs) have excellent representative power and are state of the art classifiers on many tasks. However, they often do not capture their own uncertainties well making them less robust in the real world as they overconfidently extrapolate and do not notice domain shift. Gaussian processes (GPs) with RBF kernels on the other hand have better calibrated uncertainties and do not overconfidently extrapolate far from data in their training set. However, GPs have poor representational power and do not perform as well as DNNs on complex domains. In this paper we show that GP hybrid deep networks, GPDNNs, (GPs on top of DNNs and trained end-to-end) inherit the nice properties of both GPs and DNNs and are much more robust to adversarial examples. When extrapolating to adversarial examples and testing in domain shift settings, GPDNNs frequently output high entropy class probabilities corresponding to essentially "don't know". GPDNNs are therefore promising as deep architectures that know when they don't know."
papers  neural-net  gaussian-processes
5 days ago by arsyed

Copy this bookmark: