Academic life and beyond

Poisson Kernel (intuitions)

四月 17, 2007

Poisson Kernel holds the solution to Dirichlet problem on unit disk.

Dirichlet problem: given the function value on the boundary, find a harmonic function f agree with the boundary function value.

We can find the function value inside the disk by convolution of the Poisson Kernel and boundary function.

Poisson Kernel can be think of as the solution to the Delta function .

Also related to Harmonic measure, which is the solution to the step functions.

We can find the Harmonic measure by plane geometry, and then take limit to get Poisson Kernel.

The connection to complex analysis is from harmonic function <=> holomorphic function, by harmonic function is the real part of a holomorphic function.

Cauchy’s integral formula says that we can recover the function value from the boundary.

This can be translated to the uniqueness and existence of the solution to Derichlet problem.

Poission Kernel is the real part of Cauchy’s Kernel.

So CAuchy Kernel can also be viewed as 『the holomorphic function of Delta function』 (is it true?)

At least, this is related to the derivation of Inverse Fourier theorem.

張貼於Spring 07 M113 Complexity analysis, Uncategorized | 張貼留言 »

Parversh-Vardy Codes for List-decoding and Expander

四月 13, 2007

Is it important to output y in the analysis of expander construction?

Or, it is helpful, and how is it helpful?

Recall expander’s list-decoding framework: we define a bipartite graph $\Gamma: [N] \times [D] \rightarrow [D] \times [M]$ , and say that it is a (K,A)-expander iff for every T in [D] x [M] of size < AK, |LIST(T,1)| < K.

So, output [D] in RHS makes it much easier to get good expansion. Note that we need lossless: $A = (1-\epsilon)D$ . We need [D] in RHS!

Construction:

$PV: F^n_q \times F_q \rightarrow F_q \times F_q^m, PV(f,y) = (y, f_0(y),f_1(y),\dots,f_{m-1}(y))$ , where $f_i(Y) = f^{h^i}(Y) mod E(Y)$ , E(Y) is a irreducible polynomial of degree n. Furthurmore, we will defintion a non-zeor polynomial $Q(Y, Z_1,\dots,Z_m)$ .

Description:

f(Y) is a degree n polynomial over Y.

$f_i(Y)$ is a degree n polynomial over Y.

$Q(Y, Z_1,\dots,Z_m)$ has degree $d_Y = A - 1 = q-mnh-1$ and $d_{Z_i} = h-1$ .

Want Q to be zero on T, so need $(d_Y+1)\cdot(d_{Z_i}+1)^m = AK > |T|$ .

Want $f \in LIST(T,1) \Rightarrow Q(Y,f_0(Y),\dots,f_{m-1}(Y)) = 0$ , so need $q > d_Y + mnh$ .

Want |LIST(T,1)| < K, so need $Q^*(Z) = Q(Y,Z,Z^h,\dots,Z^{h^{m-1}})$ has small degree in Z, i.e., $h^m - 1 < K$ .

張貼於Spring 07 CS225 Pseudorandomness | 張貼留言 »

Nice intuition about OWP => PRG

四月 10, 2007

Let f(x) be a OWP, we construct PRG as follows.

Construction:

$G(x,r) = <x,r><f(x),r><f^{(2)}(x),r>\dots<f^{(m-1)}(x),r>$

Intuitive analysis (can be formalized)

Consider $f^{(m-1)}(U_n),f^{m-2}(U_n),\dots,f(U_n),U_n$ . For a computational bounded test, next block is unpredicatable, so it has lots of entropy, and this is a computational version of block source. (Note that inside one block it’s possible to have good prediction given previous block ans prefix of this block.) Now, <x,r> is a good extractor, so we can think of the above construction as an extractor extracting one bit from each block. Therefore, it is indistinguishable from uniform distribution by computational bounded tests.

張貼於Spring 07 CS225 Pseudorandomness | 張貼留言 »

M113 07-04-09 Conformal mapping and it’s application

四月 9, 2007

Useful Conformal mappings:

power map $z \mapsto z^\alpha$ (~~In fact, this is not conformal, but the angle is simply multiplied by a constant $\alpha$~~ . No, this IS conformal. Conformal means preserving the infinitesimal angle difference.)
exponential map $z \mapsto e^z$
log map $z \mapsto \log z$
(Question: is this a conformal mapping? Ans: Yes, in fact, it’s a FLT) bridge between exp and trigonometric funcitons $w = \frac{1}{2} ( z + \frac{1}{z})$
fractional linear transformation (FLT) $w = \frac{az+b}{cz+d}$ , where $ad-bc \neq 0$ , and wlog, can assume $ad - bc =1$ (although we may not want to do so).

General situation (theory):

Riemann mapping theorem : existence and uniqueness(Schwarz Lemma) results.

Special cases:

Polygon: Schwarz-Christroffel transformation
Rectangle: elliptic functions (can get closed form)
Triangle: Beta functions

————————————————————————

Main idea:

It seems that conformal property is not used often (except for FLTs). The really important property seems to be holomorphic with nonzero derivatives, which implies locally we have holomorphic inverse, which enable us to solve harmonic function with boundary condition with a better boundary.
In many situations, we are interested in conformal mappings. For example, we want to transform the domain to a better form, while preserving the angle. More generally, we want to scale the angle.
Solving harmonic function given boundary condition: using biholomorphic function to reduct the domain to a better domain that we have precise solution, and then pull the solution back by the inverse of the function.

————————————————————————

Key properties of FLT:

holomorphic
maps {circles, lines} to {circles, lines}
conformal

(Point?) A circle is compact, want to map a circle to a line. Construct a FLT sending one point on the circle to $\infty$

How do you choose the coefficient a,b,c,d? Note that the degree of freedom is 3, so we expect that given {z1,z2,z3} -> {w1,w2,w3}, we should be able to construct a FLT for it. That is, FLTs act on $latex {\Bbb C}$ triple-transtive. This can be done by solving equations $w_j = \frac{az_j + b}{cz_j +d}$ for j = 1,2,3, which are four linear equations (together with ad-bc != 0)

A better way to do it is using Cross Ratio (What is this?) Cross ratio are invariant under FLTs. (I missed this point!)

————————————————————————

Another example of application of cross ratio(See the picture in notes. Just summarize points here):

Boundary condition are constance on two circles.
When two circle are co-axis, there are two possible solutions : $\latex \log |w|$ and constant funciton $1$. By linear combination, we can satisfy all possible conditions.
We want to reduce the general case to co-axis case, by sending {z1,z2,z3,z4} -> {w1,w2,w3,w4} by FLTs
Why this works: (i)z1,z2 intersect with a line L with angle 90 (ii) FTL sends {circle,line} to {circle,line} (iii) FLT is conformal, and sends L to anothe line L’. Therefore, w1,w2 intersect L’ with angle 90, and so the circle of z1,z2 must transform to a circle.
(Missing point) We need to map 4 points to 4 points. But it still works, since one thing doesn’t matter… What’s it?

————————————————————————

Example: (application to eleltricstatics)

The trick here is to use power map to change the angle

————————————————————————

Another example of applying FLTs:

maps p -> 0 and q -> infinity, we transform a sector of circle and line to a sector of two lines

————————————————————————

Understanding the geometry of map $w=\frac{1}{2} (z+\frac{1}{z})$ :

maps circles to ellipses
Let $z = re^{i\theta}, 0 \leq \theta \leq 2\pi$ ,
$w = \frac{1}{2}(r+\frac{1}{r})\cos \theta + i \frac{1}{2}(r-\frac{1}{r}) \sin \theta$ is a ellipse for fixed r
w maps { |z| > 1} -> C – [-1,1] bijectively, and preserves the orientation
w maps { |z| < 1} -> C – [-1,1] bijectively, and reverses the orientation

————————————————————————

Possion Kernel:

There are many ways to get possion kernel
We have seen one in Pset that using power series. The reason is that harmonic function is real part of holomorphic function, which has power series expansion, so the real part of the power series expansion gives the power series for Possions Kernel.
Another way is to solve the situation that boundary condition is a step function. Since every function can be approximated by linear combination of step functions and taking limit.
This is also the harmonic measure.
(Aside) The meaning of $arg(\frac{z-b}{z-a}) is the angle between zb and za.</li> </ol> ------------------------------------------------------------------------ Question: <ul> <li>How to check if a function is a conformal mapping or not? I.e., it's characterization?</li> </ul> <blockquote>Answer: Recall last time: a function is conformal and orientation preserving <strong>iff </strong>it's holomorphic with non-zero derivative. Wait, this means <strong>locally bi-homolormic</strong>!</blockquote> <ul> <li>I am confused. What does conformal mapping mean? Is$ latex z \mapsto z^2$ a conformal mapping?