text:
## ECE1236H Microwave and Millimeter-Wave Techniques. Lecture 7: Multisection quarter-wavelength transformers. Taught by Prof. G.V. Eleftheriades

### Disclaimer

Peeter’s lecture notes from class. These may be incoherent and rough.

These are notes for the UofT course ECE1236H, Microwave and Millimeter-Wave Techniques, taught by Prof. G.V. Eleftheriades, covering ch 5. [3] content.

## Terminology review

\label{eqn:uwavesDeck7MultisectionTransformersCore:20}
Z_{\textrm{in}} = R + j X

\label{eqn:uwavesDeck7MultisectionTransformersCore:40}
Y_{\textrm{in}} = G + j B

• $$Z_{\textrm{in}}$$ : impedance
• $$R$$ : resistance
• $$X$$ : reactance
• $$Y_{\textrm{in}}$$ : admittance
• $$G$$ : conductance
• $$B$$ : susceptance

Apparently this notation goes all the way back to Heavyside!

## Multisection transformers

Using a transformation of the form fig. 1 it is possible to optimize for maximum power delivery, using for example a matching transformation $$Z_{\textrm{in}} = Z_1^2/R_{\textrm{L}} = Z_0$$, or $$Z_1 = \sqrt{R_{\textrm{L}} Z_0}$$. Unfortunately, such a transformation does not allow any control over the bandwidth. This results in a pinched frequency response for which the standard solution is to add more steps as sketched in fig. 2.

../../figures/ece1236/Feb10Fig2: fig. 2. Pinched frequency response.
../../figures/ece1236/deck7Fig1: fig. 3. Single and multiple stage impedance matching.

This can be implemented in electronics, or potentially geometrically as in this sketch of a microwave stripline transformer implementation fig. 3.

../../figures/ece1236/deck7Fig3: fig. 3. Stripline implementation of staged impedance matching.

To find a multistep transformation algebraically can be hard, but it is easy to do on a Smith chart. The rule of thumb is that we want to stay near the center of the chart with each transformation.

There is however, a closed form method of calculating a specific sort of multisection transformation that is algebraically tractable. That method uses a chain of $$\lambda/4$$ transformers to increase the bandwidth as sketched in fig. 4.

../../figures/ece1236/deck7Fig4: fig. 4. Multiple $$\lambda/4$$ transformers.

The total reflection coefficient can be approximated to first order by summing the reflections at each stage (without considering there may be other internal reflections of transmitted field components). Algebraically that is

\label{eqn:uwavesDeck7MultisectionTransformersCore:60}
\Gamma(\Theta) \approx \Gamma_0
+ \Gamma_1 e^{-2 j \Theta} +
+ \Gamma_2 e^{-4 j \Theta} + \cdots
+ \Gamma_N e^{-2 N j \Theta},

where

\label{eqn:uwavesDeck7MultisectionTransformersCore:80}
\Gamma_n = \frac{Z_{n+1} – Z_n}{Z_{n+1} + Z_n}

Why? Consider reflections at the Z_1, Z_2 interface as sketched in fig. 5.

../../figures/ece1236/deck7Fig5: fig. 5. Single stage of multiple $$\lambda/4$$ transformers.

Assuming small reflections, where $$\Abs{\Gamma} \ll 1$$ then $$T = 1 + \Gamma \approx 1$$. Here

\label{eqn:uwavesDeck7MultisectionTransformersCore:100}
\begin{aligned}
\Theta
&= \beta l \\
&= \frac{2 \pi}{\lambda} \frac{\lambda}{4} \\
&= \frac{\pi}{2}.
\end{aligned}

at the design frequency $$\omega_0$$. We assume that $$Z_n$$ are either monotonically increasing if $$R_{\textrm{L}} > Z_0$$, or decreasing if $$R_{\textrm{L}} < Z_0$$.

### Binomial multisection transformers

Let

\label{eqn:uwavesDeck7MultisectionTransformersCore:120}
\Gamma(\Theta) = A \lr{ 1 + e^{-2 j \Theta} }^N

This type of a response is maximally flat, and is plotted in fig. 1.
../../figures/ece1236/multitransformerFig1: fig. 1. Binomial transformer.

The absolute value of the reflection coefficient is

\label{eqn:uwavesDeck7MultisectionTransformersCore:160}
\begin{aligned}
\Abs{\Gamma(\Theta)}
&=
\Abs{A} \lr{ e^{j \Theta} + e^{- j \Theta} }^N \\
&=
2^N \Abs{A} \cos^N\Theta.
\end{aligned}

When $$\Theta = \pi/2$$ this is clearly zero. It’s derivatives are

\label{eqn:uwavesDeck7MultisectionTransformersCore:180}
\begin{aligned}
\frac{d \Abs{\Gamma}}{d\Theta} &= -N \cos^{N-1} \Theta \sin\Theta \\
\frac{d^2 \Abs{\Gamma}}{d\Theta^2} &= -N \cos^{N-1} \Theta \cos\Theta N(N-1) \cos^{N-2} \Theta \sin\Theta \\
\frac{d^3 \Abs{\Gamma}}{d\Theta^3} &= \cdots
\end{aligned}

There is a $$\cos^{N-k}$$ term for all derivatives $$d^k/d\Theta^k$$ where $$k \le N-1$$, so for an N-section transformer

\label{eqn:uwavesDeck7MultisectionTransformersCore:140}
\frac{d^n}{d\Theta^n} \Abs{\Gamma(\Theta)}_{\omega_0} = 0,

for $$n = 1, 2, \cdots, N-1$$. The constant $$A$$ is determined by the limit $$\Theta \rightarrow 0$$, so

\label{eqn:uwavesDeck7MultisectionTransformersCore:200}
\Gamma(0) = 2^N A = \frac{Z_{\textrm{L}} – Z_0}{Z_{\textrm{L}} + Z_0},

because the various $$\Theta$$ sections become DC wires when the segment length goes to zero. This gives

\label{eqn:uwavesDeck7MultisectionTransformersCore:220}
\boxed{
A = 2^{-N} \frac{Z_{\textrm{L}} – Z_0}{Z_{\textrm{L}} + Z_0}.
}

The reflection coefficient can now be expanded using the binomial theorem

\label{eqn:uwavesDeck7MultisectionTransformersCore:240}
\begin{aligned}
\Gamma(\Theta)
&= A \lr{ 1 + e^{ 2 j \Theta } }^N \\
&= \sum_{k = 0}^N \binom{N}{k} e^{ -2 j k \Theta}
\end{aligned}

Recall that

\label{eqn:uwavesDeck7MultisectionTransformersCore:260}
\binom{N}{k} = \frac{N!}{k! (N-k)!},

providing a symmetric set of values

\label{eqn:uwavesDeck7MultisectionTransformersCore:280}
\begin{aligned}
\binom{N}{1} &= \binom{N}{N} = 1 \\
\binom{N}{1} &= \binom{N}{N-1} = N \\
\binom{N}{k} &= \binom{N}{N-k}.
\end{aligned}

Equating \ref{eqn:uwavesDeck7MultisectionTransformersCore:240} with \ref{eqn:uwavesDeck7MultisectionTransformersCore:60} we have

\label{eqn:uwavesDeck7MultisectionTransformersCore:300}
\boxed{
\Gamma_k = A \binom{N}{k}.
}

### Approximation for $$Z_k$$

From [1] (4.6.4), a log series expansion valid for all $$z$$ is

\label{eqn:uwavesDeck7MultisectionTransformersCore:320}
\ln z = \sum_{k = 0}^\infty \inv{2 k + 1} \lr{ \frac{ z – 1 }{z + 1} }^{2k + 1},

so for $$x$$ near unity a first order approximation of a logarithm is

\label{eqn:uwavesDeck7MultisectionTransformersCore:340}
\ln x \approx 2 \frac{x -1}{x+1}.

Assuming that $$Z_{k+1}/Z_k$$ is near unity we have

\label{eqn:uwavesDeck7MultisectionTransformersCore:360}
\begin{aligned}
\inv{2} \ln \frac{Z_{k+1}}{Z_k}
&\approx
\frac{ \frac{Z_{k+1}}{Z_k} – 1 }{\frac{Z_{k+1}}{Z_k} + 1} \\
&=
\frac{ Z_{k+1} – Z_k }{Z_{k+1} + Z_k} \\
&=
\Gamma_k.
\end{aligned}

Using this approximation, we get

\label{eqn:uwavesDeck7MultisectionTransformersCore:380}
\begin{aligned}
\ln \frac{Z_{k+1}}{Z_k}
&\approx
2 \Gamma_k \\
&= 2 A \binom{N}{k} \\
&= 2 \lr{2^{-N}} \binom{N}{k} \frac{Z_{\textrm{L}} – Z_0}{Z_{\textrm{L}} + Z_0} \\
&\approx
2^{-N} \binom{N}{k} \ln \frac{Z_{\textrm{L}}}{Z_0},
\end{aligned}

I asked what business do we have in assuming that $$Z_{\textrm{L}}/Z_0$$ is near unity? The answer was that it isn’t but surprisingly it works out well enough despite that. As an example, consider $$Z_0 = 100 \Omega$$ and $$R_{\textrm{L}} = 50 \Omega$$. The exact expression

\label{eqn:uwavesDeck7MultisectionTransformersCore:880}
\begin{aligned}
\frac{Z_{\textrm{L}} – Z_0}{Z_{\textrm{L}} + Z_0}
&= \frac{100-50}{100+50} \\
&= -0.333,
\end{aligned}

whereas
\label{eqn:uwavesDeck7MultisectionTransformersCore:900}
\inv{2} \ln \frac{Z_{\textrm{L}}}{Z_0} = -0.3466,

which is pretty close after all.

Regardless of whether or not that last approximation is used, one can proceed iteratively to $$Z_{k+1}$$ starting with $$k = 0$$.

### Bandwidth

To evaluate the bandwidth, let $$\Gamma_{\mathrm{m}}$$ be the maximum tolerable reflection coefficient over the passband, as sketched in fig. 6.

../../figures/ece1236/deck7Fig6: fig. 6. Max tolerable reflection.

That is

\label{eqn:uwavesDeck7MultisectionTransformersCore:400}
\begin{aligned}
\Gamma_m
&= 2^N \Abs{A} \Abs{\cos \Theta_m }^N \\
&= 2^N \Abs{A} \cos^N \Theta_m,
\end{aligned}

for $$\Theta_m < \pi/2$$. Then $$\label{eqn:uwavesDeck7MultisectionTransformersCore:420} \Theta_m = \arccos\lr{ \inv{2} \lr{ \frac{\Gamma_{\mathrm{m}}}{\Abs{A}}}^{1/N} }$$ The relative width of the interval is \label{eqn:uwavesDeck7MultisectionTransformersCore:440} \begin{aligned} \frac{\Delta f_{\mathrm{max}}}{f_0} &= \frac{\Delta \Theta_{\mathrm{max}}}{\Theta_0} \\ &= \frac{2 (\Theta_0 - \Theta_{\mathrm{max}}}{\Theta_0} \\ &= 2 - \frac{2 \Theta_{\mathrm{max}}}{\Theta_0} \\ &= 2 - \frac{4 \Theta_{\mathrm{max}}}{\pi} \\ &= 2 - \frac{4 }{\pi} \arccos\lr{ \inv{2} \lr{ \frac{\Gamma_{\mathrm{max}}}{\Abs{A}}}^{1/N} }. \end{aligned}

### Example

Design a 3-section binomial transformer to match $$R_{\textrm{L}} = 50 \Omega$$ to a line $$Z_0 = 100 \Omega$$. Calculate the BW based on a maximum $$\Gamma_{\textrm{m}} = 0.05$$.

### Solution

The scaling factor
\label{eqn:uwavesDeck7MultisectionTransformersCore:460}
\begin{aligned}
A
&= 2^{-N} \frac{Z_{\textrm{L}} – L_0}{Z_{\textrm{L}} + Z_0} \\
&\approx
\inv{2^{N+1}} \ln \frac{Z_{\textrm{L}}}{Z_0} \\
&= -0.0433
\end{aligned}

Now use

\label{eqn:uwavesDeck7MultisectionTransformersCore:940}
\ln \frac{Z_{n+1}}{Z_n}
\approx 2^{-N} \binom{N}{n} \ln \frac{R_{\textrm{L}}}{Z_0},

starting from

• $$n = 0$$.

\label{eqn:uwavesDeck7MultisectionTransformersCore:480}
\ln \frac{Z_{1}}{Z_0} \approx 2^{-3} \binom{3}{0} \ln \frac{R_{\textrm{L}}}{Z_0},

or
\label{eqn:uwavesDeck7MultisectionTransformersCore:500}
\begin{aligned}
\ln Z_{1}
&= \ln Z_0 + 2^{-3} \binom{3}{0} \ln \frac{R_{\textrm{L}}}{Z_0} \\
&= \ln 100 + 2^{-3} (1) \ln 0.5 \\
&= 4.518,
\end{aligned}

so
\label{eqn:uwavesDeck7MultisectionTransformersCore:520}
Z_1 = 91.7 \Omega

• $$n = 1$$

\label{eqn:uwavesDeck7MultisectionTransformersCore:540}
\ln Z_{2}
= \ln Z_1 + 2^{-3} \binom{3}{1} \ln \frac{50}{100} = 4.26

so
\label{eqn:uwavesDeck7MultisectionTransformersCore:560}
Z_2 = 70.7 \Omega

• $$n = 2$$

\label{eqn:uwavesDeck7MultisectionTransformersCore:580}
\ln Z_{3} = \ln Z_2 + 2^{-3} \binom{3}{2} \ln \frac{50}{100} = 4.0,

so

\label{eqn:uwavesDeck7MultisectionTransformersCore:600}
Z_3 = 54.5 \Omega.

With the fractional BW for $$\Gamma_m = 0.05$$, where $$10 \log_{10} \Abs{\Gamma_m}^2 = -26$$ dB}.

\label{eqn:uwavesDeck7MultisectionTransformersCore:920}
\begin{aligned}
\frac{\Delta f}{f_0}
&\approx
2 – \frac{4}{\pi} \arccos\lr{ \inv{2} \lr{ \frac{\Gamma_m}{\Abs{A}} }^{1/N} } \\
&=
2 – \frac{4}{\pi} \arccos\lr{ \inv{2} \lr{ \frac{0.05}{0.0433} }^{1/3} } \\
&= 0.7
\end{aligned}

At $$2$$ GHz, $$BW = 0.7$$ (70%), or $$1.4$$ GHz, which is the range $$[2.3,2.7]$$ GHz, whereas a single $$\lambda/4$$ transformer $$Z_T = \sqrt{ (100)(50) } = 70.7 \Omega$$ yields a BW of just $$0.36$$ GHz (18%).

# References

[1] DLMF. NIST Digital Library of Mathematical Functions. https://dlmf.nist.gov/, Release 1.0.10 of 2015-08-07. URL https://dlmf.nist.gov/. Online companion to Olver:2010:NHMF.

[2] F. W. J. Olver, D. W. Lozier, R. F. Boisvert, and C. W. Clark, editors. NIST Handbook of Mathematical Functions. Cambridge University Press, New York, NY, 2010. Print companion to NIST:DLMF.

[3] David M Pozar. Microwave engineering. John Wiley & Sons, 2009.

## Updated notes for ece1229 antenna theory

I’ve now posted a first update of my notes for the antenna theory course that I am taking this term at UofT.

Unlike most of the other classes I have taken, I am not attempting to take comprehensive notes for this class. The class is taught on slides which go by faster than I can easily take notes for (and some of which match the textbook closely). In class I have annotated my copy of textbook with little details instead. This set of notes contains musings of details that were unclear, or in some cases, details that were provided in class, but are not in the text (and too long to pencil into my book), as well as some notes Geometric Algebra formalism for Maxwell’s equations with magnetic sources (something I’ve encountered for the first time in any real detail in this class).

The notes compilation linked above includes all of the following separate notes, some of which have been posted separately on this blog:

## Notes for ece1229 antenna theory

I’ve now posted a first set of notes for the antenna theory course that I am taking this term at UofT.

Unlike most of the other classes I have taken, I am not attempting to take comprehensive notes for this class. The class is taught on slides that match the textbook so closely, there is little value to me taking notes that just replicate the text. Instead, I am annotating my copy of textbook with little details instead. My usual notes collection for the class will contain musings of details that were unclear, or in some cases, details that were provided in class, but are not in the text (and too long to pencil into my book.)

• Reading notes for chapter 2 (Fundamental Parameters of Antennas) and chapter 3 (Radiation Integrals and Auxiliary Potential Functions) of the class text.
• Geometric Algebra musings.  How to do formulate Maxwell’s equations when magnetic sources are also included (those modeling magnetic dipoles).
• Some problems for chapter 2 content.

## Fundamental parameters of antennas

This is my first set of notes for the UofT course ECE1229, Advanced Antenna Theory, taught by Prof. Eleftheriades, covering ch. 2 [1] content.

Unlike most of the other classes I have taken, I am not attempting to take comprehensive notes for this class. The class is taught on slides that match the textbook so closely, there is little value to me taking notes that just replicate the text. Instead, I am annotating my copy of textbook with little details instead. My usual notes collection for the class will contain musings of details that were unclear, or in some cases, details that were provided in class, but are not in the text (and too long to pencil into my book.)

## Poynting vector

The Poynting vector was written in an unfamiliar form

\label{eqn:chapter2Notes:560}
\boldsymbol{\mathcal{W}} = \boldsymbol{\mathcal{E}} \cross \boldsymbol{\mathcal{H}}.

I can roll with the use of a different symbol (i.e. not $$\BS$$) for the Poynting vector, but I’m used to seeing a $$\frac{c}{4\pi}$$ factor ([6] and [5]). I remembered something like that in SI units too, so was slightly confused not to see it here.

Per [3] that something is a $$\mu_0$$, as in

\label{eqn:chapter2Notes:580}
\boldsymbol{\mathcal{W}} = \inv{\mu_0} \boldsymbol{\mathcal{E}} \cross \boldsymbol{\mathcal{B}}.

Note that the use of $$\boldsymbol{\mathcal{H}}$$ instead of $$\boldsymbol{\mathcal{B}}$$ is what wipes out the requirement for the $$\frac{1}{\mu_0}$$ term since $$\boldsymbol{\mathcal{H}} = \boldsymbol{\mathcal{B}}/\mu_0$$, assuming linear media, and no magnetization.

It was mentioned that

U(\theta, \phi)
=
\frac{r^2}{2 \eta_0} \Abs{ \BE( r, \theta, \phi) }^2
=
\frac{1}{2 \eta_0} \lr{ \Abs{ E_\theta(\theta, \phi) }^2 + \Abs{ E_\phi(\theta, \phi) }^2},

where the intrinsic impedance of free space is

\eta_0 = \sqrt{\frac{\mu_0}{\epsilon_0}} = 377 \Omega.

(this is also eq. 2-19 in the text.)

To get an understanding where this comes from, consider the far field radial solutions to the electric and magnetic dipole problems, which have the respective forms (from [3]) of

\label{eqn:chapter2Notes:740}
\begin{aligned}
\boldsymbol{\mathcal{E}} &= -\frac{\mu_0 p_0 \omega^2 }{4 \pi } \frac{\sin\theta}{r} \cos\lr{w t – k r} \thetacap \\
\boldsymbol{\mathcal{B}} &= -\frac{\mu_0 p_0 \omega^2 }{4 \pi c} \frac{\sin\theta}{r} \cos\lr{w t – k r} \phicap \\
\end{aligned}

\label{eqn:chapter2Notes:760}
\begin{aligned}
\boldsymbol{\mathcal{E}} &= \frac{\mu_0 m_0 \omega^2 }{4 \pi c} \frac{\sin\theta}{r} \cos\lr{w t – k r} \phicap \\
\boldsymbol{\mathcal{B}} &= -\frac{\mu_0 m_0 \omega^2 }{4 \pi c^2} \frac{\sin\theta}{r} \cos\lr{w t – k r} \thetacap \\
\end{aligned}

In neither case is there a component in the direction of propagation, and in both cases (using $$\mu_0 \epsilon_0 = 1/c^2$$)

\label{eqn:chapter2Notes:780}
\Abs{\boldsymbol{\mathcal{H}}}
= \frac{\Abs{\boldsymbol{\mathcal{E}}}}{\mu_0 c}
= \Abs{\boldsymbol{\mathcal{E}}} \sqrt{\frac{\epsilon_0}{\mu_0}}
= \inv{\eta_0}\Abs{\boldsymbol{\mathcal{E}}} .

A superposition of the phasors for such dipole fields, in the far field, will have the form

\label{eqn:chapter2Notes:800}
\begin{aligned}
\BE &= \inv{r} \lr{ E_\theta(\theta, \phi) \thetacap + E_\phi(\theta, \phi) \phicap } \\
\BB &= \inv{r c} \lr{ E_\theta(\theta, \phi) \thetacap – E_\phi(\theta, \phi) \phicap },
\end{aligned}

with a corresponding time averaged Poynting vector

\label{eqn:chapter2Notes:820}
\begin{aligned}
\BW_{\textrm{av}}
&= \inv{2 \mu_0} \BE \cross \BB^\conj \\
&=
\inv{2 \mu_0 c r^2}
\lr{ E_\theta \thetacap + E_\phi \phicap } \cross
\lr{ E_\theta^\conj \thetacap – E_\phi^\conj \phicap } \\
&=
\frac{\thetacap \cross \phicap}{2 \mu_0 c r^2}
\lr{ \Abs{E_\theta}^2 + \Abs{E_\phi}^2 } \\
&=
\frac{\rcap}{2 \eta_0 r^2}
\lr{ \Abs{E_\theta}^2 + \Abs{E_\phi}^2 },
\end{aligned}

verifying \ref{eqn:advancedantennaL1:20} for a superposition of electric and magnetic dipole fields. This can likely be shown for more general fields too.

## Field plots

We can plot the fields, or intensity (or log plots in dB of these).
It is pointed out in [3] that when there is $$r$$ dependence these plots are done by considering the values of at fixed $$r$$.

The field plots are conceptually the simplest, since that vector parameterizes
a surface. Any such radial field with magnitude $$f(r, \theta, \phi)$$ can
be plotted in Mathematica in the $$\phi = 0$$ plane at $$r = r_0$$, or in
3D (respectively, but also at $$r = r_0$$) with code like that of the
following listing

Intensity plots can use the same code, with the only difference being the interpretation. The surface doesn’t represent the value of a vector valued radial function, but is the magnitude of a scalar valued function evaluated at $$f( r_0, \theta, \phi)$$.

The surfaces for $$U = \sin\theta, \sin^2\theta$$ in the plane are parametrically plotted in fig. 2, and for cosines in fig. 1 to compare with textbook figures.

Visualizations of $$U = \sin^2 \theta$$ and $$U = \cos^2 \theta$$ can be found in fig. 3 and fig. 4 respectively. Even for such simple functions these look pretty cool.

fig 3. Square sinusoidal radiation intensity

fig 4. Square cosinusoidal radiation intensity

## dB vs dBi

Note that dBi is used to indicate that the gain is with respect to an “isotropic” radiator.
This is detailed more in [2].

## Trig integrals

Tables 1.1 and 1.2 produced with tableOfTrigIntegrals.nb have some of the sine and cosine integrals that are pervasive in this chapter.

## Polarization vectors

The text introduces polarization vectors $$\rhocap$$ , but doesn’t spell out their form. Consider a plane wave field of the form

\label{eqn:chapter2Notes:840}
\BE
=
E_x e^{j \phi_x} e^{j \lr{ \omega t – k z }} \xcap
+
E_y e^{j \phi_y} e^{j \lr{ \omega t – k z }} \ycap.

The $$x, y$$ plane directionality of this phasor can be written

\label{eqn:chapter2Notes:860}
\Brho =
E_x e^{j \phi_x} \xcap
+
E_y e^{j \phi_y} \ycap,

so that

\label{eqn:chapter2Notes:880}
\BE = \Brho e^{j \lr{ \omega t – k z }}.

Separating this direction and magnitude into factors

\label{eqn:chapter2Notes:900}
\Brho = \Abs{\BE} \rhocap,

allows the phasor to be expressed as

\label{eqn:chapter2Notes:920}
\BE = \rhocap \Abs{\BE} e^{j \lr{ \omega t – k z }}.

As an example, suppose that $$E_x = E_y$$, and set $$\phi_x = 0$$. Then

\label{eqn:chapter2Notes:940}
\rhocap = \xcap + \ycap e^{j \phi_y}.

## Phasor power

In section 2.13 the phasor power is written as

\label{eqn:chapter2Notes:620}
I^2 R/2,

where $$I, R$$ are the magnitudes of phasors in the circuit.

I vaguely recall this relation, but had to refer back to [4] for the details.
This relation expresses average power over a period associated with the frequency of the phasor

\label{eqn:chapter2Notes:640}
\begin{aligned}
P
&= \inv{T} \int_{t_0}^{t_0 + T} p(t) dt \\
&= \inv{T} \int_{t_0}^{t_0 + T} \Abs{\BV} \cos\lr{ \omega t + \phi_V }
\Abs{\BI} \cos\lr{ \omega t + \phi_I} dt \\
&= \inv{T} \int_{t_0}^{t_0 + T} \Abs{\BV} \Abs{\BI}
\lr{
\cos\lr{ \phi_V – \phi_I } + \cos\lr{ 2 \omega t + \phi_V + \phi_I}
}
dt \\
&= \inv{2} \Abs{\BV} \Abs{\BI} \cos\lr{ \phi_V – \phi_I }.
\end{aligned}

Introducing the impedance for this circuit element

\label{eqn:chapter2Notes:660}
\BZ = \frac{ \Abs{\BV} e^{j\phi_V} }{ \Abs{\BI} e^{j\phi_I} } = \frac{\Abs{\BV}}{\Abs{\BI}} e^{j\lr{\phi_V – \phi_I}},

this average power can be written in phasor form

\label{eqn:chapter2Notes:680}
\BP = \inv{2} \Abs{\BI}^2 \BZ,

with
\label{eqn:chapter2Notes:700}
P = \textrm{Re} \BP.

Observe that we have to be careful to use the absolute value of the current phasor $$\BI$$, since $$\BI^2$$ differs in phase from $$\Abs{\BI}^2$$. This explains the conjugation in the [4] definition of complex power, which had the form

\label{eqn:chapter2Notes:720}
\BS = \BV_{\textrm{rms}} \BI^\conj_{\textrm{rms}}.

### Flat plate.

\label{eqn:chapter2Notes:960}
\sigma_{\textrm{max}} = \frac{4 \pi \lr{L W}^2}{\lambda^2}

fig. 6. Square geometry for RCS example.

### Sphere.

In the optical limit the radar cross section for a sphere

fig. 7. Sphere geometry for RCS example.

\label{eqn:chapter2Notes:980}
\sigma_{\textrm{max}} = \pi r^2

Note that this is smaller than the physical area $$4 \pi r^2$$.

### Cylinder.

fig. 8. Cylinder geometry for RCS example.

\label{eqn:chapter2Notes:1000}
\sigma_{\textrm{max}} = \frac{ 2 \pi r h^2}{\lambda}

### Tridedral corner reflector

fig. 9. Trihedral corner reflector geometry for RCS example.

\label{eqn:chapter2Notes:1020}
\sigma_{\textrm{max}} = \frac{ 4 \pi L^4}{3 \lambda^2}

## Scattering from a sphere vs frequency

Frequency dependence of spherical scattering is sketched in fig. 10.

• Low frequency (or small particles): Rayleigh\label{eqn:chapter2Notes:1040}
\sigma = \lr{\pi r^2} 7.11 \lr{\kappa r}^4, \qquad \kappa = 2 \pi/\lambda.
• Mie scattering (resonance),\label{eqn:chapter2Notes:1060}
\sigma_{\textrm{max}}(A) = 4 \pi r^2

\label{eqn:chapter2Notes:1080}
\sigma_{\textrm{max}}(B) = 0.26 \pi r^2.
• optical limit ( $$r \gg \lambda$$ )\label{eqn:chapter2Notes:1100}
\sigma = \pi r^2.

fig 10. Scattering from a sphere vs frequency (from Prof. Eleftheriades’ class notes).

FIXME: Do I have a derivation of this in my optics notes?

## Notation

• Time average.
and the text [1] use square brackets $$[\cdots]$$ for time averages, not $$<\cdots>$$. Was that an engineering convention?
writes $$\Omega$$ as a circle floating above a face up square bracket, as in fig. 1, and $$\sigma$$ like a number 6, as in fig. 1.
• Bold vectors are usually phasors, with (bold) calligraphic script used for the time domain fields. Example: $$\BE(x,y,z,t) = \ecap E(x,y) e^{j \lr{\omega t – k z}}, \boldsymbol{\mathcal{E}}(x, y, z, t) = \textrm{Re} \BE$$.

fig. 11. Prof. handwriting decoder ring: Omega

fig 12. Prof. handwriting decoder ring: sigma

# References

[1] Constantine A Balanis. Antenna theory: analysis and design. John Wiley \& Sons, 3rd edition, 2005.

[3] David Jeffrey Griffiths and Reed College. Introduction to electrodynamics. Prentice hall Upper Saddle River, NJ, 3rd edition, 1999.

[4] J.D. Irwin. Basic Engineering Circuit Analysis. MacMillian, 1993.

[5] JD Jackson. Classical Electrodynamics. John Wiley and Sons, 2nd edition, 1975.

[6] L.D. Landau and E.M. Lifshitz. The classical theory of fields. Butterworth-Heinemann, 1980. ISBN 0750627689.


text:
• Nov 24th 2012, 11:52 PM
aroe
Sqrt(x)=-x

x=0

Right? It can't be positive or negative so it has to be 0.
• Nov 24th 2012, 11:53 PM
jakncoke
looks good.
• Nov 24th 2012, 11:59 PM
MarkFL
You could arrange as:

$x+\sqrt{x}=0$

$\sqrt{x}(\sqrt{x}+1)=0$

Since $0\le\sqrt{x}$ we must have:

$\sqrt{x}=0$

$x=0$

format: plain


text:
# Why can't I make a TimeSeriesForecast with a GARCH model?

I am playing with TimeSeriesForecast and I find that it invariably forecasts 0 for GARCH models. It is possible that I am misunderstanding TimeSeriesForecast, or that I am misunderstanding GARCH models and I would appreciate any guidance.

Take as an example,

data = {5., 9., 8., 10., 6.1, 10.4, 9.1, 11.6, 7.5, 12.1, 10.4, 13.5,
9., 14.1, 11.9, 15.7, 10.8, 16.4, 13.7, 18.3, 12.9, 19., 15.8, 21.2,
15.3, 22.1, 18.3, 24.6, 20, 20, 31, 31, 42, 42, 55, 55, 43, 22, 11,
233, 432, 12, 23, 34, 23};

TimeSeriesModelFit and TimeSeriesForecast work for ARMA and other model types. For example,

In[]:= tsArima = TimeSeriesModelFit[data, "ARIMA"];
In[]:= TimeSeriesForecast[tsArima, 10]
Out[]= 33.2511 (* ok, works *)

In[]:= tsGarch = TimeSeriesModelFit[data, {"GARCH", {1, 1}}];
In[]:= TimeSeriesForecast[tsGarch , 10]
Out[]= 0 (* always *)

It doesn't matter what the source data is, GARCH always returns 0 and never produces an error. What am I missing here?

• I note that there is an example in the GARCHProcess documentation that precisely does this, and where the author does not seem to be surprised at all. Perhaps something related to a property of this random process? Oct 11, 2016 at 21:29

TimeSeriesForecast returns the conditional expectation which for GARCH process is always zero. Therefore you always get 0. Now TimeSeriesForecast[tsGarch, 10] returns a forecasted value ONLY, hence you get 0. If you want to get the forecast WITH the errors, you need to call TimeSeriesForecast with a list of steps so it does return TemporalData that carries the error information:

In[8]:= data = {5., 9., 8., 10., 6.1, 10.4, 9.1, 11.6, 7.5, 12.1,
10.4, 13.5, 9., 14.1, 11.9, 15.7, 10.8, 16.4, 13.7, 18.3, 12.9,
19., 15.8, 21.2, 15.3, 22.1, 18.3, 24.6, 20, 20, 31, 31, 42, 42,
55, 55, 43, 22, 11, 233, 432, 12, 23, 34, 23};

In[21]:= tsGarch = TimeSeriesModelFit[data, {"GARCH", {1, 1}}];
forecast = TimeSeriesForecast[tsGarch, {1}];

Out[23]= TemporalData

In[24]:= forecast["Path"]

Out[24]= {{45, 0}}

In[25]:= forecast["Properties"]

Out[25]= {"Components", "DateList", "DatePath", "DatePaths", "Dates", \
"FirstDates", "FirstTimes", "FirstValues", "LastDates", "LastTimes", \
"LastValues", "MeanSquaredErrors", "Part", "Path", "PathCount", \
"PathFunction", "PathFunctions", "PathLength", "PathLengths", \
"Paths", "PathTimes", "SliceData", "SliceDistribution", "TimeList", \
"Times", "ValueDimensions", "ValueList", "Values"}

In[26]:= errors = forecast["MeanSquaredErrors"];


text:
# Tag Info

## Hot answers tagged topology

50

All of physics has two aspects: a local or even infinitesimal aspect, and a global aspect. Much of the standard lore deals just with the local and infinitesimal aspects -- the perturbative aspects_ and fiber bundles play little role there. But they are the all-important structure that govern the global -- the non-perturbative -- aspect. Bundles are the ...

33

We need to be precise about the phrase the size of the universe. Specifically I'm going to take it to mean the maximum possible separation between any two points. In an infinite universe two points can be separated by an arbitrarily large distance, so if the maximum distance between two points is finite this means the universe must not be infinite. The ...

32

Topology is of fundamental importance even to systems in classical mechanics. The configuration space (or phase space) of a generic classical mechanical system is a manifold and manifolds are topological spaces with some extra structure (e.g. a smooth structure in the case of smooth manifolds). At the very start of any classical mechanics problem, you need ...

26

Basically, this is related to the theory of Riemann surfaces. Such surfaces arise in complex analysis when one tries to extend the complex plane to make multi-valued functions well-defined. Take a simpler example first. Consider the function $f(z) = \sqrt{ z}$. This function is not single valued since $f( e^{2\pi i } z ) = - f(z)$. The usual way this is ...

24

I'm not going to provide a full answer here, because I don't know the answer, but I want to give some statements that illustrate quite nicely the kind of problems one would face when determining topology of anything: We know spacetime is a manifold. That means, locally, it looks just like $\mathbb{R}^4$. That's already a bummer. We can't do jack at one ...

20

Just one additional point that I haven't seen mentioned above: if the space-time has non-trivial fundamental group, it won't be seen by an observer at infinity. This is the content of the Topological Censorship Theorem. The implication is that for an asymptotically flat space-time, any interesting topology will be hidden behind the event-horizon. The proof ...

18

There are a bunch of questions here. Let me try to take them in order: Is it possible that our Universe has the feature that if you travel far enough you return to where you started? Yes. The standard Big-Bang cosmological model is based on the idea that the Universe is homogeneous and isotropic. One sort of homogeneous spacetime has the geometry of a 3-...

18

In the presence of massless chiral fermions, a $\theta$ term in can be rotated away by an appropriate chiral transformation of the fermion fields, because due to the chiral anomaly, this transformation induces a contribution to the fermion path integral measure proportional to the $\theta$ term Lagrangian. $$\psi_L \rightarrow e^{i\alpha }\psi_L$$ $${\... 17 As far as I understand it there are essentially two ways in which you can study quantum mechanics on a manifold with some curvature. Classically speaking these two ways lead to the same physics but in a quantum mechanical approach they are distinct. The first approach is to think of a particle moving "freely" through three-dimensional space, but subject to ... 17 Let me first answer your second questions about the physical intuition behind fiber bundles: Fiber bundles ( with compact structure groups) describe internal degrees of freedom such as spin and isospin just as manifolds describe translational degrees of freedom. For example, (a non-trivial fibre bundle is needed to describe the rotation of a neutral spinning ... 15 This claim is simply wrong. The flat hyperplane is of course infinite, but non trivial topologies can be flat and still finite. The simplest example is the 3-torus, but there are even the Klein bottle and the Hantzsche-Wendt manifold. See for example page 27 of Janna Levin - Topology and the Cosmic Microwave Background, which show you ten different closed ... 14 First a warning: I don't know much about either algebraic topology or its uses of physics but I know of some places so hopefully you'll find this useful. Topological defects in space The standard (but very nice) example is Aharonov-Bohm effect which considers a solenoid and a charged particle. Idealizing the situation let the solenoid be infinite so that ... 14 Euler density is simply the integrand in 2n dimensions of the integral that is equal to the Euler characteristic. The Euler characteristic may be written as the integral of the following Euler density in 2n dimensions:$$E_{2n} = \frac{1}{2^n} R_{i_1 j_1 k_1 l_1} \dots R_{i_n j_n k_n l_n} \epsilon^{i_1 j_1 \dots i_n j_n} \epsilon^{k_1 l_1 \dots k_n l_n} $... 14 Well, the simplest case is that some topologies of spacetime may only allow a particular class of metrics. But unfortunately, it usually requires the knowledge of the metric at every point to be quite certain. Here's a few thing we can probably assume about the spacetime manifold : All the usual jazz about manifolds in general relativity (paracompactness,... 14 The bible for the mathematical formulation of classical Mechanics, namely Foundations of Mechanics by Abraham and Marsden, defines a hamiltonian system as a triple$(M, \omega, X_H)$where$(M, \omega)$is a symplectic manifold, and$X_H$is the Hamiltonian vector field corresponding to a hamiltonian function$H:M\to\mathbb R$. Now, are there typically any ... 13 Our spacetime cannot be unorientable. That's because the laws of physics describing our spacetime are not left-right symmetric. We say that they break the P-symmetry (parity) or that they are "chiral" (derived from a Greek word for the hand which is either left or right.) For example, a left-handed neutrino would turn into a right-handed neutrino if you ... 13 Very loosely speaking the reasoning is this. Imagine a two band system in which the fermi sea has one filled band with Chern number$n$and another system with$N$filled bands but also with Chern number$n$. Physically they have the same topological properties (for example the same Hall conductance, edge states and so on), but cannot be deformed ... 13 No, because a Lorentz transformation is continuous with a continuous inverse. While an open ball is not mapped to itself, it is mapped to some other open set, in an invertible way. (That a Lorentz transformation is continuous of course follows from that it is linear.) 11 I don't know the answer, but your intuition is right on -- the fact that the equations are local doesn't mean that there cannot be a constraint on the topology of a global solution. For example, in Euclidean signature,$R_{ij} = g_{ij}$immediately implies that the scalar curvature is positive, which in turn leads to topological constraints. If the four-... 11 the answer to the Magellan question for our Universe is actually "No". If the Universe were a static 3-sphere, as Ted Bunn suggests, then you could "swim" around the Universe just like Megallan around the Earth. But an important fact about our Universe is that its size is changing: the size can't stay constant just like the apple can't sit in the middle of ... 11 I was always told that to find whether or not a field is conservative, see if the curl is zero. This is almost always true, but not always true. I have now been told that just because the curl is zero does not necessarily mean it is conservative. Correct! To illustrate what's going on, let's do an example. Conside the following vector field:$$\vec{... 10 Here is an overview of quantization methods: http://arxiv.org/abs/math-ph/0405065 Most of this article deals with QM on manifolds. 10 No. Firstly, weak cosmic censorship can only hold in the generic sense, as there are known examples of nakedly singular space-times. (See, e.g. Christodoulou 1993, and Christodoulou 1999.) Observe in particular that the nakedly singular space-time constructed in the 1993 paper is spherically symmetric with a central axis, and the initial data is ... 10 Orbifolds are spaces of the type$O = M/G$where$M$is a manifold and$G$is a group acting nonfreely on$M$. That is there are fixed points (or more generally submanifolds of this action); i.e., points$x \in M$such that$G.x = x$for all$G$. These fixed points are called singular points, they have the property that geometrical objects (such as the ... 10 You can't do calculus on a manifold that is not Hausdorff and paracompact. If you can't do calculus, doing physics with field equations is pretty pointless. 10 The phase space is a symplectic manifold, so any manifold$\mathcal{M}$that admits a closed nondegenerate 2-form is a possible phase space. Now, what is necessary (or sufficent) for admitting such a form? First, as you mention,$\mathcal{M}$must be even-dimensional. Second,$\mathcal{M}$must be orientable. Why? Because orientability is equivalent to ... 10 As has been discussed in many questions around here (e.g. here), relativity tells us only about local properties and behavior of a space-time. There are some exceptions when we make global assumptions - if we have a space of globally and strictly constant positive curvature, non-trivial topology is imminent because the space has to be the 3-sphere$\mathbb{S^...

10

My favorite reference for these sorts of things that straddle physics and geometry is Frankel's "The geometry of physics". In the chapter on harmonic forms, you will find what he refers to simply as "Hodge's Theorem". It's a little more general than you need, because it applies to general $p$-forms, and you only need functions (0-forms). So I'll ...

9

Since only a fraction of the universe is actually observable, I am not sure if it possible to answer this question.

Only top voted, non community-wiki answers of a minimum length are eligible


text:
### 9 responses to “Political Districting and OR”

1. The flaw here is that “fairness” is defined (by the party in power at the time of redistricting) as “keeps our seats safe for the indefinite future”. So perhaps a more practical model would minimize the geometric goofiness of districts with a side constraint that the incumbent party should retain at least as many “safe” districts as they currently own. (Not that I’m being cynical or anything.)

2. orbythebeach

Paul: Thanks for the comment. I agree that all kinds of cheating strategies are applied, but the (my) hope is that, by using an OR model, the definition of fairness would have to be made explicit and precise, and perhaps we’d get a bit closer to actual fairness.

3. Robert

Here is a link I saw a long time ago about another approach
to redistricting designed by a mathematician.
http://rangevoting.org/SplitLR.html Haven’t looked at in depth but
it seems more geometrically inspired.

4. orbythebeach

Robert: thanks for the link. I’ll check it out.

5. @Tallys: I’m sympathetic to the desire for transparency,
but my strong suspicion is that any redistricting method that
requires approval by the very people who benefit from unfairness.
The one hope would be judicial intervention to require a truly fair
algorithm, but I’m not sure the judiciary would have grounds to
intervene.

6. I think Paul Rubin and I agree on most everything. But I would add that it doesn’t take OR (now called “Business Analytics” by the way) to tackle the problem. It just takes a ruler, either the kind that dictates (like a strong governor) or the measuring stick kind. Draw a square or rectangular boundry no more than x miles around a district and adjust for geography, like rivers. We, in Florida, have the most aggregious district around—it runs from Jacksonville to Orlando, at some places just the width of I-4. It will be interesting to see if it ever gets changed.

7. orbythebeach

Barry: thank you for the comment. The distinction between Business Analytics and OR will vary from person to person, depending on how you define OR. For example, some people would say that Statistics is part of OR, but that’s not a universal belief. For an interesting point of view on the distinction between Analytics and OR, see the comment by Michael Rappa on this blog post. I certainly agree that it’s easy to come up with a feasible solution manually by just looking at the map, but I still believe that using an optimization model can bring you closer to satisfying criteria like population equality with a lot less trial-and-error. Of course, as Paul correctly pointed out, this is one of those problems in which the decision makers are biased against the mathematically ideal optimal solution. Nevertheless, I still enjoy having this kind of discussion because it highlights the pros and cons of the mathematical approach and helps increase the visibility of our field.

8. I have another reading on the morphing from OR to analytics. You can see my blog of a few days ago at http://www.heizerrenderom.wordpress.com. There are many reasons why the change is needed, and you are 100% correct re stat and the differing views people have (which is, of course, one of the reasons we have a problem in our profession).

9. Burçin Bozkaya

I also read this article and I, myself, have academic and practical experience in use of OR in political districting. I agree that the key issues are fairness (or objectivity) and transparency. When I mention to people that we have algorithms for automated districting, I instantly get a feedback that these are suitable only for other types of districting, not for political districting. Being an OR professional myself, I think otherwise, as OR methodologies, if they can fully (or near-fully) capture the governing rules and they are also transparent, can form an objective framework where few can claim that there is deliberate gerrymandering or other manipulations.

In our recent project with the City of Edmonton in Canada for city council election districting, we applied a heuristic multi-criteria algorithm (that originated from my PhD thesis) integrated with ArcGIS. Using this approach, it is possible to quickly (in a matter of seconds) generate good quality maps that appeal to different tastes (using adjustable weights on multiple criteria). The city officials would in fact take this as their first step and then modify the map as they see fit. But in our experience, the number of modifications were so minimal that we were convinced the algorithm can successfully address most, if not all, of the relevant districting requirements. This work will be published in Interfaces soon. An earlier work of ours was published in EJOR.


text:
# Closeness without distance

In my introduction, I said that topology is fundamentally built on the notion of closeness. Someone very quickly responded on Twitter, because they thought that was wrong. It wasn’t wrong, but it’s easy to see where the confusion came from. Like so much math, Topology is built on a very precise logical and set-theoretic formalism. Mathematicians build those formalisms not because they’re annoying people who want to be mysterious and incomprehensible, but because the precision of those formalisms is critically important.

When you hear a statement like “point A is close to point B in a space S”, you have an intuitive idea of what the word “close” means. But when you try to expand that to math, it could potentially mean several different things. The easiest meaning would be: the distance between A and B is small.

Mathematicians have used that definition for a lot of interesting work. It’s got one limitation though: For it to work, you need to be able to define “distance” in the space. How do you do that? In conventional Euclidean space, we have an easy definition. Describe the position of the two points using Cartesian coordinates: A=(x1, y1), B = (x2, y2). The distance between A and B is:

$d(A, B) = \sqrt{(x_2-x_1)^2 + (y_2-y_1)^2}$

But we’re moving towards the world of topology. We can’t count on our spaces to be Euclidean. In fact, the whole point of topology is, in some sense, to figure out what happens when you have different spatial structures – that is, structures other than the familiar Euclidean one! We need to be able to talk about distances in some more general way. To do that, we’ll create a new kind of space – a space with an associated distance metric. This new space is called a metric space.

A distance metric is conceptually simple. It’s just a special kind of function, from pairs of points in a space to a real number. To be a distance metric, it needs a couple of properties. Suppose that the set of points in the space is $S$. Then a function $d: S \times S \rightarrow \mathbf{R}$ is a distance metric if it satisfies the following requirements:

1. Identity: $\forall s_i, s_j \in S: d(s_i, s_j) = 0 \Leftrightarrow s_i = s_j$
2. Symmetry:$\forall s_i, s_j \in S: d(s_i, s_j) = d(s_j, s_i)$
3. Triangle Inequality: $\forall s_i, s_j, s_k \in S: d(s_i, s_k) \le d(s_i, s_j) + d(s_j, s_k)$
4. Non-negativity: $\forall s_i, s_j \in S: d(s_i, s_j) \ge 0$

A metric space is just the pair $(S,d)$ of a set $S$, and a metric function $d$ over the set. For example:

1. A cartesian plane is a metric space whose metric function is the euclidean distance: $d((a_x,a_y), (b_x,b_y)) = \sqrt{(a_x-b_x)^2 + (a_y-b-y)^2}$.
2. A checkerboard is a metric space with the number of kings moves as the metric function.
3. The Manhattan street grid is a metric space where the distance function between two intersections is the sum of the number of horizontal blocks and the number of vertical blocks between them.

All of this is the mathematical work necessary to take one intuitive notion of closeness – the idea of “two points are close if there’s a small distance between them” and turn it into something formal, general, and unambiguous. But we still haven’t gotten to what closeness means in topology! It’s not based on any idea of distance. There are many topological spaces which aren’t metric spaces – that is, there’s no way to define a metric function!

Fortunately, metric spaces give us a good starting point. In topological spaces, closeness is defined in terms of neighborhoods and open balls.

Take a metric space, $(S, d)$, and a point $p \in S$. An open ball B(p, r) (that is, a ball of radius $r$ around the point $p$) is the set of points $x \in S | d(p, x) < r$.

Given a large enough set of points, you can create an infinite series of concentric open spheres: $B(p, \epsilon), B(p, 2\epsilon), B(p, 3\epsilon)$, and so on. Once you’ve got that series of ever-smaller and ever-larger open balls around a point $p$, you’ve got another notion of closeness. $A$ is closer to $p$ than $B$ is if $A$ is in a smaller open ball around $p$.

This is the heart of topology. You can define something like an open-ball on a set without a metric. As long as you can create a consistent sequence of open balls, where each larger ball is a strict superset of all of the smaller ones, you can define closeness without any notion of measurable distance!

In the next post, we’ll use this notion of a distance-free sense of closeness to define what a topology actually is.

## 3 thoughts on “Closeness without distance”

1. David Starner

Unless I’m misunderstanding what cardinality means here, “where each larger ball has a larger cardinality than one of the smaller ones” is incorrect, no? {x where |x – (0 + 0i)| 0, even though the ball where r = 2 encloses the smaller ball where r = 1.

2. Pingback: Alberta Crisafulli


text:
Induction Proof of Inequality Involving Summation and Product

Reckoner

Member
I'm reading "An Introduction to Mathematical Reasoning," by Peter Eccles. It has some interesting exercises, and right now I'm stuck on this one:

"Prove that

$\frac1n\sum_{i=1}^nx_i \geq \left(\prod_{i=1}^nx_i\right)^{1/n}$

for positive integers $$n$$ and positive real numbers $$x_i$$."

The author notes, "It does not seem possible to give a direct proof of this result using induction on $$n$$. However, it can be proved for $$n = 2^m$$ for $$m\geq0$$ by induction on $$m$$. The general result now follows by proving the converse of the usual inductive step: if the result holds for $$n = k + 1$$, where $$k$$ is a positive integer, then it holds for $$n = k$$."

So, following the author's advice, I try to show that

$\frac1{2^m}\sum_{i=1}^{2^m}x_i \geq \left(\prod_{i=1}^{2^m}x_i\right)^{1/2^m}$

for nonnegative integers $$m$$. The base case is straightforward. Here's what I've tried for the inductive step:

Assume

$\frac1{2^k}\sum_{i=1}^{2^k}x_i \geq \left(\prod_{i=1}^{2^k}x_i\right)^{1/2^k}$

for some $$k \geq 0$$. Then

$\frac1{2^{k+1}}\sum_{i=1}^{2^{k+1}}x_i = \frac12\left(\frac1{2^k}\sum_{i=1}^{2^k}x_i + \frac1{2^k}\sum_{i=2^k+1}^{2^{k+1}}x_i\right).$

Letting $$j = i - 2^k,$$ we have

$\frac12\left(\frac1{2^k}\sum_{i=1}^{2^k}x_i + \frac1{2^k}\sum_{i=2^k+1}^{2^{k+1}}x_i\right) = \frac12\left(\frac1{2^k}\sum_{i=1}^{2^k}x_i + \frac1{2^k}\sum_{j=1}^{2^k}x_{j+2^k}\right)$

$\geq\frac12\left(\prod_{i=1}^{2^k}x_i\right)^{1/2^k} + \frac12\left(\prod_{j=1}^{2^k}x_{j+2^k}\right)^{1/2^k}\mbox{ (by inductive hypothesis)}$

$=\frac12\left(\prod_{i=1}^{2^k}x_i\right)^{1/2^k} + \frac12\left(\prod_{i=2^k+1}^{2^{k+1}}x_i\right)^{1/2^k}.$

And I'm not sure where to go from here. All that would be left is to show that

$\frac12\left(\prod_{i=1}^{2^k}x_i\right)^{1/2^k} + \frac12\left(\prod_{i=2^k+1}^{2^{k+1}}x_i\right)^{1/2^k}\geq \left(\prod_{i=1}^{2^{k+1}}x_i\right)^{1/2^{k+1}},$

but I'm not seeing it. Maybe I need to employ a different strategy altogether. Any ideas?

Evgeny.Makarov

Well-known member
MHB Math Scholar
And I'm not sure where to go from here. All that would be left is to show that

$\frac12\left(\prod_{i=1}^{2^k}x_i\right)^{1/2^k} + \frac12\left(\prod_{i=2^k+1}^{2^{k+1}}x_i\right)^{1/2^k}\geq \left(\prod_{i=1}^{2^{k+1}}x_i\right)^{1/2^{k+1}},$
Now use the base case (for two numbers) again.

This proof, along with several others, is given in Wikipedia. I am not sure about the following claim, though: 'The general result now follows by proving the converse of the usual inductive step: if the result holds for n=k+1, where k is a positive integer, then it holds for n=k."' If we denote by $P(n)$ the claim that the arithmetic mean of n numbers is >= the geometric mean of those numbers, the proof first establishes $\forall k\, P(2^k)$ by induction on k. The last part of the proof shows that $P(m)$ and $n < m$ imply $P(n)$, so, in particular, indeed $P(2^{k+1})$ implies $P(2^k)$. However, it is not necessary to go from $P(2^{k+1})$ to $P(2^k)$; rather, if $2^k<n<2^{k+1}$, one goes from $P(2^{k+1})$ to $P(n)$.

Reckoner

Member
Now use the base case (for two numbers) again.
Wow, I completely missed that. The left-hand side is really just the mean of two positive numbers. Thanks a lot, I got it from here.

The last part of the proof shows that $P(m)$ and $n < m$ imply $P(n)$, so, in particular, indeed $P(2^{k+1})$ implies $P(2^k)$. However, it is not necessary to go from $P(2^{k+1})$ to $P(2^k)$; rather, if $2^k<n<2^{k+1}$, one goes from $P(2^{k+1})$ to $P(n)$.
Unless I misunderstand you, I believe that is exactly what the author is saying. We've shown that, $$\forall k\geq0, P(2^k),$$ so to prove $$P(k)\,\forall k\geq1$$ we prove that $$P(k+1)\Rightarrow P(k)$$.

Evgeny.Makarov

Well-known member
MHB Math Scholar
Unless I misunderstand you, I believe that is exactly what the author is saying. We've shown that, $$\forall k\geq0, P(2^k),$$ so to prove $$P(k)\,\forall k\geq1$$ we prove that $$P(k+1)\Rightarrow P(k)$$.
Even if we prove the converse of the usual inductive step, we don't use induction in the opposite direction. If we used such opposite induction, then we would start, say, with P(8), from there prove P(7), use it to prove P(6) and use that to prove P(5). Instead, P(5) is proved directly from P(8). Why emphasize $P(k + 1)\Rightarrow P(k)$ and create an impression that $P(2^k)\Rightarrow P(n)$ for $n < 2^k$ is proved in $2^k-n$ steps when it is proved in one step?

Evgeny.Makarov

Well-known member
MHB Math Scholar
I was looking at the Wikipedia proof, which deals with the last part in one step. I should have realized that it is indeed reasonable (and more formal) to prove $P(k + 1)\Rightarrow P(k)$ for all k and thus prove $P(n)$ from $P(2^k)$ in $2^k-n$ steps.

Reckoner

Member
I was looking at the Wikipedia proof, which deals with the last part in one step. I should have realized that it is indeed reasonable (and more formal) to prove $P(k + 1)\Rightarrow P(k)$ for all k and thus prove $P(n)$ from $P(2^k)$ in $2^k-n$ steps.
Yes, after taking a look at that proof, I understand what you were saying - they proved the statement for a general positive integer less than $$2^k$$. I believe the author of my text worded his note in a way to emphasize the induction process, because one of the preceding chapters was an introduction to induction.

Thanks for the help.


text:
Near-optimal bounds for phase synchronization

# Near-optimal bounds for phase synchronization

## Abstract

The problem of phase synchronization is to estimate the phases (angles) of a complex unit-modulus vector from their noisy pairwise relative measurements , where is a complex-valued Gaussian random matrix. The maximum likelihood estimator (MLE) is a solution to a unit-modulus constrained quadratic programming problem, which is nonconvex. Existing works have proposed polynomial-time algorithms such as a semidefinite relaxation (SDP) approach or the generalized power method (GPM) to solve it. Numerical experiments suggest both of these methods succeed with high probability for up to , yet, existing analyses only confirm this observation for up to . In this paper, we bridge the gap, by proving SDP is tight for , and GPM converges to the global optimum under the same regime. Moreover, we establish a linear convergence rate for GPM, and derive a tighter bound for the MLE. A novel technique we develop in this paper is to track (theoretically) closely related sequences of iterates, in addition to the sequence of iterates GPM actually produces. As a by-product, we obtain an perturbation bound for leading eigenvectors. Our result also confirms intuitions that use techniques from statistical mechanics.

Keywords:

angular synchronization, nonconvex optimization, semidefinite relaxation, power method, maximum likelihood estimator, eigenvector perturbation bound.

## 1Introduction

Phase synchronization is the problem of estimating angles in based on noisy measurements of their differences . This is equivalent to estimating phases from measurements of relative phases .

A typical noise model for this estimation problem is as follows. The target parameter (the signal) is the vector with entries . The measurements are stored in a matrix such that, for ,

where is the noise level and are independent standard complex Gaussian variables. Under this model, defining and for consistency, the model is compactly written in matrix notation as

where both and are Hermitian. An easy derivation1 shows that a maximum likelihood estimator (MLE) for the signal is a global optimum of the following quadratically constrained quadratic program (we define ):

Problem is non-convex and hard in general ([?]). Yet, numerical experiments in [?] suggest that, provided ,2 the following convex semidefinite relaxation for admits as its unique global optimum with high probability (more generally, if the problem below admits a solution of rank 1, , then the relaxation is said to be tight and is an optimum of ):

In this paper, we give a rigorous proof for this observation, improving on the previous best result which only handles [?]. Our result also provides some justification for the analytical prediction in [?] on optimality of the semidefinite relaxation approach.3

In the theorem statement, “up to phase” refers to the fact that the measurements are relative: the distribution of does not change if is replaced by for any angle , so that if is a solution of , then necessarily so is for any , and can only be recovered up to a global phase shift.

Theorem ? shows that the non-convex problem enjoys what is sometimes called hidden convexity, that is, in the proper noise regime, it is equivalent to a (tractable) convex problem. As a consequence, it is not a hard problem in that regime, suggesting local solvers may be able to solve it in its natural dimension. This is desirable, since the relaxation , while convex, has the disadvantage of lifting the problem from to dimensions.

And indeed, numerical experiments in [?] suggest that local optimization algorithms applied to directly succeed in the same regime as . This was confirmed theoretically in [?] for , using both a modification of the power method called the generalized power method (GPM) and local optimization algorithms acting directly on the search space of , which is a manifold. Results pertaining to GPM have been rapidly improved to allow for in [?].

In this paper, we consider a version of GPM listed as Algorithm ? and prove that it works in the same regime as the semidefinite relaxation, thus better capturing the empirical observation. Note that GPM, as a local algorithm, is a more desirable approach versus semidefinite relaxation in practice. GPM and its variants are also considered in a number of related problems [?], and can be seen as special cases of the conditional gradient algorithm [?].

To establish both results, we develop an original proof technique based on following separate but closely related sequences of feasible points for , designed so that they will have suitable statistical independence properties. Furthermore, as a necessary step toward proving the main theorems, we prove an perturbation bound for eigenvectors, which is of independent interest.

It is worth noting that for , it is impossible to reliably detect, with probability tending to 1, whether is of the form or if it is only of the form [?], which suggests that is necessary in order for a good estimator to exist. This can be made precise by considering the simpler problem of synchronization,4 where we have the stronger knowledge that . For the synchronization problem, non-rigorous arguments that use techniques from statistical mechanics show is the information-theoretic threshold for mean squared estimation error (MSE): when is above this threshold, no estimator is able to beat the trivial estimator as [?]. In [?], it was rigorously proved that is the threshold for a different notion of MSE. These results a fortiori imply, for phase synchronization, that is necessary5 in order for an estimator to have nontrivial MSE (better than the trivial estimator ). It is also known that both the eigenvector estimator and the MLE have nontrivial MSE as soon as [?]. Whether the extra logarithmic factor is necessary to compute the MLE efficiently up to the threshold remains to be determined.

To close this introduction, we state the relevance of the MLE as an estimator for .

The bound on error appears in [?], while the bound on error improves on [?] as a by-product of the results obtained here. We remark that is necessary for a nontrivial error (smaller than , which is trivially attained by ) due to [?].6

It is important to state that the eigenvector estimator mentioned above is order-wise as good an estimator as the MLE, in that it satisfies the same error bounds as in Theorem ? up to constants. From the perspective of optimization, the main merit of Theorems 1 and 2 is that they rigorously explain the empirically observed tractability of (P) despite non-convexity.

### The difficulty: statistical dependence

As will be argued momentarily, the main difficulty in the analysis is proving a sharp bound for , which involves two dependent random quantities: the noise matrix and a solution of , which is a nontrivial function of . While in the -norm the simple bound is sharp, no such simple argument is known to bound the -norm. The need to study perturbations in -norm appears inescapable, as it arises from the entry-wise constraints of and the aim to control as well as .

This issue has already been raised in [?], which focuses on the relaxation (Equation 4). Specifically, in [?], it is shown that the relaxation is tight in particular if

where is an optimum of which is then unique up to phase. From this expression, it is apparent that if , it only remains to show that to conclude that solving is equivalent to solving . This reduces the task to that of carefully bounding this scalar, random variable:

where are the columns of the random noise matrix . If and were statistically independent, this would be bounded with high probability by , as desired. Indeed, since the vector contains only phases and since the Gaussian distribution is isotropic (the distribution is invariant under rotation in the complex plane), would be distributed identically to a sum of independent standard complex Gaussians. The modulus of such a variable concentrates close to . Taking the maximum over incurs an additional factor.

Unfortunately, the intricate dependence between and has not been satisfactorily resolved in previous work, where only suboptimal bounds have been produced for , eventually leading to suboptimal bounds on the acceptable noise levels [?][?][?].

As a key step to overcome this difficulty, we (theoretically) introduce auxiliary problems to transform the question of controlling into one about the sensitivity of the optimum to perturbations of the data. This is outlined next.

### Introducing auxiliary problems to reduce dependence

Since the main concern in controlling is the statistical dependence between and , we introduce new optimization problems of the form , where, for each value of in , the cost matrix is replaced by

where is the indicator function. In other terms, is with the th row and column set to 0, so that is statistically independent from . As a result, a global optimum of with set to is also independent from . This usefully informs the following observation, where the global phases of and are chosen so that :

Crucially, independence of and implies the first term is with high probability, by the argument laid out after eq. . In the second term, a standard concentration argument shows with high probability—see Section 3. Hence, to control , it is sufficient to show that, with high probability for all , the solutions and are within distance of each other, in the sense.

This claim about the proximity of and turns out to be a delicate statement about the sensitivity of the global optimum of to perturbations of only measurements which involve the th phase, . To establish it, we need precise control of the properties of the optima of . To this end, we develop a strategy to track the properties of sequences which converge to as well as to for each .

To ease further discussion about distances up to phase, consider the following distance-like function:

Restricted to complex vectors of given -norm or to complex vectors with unit-modulus entries, is a true metric on the quotient space induced by the equivalence relation :

Thus, is appropriate as a distance between estimators for and as a distance between candidate eigenvectors, being invariant under global phase shifts. Moreover, the quotient space is a complete metric space with . More details will follow.

Coming back to our problem, the core argument is an analysis of recursive error bounds of GPM, and this analysis leads to the proof that all iterates stay in , where

and are some constants (determined in Section 4). On one hand, we show that, with high probability, the nonlinear mapping iterated by GPM is Lipschitz continuous over with constant . On the other hand, we show that, with high probability, all iterates of GPM are in . Together, these two properties imply that, with high probability, is a contraction mapping over the set of iterates of GPM. By a completeness argument, this implies that the sequence of iterates of GPM converges in . The roadmap of our proof is the following:

1. (this requires developing new bounds for eigenvector perturbation—see Theorem ?),

2. (this is done in two stages,7 for small and large —see Theorems ? and ?),

3. is -Lipschitz with on with respect to (by completeness, this implies —see Lemma ?), and

4. any fixed point of in is a global optimum of (see Lemma ?).

On top of securing results about GPM, this will imply that admits a solution which is in and hence, a fortiori, satisfies , yielding the announced results about the SDP relaxation as per .

As hinted above, we follow this reasoning not only for the sequence which is expected to converge to , but also for auxiliary sequences expected to converge to . It is only through exploitation of the strong links between these sequences and reduction in statistical dependence they offer that we are able to go through with the proof program above.

Note that might not be a contraction mapping on all of since we do not show that . Nevertheless, is a contraction on the iterates, which is sufficient for our purpose; henceforth, we say the mapping has the local contraction property.

We remark that, in the study of high-dimensional -estimation [?], the idea of introducing auxiliary problems (and associated optimizers) is also used to tackle dependence, and it yields powerful analysis. While sharing similarity with that approach, our analysis relies on studying auxiliary sequences of iterates, as will be discussed soon—also see Figure 1.

As a necessary and useful warm-up, we first focus on the task of showing that (a leading eigenvector of ) is in , via analysis of the related (leading eigenvectors of ). This requires sharp bounds for . The outcome of this analysis is an eigenvector perturbation bound in the -norm, which is another motivation for the introduction of auxiliary problems.

### First analysis: an ℓ∞ perturbation bound for eigenvectors

As the initializer of Algorithm ?, the leading eigenvector of has several good properties necessary for analysis, and we will discuss them in depth in Section 3. Theorems and lemmas in this direction are stated separately and proved first, because their proof is illustrative of the techniques deployed to prove results about . Most notably, we prove a sharp perturbation bound for leading eigenvectors.

The crux of the proof lies in a sharp bound on . This is obtained by using (a suitable version of) the Davis–Kahan theorem (Lemma ?): when ,

To reach the first conclusion, we view as the perturbed version of due to perturbation . Note that has nonzero entries only in the th row and th column, and they are independent of . Compared to the full perturbation which perturbs the eigenvector to , the matrix results in a much smaller distance between and . Notice that, as will be detailed later, these results combined with the reasoning of imply that is in , as desired.

Comparing Theorem ? to Theorem ? readily shows that the eigenvector is an excellent estimator for (up to the fact that its entries are not necessarily unit-modulus, which can be easily corrected—see Theorem ?). Further efforts in this paper are dedicated to characterizing the performance and tractability of the MLE .

### Analysis of iterations: tracking n auxiliary sequences

While analyzing the eigenvector is relatively straightforward, the optima of are more difficult to tame due to the unit-modulus constraints. As hinted above, the novel idea we develop in this paper is to track the sequences produced by Algorithm ? with inputs instead of , for each . These auxiliary sequences—which only serve for the analysis and are not (and could not be) computed in practice—enjoy the crucial proximity property desired in the previous subsection—see Figure 1.

Indeed, we will show by induction that there exist absolute constants such that, for all and for ,

The proximity and local contraction properties8 are both crucial and complementary for the analysis: the proximity property allows to control quantities in the presence of the random matrix despite statistical dependence (as shown in ), and the local contraction property is used to establish below, making sure remains small.

For the high-level idea, consider the nonlinear operators and implicitly defined by Algorithm ? so that and . If we can show that is -Lipschitz with constant with respect to , then a recursive error bound follows:

This ensures does not accumulate with , provided the discrepancy error—which is caused by the difference between and —is small enough. This is assured with high probability, because is independent of , causing the discrepancy error to be —considerably smaller than . In spirit, this is the same argument as in the analysis of the eigenvector estimator.

The above recursive error bound hinges on the other important property, that is, staying in the contraction region. Crucially, to establish , we need a tight bound on . Fortunately, we have seen how to control this quantity in : for any ,

This, in turn, requires a proximity result for . This insight naturally motivates an analysis of each iteration by induction.

There are two technical issues we briefly address before ending this introduction with a remark.

The first issue concerns the probabilistic argument in the proof. In (Equation 12) and (Equation 13), we invoke concentration inequalities to obtain tight bounds. However, since there is a (small) probability that such inequalities fail, we cannot use union bounds for , which is infinite. To overcome this obstacle, we use concentration inequalities only for the first iterations, and resort to a deterministic analysis for iterations . The critical observation is that, decays exponentially for due to contraction, so the amount of update is tiny after iterations. Using another inductive argument, we can secure exponential decay for as well. The rationale is that we already established good properties about , and is tiny for , so we can easily relate to and show also has good properties. Essentially, remains in a contraction region with slightly larger constants.

The second issue is identifying the limit with a solution of . We will verify the optimality and uniqueness (up to phase) of via a known dual optimality certificate [?].

We close with a remark about the initializer (and ). Algorithm ? uses the leading eigenvector of for initialization, and our analysis relies on perturbation bounds to verify the base case of the induction. However, we point out that, even in the absence of such perturbation results, we could set in theory, deduce that and thus prove Theorem ? about the SDP relaxation. In other words, even if we leave out the discussion about the initializer altogether, there is still enough material to secure tightness of the SDP relaxation. The proof augmented with the analysis of the eigenvector perturbation has the advantage of also providing a statement about Algorithm ? which is actually runnable in practice.

## 2Main results

In this section we will state our main theorems formally. The assumption on random noise will also be relaxed to a broader class of random matrices. To begin with, let us first clarify the “up to phase” statements in Section 1.

The quotient space For any , whether the true phases are or does not affect the measurements . As a result, the available data are insufficient to distinguish from . Clearly the program is invariant to global phase shifts as well. It thus makes sense to ignore the global phase in defining distances between estimators. A reasonable notion of error then becomes

where the optimal phase is the phase (Arg) of . Similarly, a notion of error can be defined:

Formally, one can partition all points in into equivalence classes via the equivalence relation . The resulting quotient space contains the equivalence classes for all . Specifically, the feasible set of ,

reduces to under this equivalence relation. It is easily verified that defines a distance on . In particular, it satisfies the triangular inequality (where is understood to mean ):

Moreover, is a complete metric space under (see Theorem ?). Similarly, is also a distance. As will be shown, the sequence described in Section 1 satisfies the local contraction property (see ) on the metric space , hence converges to a fixed point which is exactly (understood as ).

The noise matrix In Section 1 we assume that has independent standard complex Gaussian variables above its diagonal. However, this restricted assumption is only for expository convenience, and can be relaxed to the class of Hermitian Wigner matrices with sub-gaussian entries. Statements about Algorithm ? and about tightness of the SDP relaxation continue to hold, although of course the solution of now no longer necessarily corresponds to the MLE.

The class of sub-gaussian variables subsumes Gaussian variables, but has one defining feature similar to Gaussian variables, that is, the tail probability decaying no slower than Gaussian variables. In our model, each entry of satisfies the tail bound

for both real and imaginary parts, where is an absolute constant. Formally, we assume the Hermitian matrix satisfies the following: are jointly independent, have zero mean, and satisfy the sub-gaussian tail bound (Equation 17); the diagonal elements are zero, and for any . Note there are equivalent definitions of sub-gaussian variables (up to constants) [?].

This random model is a much richer class of noise matrices, containing the Gaussian model introduced in Section 1 as a special case. Each random variable in can be, for example, a symmetric Bernoulli variable, any other centered and bounded variable, or simply zero.

SDP approach The SDP approach tries to solve (Equation 3) via its convex semidefinite relaxation (Equation 4). It is a relaxation of in the following sense. For any feasible , the corresponding matrix is feasible for . Likewise, any feasible matrix of rank 1 can be factored as such that is feasible for . Thus, the relaxation consists in allowing solutions of rank more than 1 in . Consequently, if admits a solution of rank 1, , then the corresponding is a global optimum for . Furthermore, if the rank-1 solution of is unique, it can be recovered in polynomial time. For this reason, the regime of interest is one where admits a unique solution of rank 1.

The following theorem—a statement of Theorem ? which holds in the broadened noise model—closes the gap in previous papers [?].

Note that the exponent 2 in the failure probability can be replaced by any positive numerical constant, only affecting other absolute constants in the theorem (and all other theorems).

GPM approach The generalized power method (Algorithm ?) is an iterative algorithm similar to the classical power method, but instead of projecting vectors onto a sphere after matrix-vector multiplication , it extracts the phases from , which is an entry-wise projection. It is much faster than SDP, and converges linearly to a limit, which is the optimum up to phase (optimality is stated in Theorem ?). The next theorem is a precise version of Theorem ?.

The proof is based on induction: in each iteration, we will establish the proximity property and the contraction property for . The proof is simply a rigorous justification of the heuristics we discussed in Section 1. It also leads to and error bounds for . The following theorem is a precise version of Theorem ?.

Eigenvector estimator We denote, henceforth, the leading eigenvector of by , and similarly the leading eigenvector of by . Note that and (similarly and ) are identical.9 We highlight the significance of the eigenvector estimator in the following theorem, which is a precise version of Theorem ?.

The eigenvector estimator has been studied extensively in recent years, prominently in the statistics literature [?], under the spiked covariance model. While the perturbation is usually studied under norms, the norm received much less attention. A recent perturbation result appeared in [?], but it is a deterministic bound and would produce a suboptimal result here.

## 3Proof organization for eigenvector perturbations

We begin with some concentration lemmas, which will also be useful in Section 4. Recall the definition of . We also define , which has nonzero entries only in the th row and th column, given by .

### Concentration lemmas

The first concentration result is standard and is a direct consequence of, for example, Proposition 2.4 in [?].

Let be the set of unit vectors in . Suppose for each we have a finite (random) set whose elements are independent of , and the cardinality of is not random. Concentration inequalities enable us to bound uniformly over all with high probability. We state this formally in the next lemma.

A straightforward application of Hoeffding’s inequality for sub-gaussian variables [?] shows with probability . Lemma ? is more general, because , and it will be useful in later proofs.

For the eigenvector problem, we will choose (a singleton) where is a leading eigenvector of scaled to have norm . For problem (Equation 3), for each , the set will be , namely, the first iterates of Algorithm ? with input , where . By construction, elements of the set are independent of .

### Introducing auxiliary eigenvector problems

As is well known, the leading eigenvectors of are the solutions to the following optimization problem (note that this problem is a relaxation of ):

We aim to show that a solution of is close to in the sense of . As before, the major difficulty of the analysis is obtaining a sharp bound on . This is apparent when we write for the leading eigenvalue of and use to obtain (choosing the global phase of such that ):

While it is easy to analyze and , bounding requires more work.

For , let be the solution to an auxiliary problem in which is replaced by —thus, is equivalent to . Following the same strategy as in , we can now split into two terms and try to bound separately:

where is the dominant term, and can be easily bounded—see the paragraph below Lemma ?; and is the higher-order discrepancy error, which is the price we pay for replacing with .

The crucial point is that , which is much smaller than . This is because the difference between and results from a sparse perturbation , whose effect on the leading eigenvector is small. This point is formalized in the next lemma, which follows from [?].10

The benefit of this perturbation result is pronounced when is a sparse random matrix: if we set , then the numerator in ( ?) becomes with high probability (by Lemma ? and a bound on ). If, however, we set , then the numerator is with high probability. This is why is so small and (Equation 19) yields a tight bound.

We remark that in many later uses of perturbation results (e.g., [?]), especially in statistics and theoretical computer science, it is common to invoke a variant of the Davis–Kahan theorem in which is replaced by in ( ?), which would lead to a suboptimal result here. This is because with high probability when is a random sparse matrix and is not large. Our analysis here is an example that shows the merit of using the more precise version of the Davis–Kahan theorem.

## 4Proof organization for phase synchronization

We begin with some useful lemmas about the local contraction property. These will prove useful to establish the desired properties of the iterates of Algorithm ?, by induction. These properties extend to the limit by continuity. Finally, we will use a known optimality certificate for to validate .

### Local contraction lemmas

First let us denote the rescaled matrix by , which can also be viewed as a linear operator in :

This is a linear combination of (signal) and (noise). When is small compared to , is Lipschitz continuous on the sphere around , with respect to .

This lemma is instrumental in establishing the key local contraction property (Lemma ?). It is related to the contraction mapping theorem, in which an iteratively defined sequence converges to a fixed point. We could use this lemma to easily show (using [?] for example) that the normalized version is a contraction mapping in a neighborhood of on is the power method operator.

However, our problem is more complicated due to the unit-modulus constraints in which call for the entry-wise operator in Algorithm ?. Consequently, an analysis of Algorithm ? requires entry-wise bounds on key quantities in each iteration, which are more involved than bounds. In the next two lemmas, we will see which entry-wise bounds we need in order to establish the local contraction property.

Recall that maps each entry of a vector to the unit circle in the complex plane:

The case will not appear in the proofs because it can be excluded with high probability. Henceforth, we also drop parentheses in for simplicity.

In the next two lemmas, we establish the local contraction property of (the GPM operator) under the distance . Under certain conditions on the input points, shrinks the distance between points by a ratio in . In a rigorous sense, this does not imply that is a contraction mapping, because the output points do not necessarily satisfy the conditions themselves. However, for the sequences of interest, the conditions are satisfied with high probability and this is all we need to ascertain convergence—see Theorems ? and ?.

This lemma says is Lipschitz continuous (in the quotient space ) in a region where and are uniformly lower bounded. The composition , will have the local contraction property as long as the contraction ratio in ( ?) is small enough, and the in ( ?) is not too close to . The next lemma formalizes this result. For later use in the proofs, we also introduce an additional notation: for a Hermitian matrix , we let .

This deterministic lemma states that has the local contraction property in a region where ( ?) and ( ?) are satisfied, as long as . Note that we have to require bounds in because of the entry-wise nature of . In the next subsection, we use this lemma to show that, with high probability, is controlled by where the ratio lies in .

### Convergence analysis

Let us denote the rescaled matrix by , where . Also let . Recall that is identical to the leading eigenvector of , and is identical to the leading eigenvector of ; and they are normalized such that . Algorithm ? iterates . The auxiliary sequences defined for theoretical analysis (not implemented in practice) follow a similar update rule: (Figure Figure 1). Note that, for all , each entry of and has unit modulus, i.e., , but are not in in general.

As shown in Lemma ?, the local contraction property of hinges on the condition that the vectors to be updated are in the contraction region , where and are defined in (Equation 11) and ( ?). The absolute constants in their definitions will be specified in Theorem ?.

In order to show the iterates stay in , we analyze the dependence between the random quantities and by making use of the auxiliary sequences , as illustrated by eq. (Equation 13). As shown in the analysis of eigenvectors in Section 3, we know is small. Owing to the local contraction property (Lemma ?), we can prove the recursive error bound (Equation 12), which ensures that is bounded throughout all iterations. The analysis is based on induction.

As discussed in Section 1, a technical issue is that we cannot use concentration results infinitely many times for all , because we use the union bound to achieve a high probability result. We study first iterates using concentration results, and resort to deterministic analysis for later iterations. In the following theorems, constants are those constants in Lemmas ? and ?.

Note that ( ?) and ( ?) guarantee . Considering from our proof map,

Assuming ( ?) and ( ?) for the case , by the local contraction property (Lemma ?), the first term is bounded by where . By the concentration bounds (Lemma ?), the second term is bounded by with high probability. Therefore, it is expected that ( ?) continues to hold for the case .

This proximity property ( ?) is crucial to show that stays in the local region . To bound , we use the concentration bounds (Lemma ?) and the proximity property ( ?) in the inequality (Equation 13).

To bound , we derive an entry-wise bound on , then use Lemma ?. This is straightforward once we have a bound on .

The next result says decreases geometrically for , which is notably useful to analyze later iterations .

This result is similar to the contraction mapping theorem (though we cannot prove for all ), which says the sequence produced by a contraction mapping is a Cauchy sequence and satisfies an inequality similar to ( ?). After iterations, the update from to is almost negligible. Although we no longer rely on concentration results, we will show, by induction again, that remains very small for all . This ensures that stays in a slightly larger contraction region for all (with larger constants). The next theorem depends crucially on the conclusions of Theorem ? and ?.

Under the stated conditions, this theorem is a deterministic result. By Theorems ? and ?, the conditions hold with high probability (note that when ). This theorem establishes the convergence of and, importantly, the bounds extend to the limit by continuity. This strong characterization of the limit point puts us in a favorable position to verify optimality.

### Verifying optimality

To verify optimality of , it is convenient to use a known dual certificate for the SDP relaxation. The following is a combination of Lemmas 4.3 and 4.4 in [?].

To simplify notation, let . Using the same developments as in [?], we verify that is positive semidefinite and has rank under condition on and the conclusions of Theorem ?, namely, inequalities and equation . By construction, . Hence, it is sufficient to verify that for all with and :

(Owing to , we used , with appropriate choice of .) Now using and assuming and the bounds hold, it follows that

Assume satisfies inequality . Then, using and as in Theorem ?,

Thus, is positive semidefinite and has rank —which implies is the unique solution of and is the unique solution of up to phase by Lemma ?—provided satisfies , and the conclusions of Theorem ? hold. Theorem ? follows directly; details for Theorems ?? are in the appendix.

## 5Conclusions and perspectives

We proved that both semidefinite relaxation and the generalized power method are able to find the global optimum of (Equation 3) under the regime with high probability. In other words, the maximum-likelihood estimator of phase synchronization is computationally feasible under noise level , which (nearly) matches the information-theoretic threshold, thus closing the gap in previous papers. We also derived and bounds on the optimum , and the bound improves upon previous results. The proof is based on tracking auxiliary sequences, which is a novel technique developed in this paper. As a by-product, we also proved an bound for the eigenvector estimator, which is of independent interest.

An interesting problem for future work is to prove (or disprove) that second-order necessary optimality conditions are sufficient for (Equation 3). If this is true, then any algorithm that finds a second-order critical point also solves the nonconvex problem (Equation 3). This was proved in [?] for then in [?] for . Numerical experiments in [?] suggest that a local optimization method (namely, the Riemannian trust-region method) with random initialization finds the global optimum with and random initialization. The analysis presented here does not apply directly though, because it hinges on a characterization of the limit points of GPM: a priori, this does not allow to characterize all second-order critical points.

A natural extension of our work is to establish similar results for synchronization over SO() [?] and SE() [?]. The general synchronization problem is to recover group element from their noisy pairwise measurements . Our work here addresses synchronization over the group SO(2) (equivalently, the group U(1)), that is, in-plane rotations (equivalently, points on the unit complex circle). Another important group in practice is the rotation group SO(3), which is often used to describe the orientation of an object [?]. It is shown empirically in [?] that the Riemannian trust-region method performs well. The analysis may be complicated by the fact that SO(3) is a non-commutative group.

Another important problem in practice is to handle incomplete measurement sets. In this paper, we suppose all entries of are known. A more realistic setting is that some pairs of phase differences are measured, forming edges of a graph. This appears in many applications [?], and is addressed in a number of papers [?]. The effect of an incomplete measurement graph on fundamental bounds is well understood as being related to the Laplacian of the graph [?]. See [?] for robotics applications.

Finally, another problem of practical concern is robustness of estimation methods. Here, (Equation 3) minimizes the sum of squared errors. However, in practice, more robust methods may be required to deal with outliers. In [?] for example, the authors minimize a sum of unsquared errors. A common way to solve such problems is via iterative reweighted least squares (IRLS), which is widely used in statistics [?]. IRLS solves a weighed least squares problem in each step, where the weights depend on the current iterate. In this regard, our analysis could be a first step toward understanding robust methods with IRLS for synchronization problems.

## Acknowledgements

The authors thank Afonso Bandeira, Amelia Perry, Alexander Wein, Amit Singer and Jianqing Fan for helpful discussions.

## AProofs

### Proofs for Section

Let be the upper triangular part of , i.e., , and . Then are all matrices with independent and sub-gaussian entries, whose sub-gaussian moments are bounded by an absolute constant (see [?] for equivalent definitions of sub-gaussian variables). We can then apply Proposition 2.4 in [?] and obtain the desired concentration bound on . For , we take a union bound over choice of . The bound on follows from those on and . The bound on follows from that on , since

We will prove this lemma in the case where is a deterministic set. The case where is random follows easily from the deterministic case, since we can first condition on and use independence between and . In the proof, notations denote some absolute constants. For a fixed and ,

We will bound the two parts on the right-hand side separately. We can expand into a sum: . By assumption, is a sub-gaussian random variable. By Hoeffding’s inequality for sub-gaussian variables [?],

For sums of random variables of , or over , similar concentration results hold. Thus, we can set , where is some large absolute constant such that


text:
## STEM: A Stochastic Two-Sided Momentum Algorithm Achieving Near-Optimal Sample and Communication Complexities for Federated Learning

21 May 2021, 20:49 (modified: 16 Dec 2021, 22:27)NeurIPS 2021 PosterReaders: Everyone
Keywords: Distributed Non-Convex Optimization, Minibatch SGD, Local SGD
Abstract: Federated Learning (FL) refers to the paradigm where multiple worker nodes (WNs) build a joint model by using local data. Despite extensive research, for a generic non-convex FL problem, it is not clear, how to choose the WNs' and the server's update directions, the minibatch sizes, and the local update frequency, so that the WNs use the minimum number of samples and communication rounds to achieve the desired solution. This work addresses the above question and considers a class of stochastic algorithms where the WNs perform a few local updates before communication. We show that when both the WN's and the server's directions are chosen based on certain stochastic momentum estimator, the algorithm requires $\tilde{\mathcal{O}}(\epsilon^{-3/2})$ samples and $\tilde{\mathcal{O}}(\epsilon^{-1})$ communication rounds to compute an $\epsilon$-stationary solution. To the best of our knowledge, this is the first FL algorithm that achieves such {\it near-optimal} sample and communication complexities simultaneously. Further, we show that there is a trade-off curve between local update frequencies and local minibatch sizes, on which the above sample and communication complexities can be maintained. {Finally, we show that for the classical FedAvg (a.k.a. Local SGD, which is a momentum-less special case of the STEM), a similar trade-off curve exists, albeit with worse sample and communication complexities. Our insights on this trade-off provides guidelines for choosing the four important design elements for FL algorithms, the update frequency, directions, and minibatch sizes to achieve the best performance.}
Supplementary Material: pdf
Code Of Conduct: I certify that all co-authors of this work have read and commit to adhering to the NeurIPS Statement on Ethics, Fairness, Inclusivity, and Code of Conduct.
14 Replies


text:
# Cu(NO_3)_2 + Zn(s) -> Cu(s) + Zn(NO_3)_2 is an example of which type of reaction?

$C {u}^{2 +}$ is reduced to copper metal. Zinc metal is oxidized to $Z {n}^{2 +}$. Formal electron transfer has taken place between the ion and the metal, i.e. a redox or oxidation/reduction reaction has occurred.


text:
# Not all interventions are equal for the height of the second peak

Speaker: Joost Jorritsma

Date: Mon, Jun 22, 2020

Location: Zoom

Subject:

Class: Scientific

### Abstract:

We present a simulation study of the spread of an epidemic like COVID-19 with temporary immunity on finite spatial and non-spatial network models. In particular, we assume that an epidemic spreads stochastically on a scale-free network and that each infected individual in the network gains a temporary immunity after its infectious period is over. After the temporary immunity period is over, the individual becomes susceptible to the virus again. When the underlying contact network is embedded in Euclidean geometry, we model three different intervention strategies that aim to control the spread of the epidemic: social distancing, restrictions on travel, and restrictions on maximal number of social contacts per node. Our first finding is that on a finite network, a long enough average immunity period leads to extinction of the pandemic after the first peak, analogous to the concept of herd immunity''. For each model, there is a critical average immunity duration $L_c$ above which this happens. Our second finding is that all three interventions manage to flatten the first peak (the travel restrictions most efficiently), as well as decrease the critical immunity duration $L_c$, but elongate the epidemic. However, when the average immunity duration $L$ is shorter than $L_c$, the price for the flattened first peak is often a high second peak: for limiting the maximal number of contacts, the second peak can be as high as 1/3 of the first peak, and twice as high as it would be without intervention. Thirdly, interventions introduce oscillations into the system and the time to reach equilibrium is, for almost all scenarios, much longer. We conclude that network-based epidemic models can show a variety of behaviors that are not captured by the continuous compartmental models.


text:
$$\require{cancel}$$

# 1: Electric Fields

So, you might ask, if your primary interest in electricity is to understand how machines, instruments and electrical equipment work, is there any point in studying electricity from the very “academic” and abstract approach that will be used in these notes, completely divorced as they appear to be from the world of practical reality? The answer is that electrical engineers more than anybody must understand the basic scientific principles before they even begin to apply them to the design of practical appliances. So – do not even think of electrical engineering until you have a thorough understanding of the basic scientific principles of the subject.

• 1.1: Prelude to Electric Fields
The subject of electromagnetism is an amalgamation of what were originally studies of three apparently entirely unrelated phenomena, namely electrostatic phenomena of the type demonstrated with pieces of amber, pith balls, and ancient devices such as Leyden jars and Wimshurst machines; magnetism, and the phenomena associated with lodestones, compass needles and Earth’s magnetic field; and current electricity – the sort of electricity generated by chemical cells such as Daniel and Leclanché cells
• 1.2: Triboelectric Effect
It was long ago noticed that if a sample of amber is rubbed with cloth, the amber became endowed with certain apparently wonderful properties. For example, the amber would be able to attract small particles of fluff to itself. The effect is called the triboelectric effect. The amber, after having been rubbed with cloth, is said to bear an electric charge, and space in the vicinity of the charged amber within which the amber can exert its attractive properties is called an electric field.
• 1.3: Experiments with Pith Balls
There are two kinds of electric charge, with exactly opposite properties. We observe that like charges (i.e. those of the same sign) repel each other, and unlike charges (i.e. those of opposite sign) attract each other.
• 1.4: Experiments with a Gold-leaf Electroscope
A gold-leaf electroscope has a vertical rod R attached to a flat metal plate. Electroscopes detect electric charge by the motion of a test object due to the Coulomb electrostatic force. Since the electric potential or voltage of an object with respect to ground equals its charge divided by its capacitance to ground, an electroscope can be regarded as a crude voltmeter.
• 1.5: Coulomb's Law
Coulomb’s Law is that two electric charges of like sign repel each other with a force that is proportional to the product of their charges and inversely proportional to the square of the distance between them:
• 1.6: Electric Field E
The region around a charged body within which it can exert its electrostatic influence may be called an electric field. In principle, it extends to infinity, but in practice it falls off more or less rapidly with distance.
• 1.7: Electric Field D
We have been assuming that all “experiments” described have been carried out in a vacuum or (which is almost the same thing) in air. But what if the point charge, the infinite rod and the infinite charged sheet of Section 1.6 are all immersed in some medium whose permittivity is not ϵ0 , but is instead ϵ ?
• 1.8: Flux
The product of electric field intensity and area is the flux . Whereas E is an intensive quantity, flux is an extensive quantity.
• 1.9: Gauss's Theorem
Gauss’s theorem argues that the total normal component of the D -flux through any closed surface is equal to the charge enclosed by that surface.  It is a natural consequence of the inverse square nature of Coulomb’s law.

Thumbnail: The electric field lines and equipotential lines for field of two point charges. (CC BY-SA 3.0; Geek3 via Wikipedia).

This page titled 1: Electric Fields is shared under a CC BY-NC 4.0 license and was authored, remixed, and/or curated by Jeremy Tatum via source content that was edited to the style and standards of the LibreTexts platform; a detailed edit history is available upon request.