Fractional Distances and Moments, Part 1

I've just pulled up out of an obsessive compulsive research project, so hold on as this will be a long post.  I work doing signal integrity for computer system interfaces and one of the critical things we do is evaluate the performance of a bus by quantifying the minimum eye diagram width and height.  The quick and dirty way of obtaining this minimum eye diagram is through Peak Distortion Analysis (PDA) description here and the original PDA paper here.  One of the problems is that for a multi-line system the chances of actually getting this worst case eye diagram is very small and to constrain design based on this alone would be crippling to progress and cost.  So instead the signal integrity community is moving to evaluating the Bit Error Rate (BER) to quantify performance but this is much more complex and  computationally expensive.

Through my research at Intel (DesignCon paper and presentation), I've shown that PDA is just a periodic one-norm and thus is subject to triangle inequality property.  A norm is a  measure of distance and the two-norm or Euclidean norm is the distance metric that most people are familiar with.  A one-norm is the distance one would  travel between two points if you are constrained to some coordinate system.  For instance, a taxi cab driver in Manhattan will charge you the distance he drove you through the city blocks rather than the distance it would take a crow to fly between two points.  The distance the taxi-cab drove is an example of the one-norm.

My obsessive compulsive research was based on the observation that I could replace the 1-norm in the PDA equations with a higher order fractional norm and then then relate this to the BER response of the system.  This would enable a quick and dirty BER calculation and would be really cool.  There is a clear correspondence between one-norm and worst BER value but I had difficulty in mapping the 2-norm value to a specific BER value.  Without a second point I can not relate the two and have concluded that this is just an interesting dead end.   In an effort to justify the countless hours I spent I am going to describe some of my peripheral findings. (That's right, I'm just getting started.)

There are many example of fractional approximations to otherwise discrete relations and equations.  I first became aware of such relations in high school while reading about the chaos theory, fractals and fractional dimensions.  Other well defined examples are fractional calculus, where you can take a 1/2 or 1/3 derivative of a function and the gamma function which is the continuous version of the factorial.  A visual approach to these fractional and higher order ideas is shown with superellipses.  These shapes are the result of the following equation:

|y|^p+|x|^p = 1

Here we see that we get the unit circle for p=2, which is a nice visualization of how euclidean or two-norms measure distance.  A unit circle shows all the points equidistant from the origin.

For p=1 we get the one norm diamond, for p=infinity we get a square and with p=4 we get the squircle (it is seriously called that) which is half way between a circle and square.  With each distinct p value, a different space is mathematically defined.  Each of these spaces has their own concept of distance (generalized p-norm) as well as its own concept of 'center' which is called a moment.

The p-norm is notated as ||x|_p and is defined for any p greater or equal to one.  You can quickly see that for p = 2 that the equation simplifies to the Euclidean distance equation.  There is a relation that higher order norms (higher p value) are smaller in magnitude than lower order norms for the same data sequence xi.  This is important to remember,  useful in many situations and summarized by the following equation:

The generalized mean equation (also called the power mean) is shown next.  If the target vector x is composed by subtracting a measure of central tendency (mean, median, mode, etc) it becomes a generalized moment equation  (more on this in Part 2).  If you set p to 1, the generalized mean becomes the familiar averaging function, if p is allowed to approach 0, the equation becomes the geometric mean. (I am still working on carrying out this simplification) and if p=-1, then the equation becomes the harmonic mean (for the EE's think of resistors in parallel).  The first four moments, which correspond to p = 1, 2, 3 and 4, are the arithmetic mean, standard deviation, asymmetry (skewness) and sharpness (kurtosis).

With this setup we are ready to go into Part 2 where I'll discuss fractional norms and fractional moments.

Deviation

Ever wonder why the standard deviation contains the squared and square root terms? Why is it like that? What makes it so standard? Well it turns out that there are some alternative deviation metrics such as the mean absolute deviation. This deviation metric takes the average of the absolute deviation of a vector (or random variable). This target vector could be a difference vector of the vector of interest and some measure of central tendency. It turns out the mean minimizes the standard deviation whereas the median minimizes the mean absolute deviation.

The paper "Revisiting a 90-year-old debate: the advantages of the mean deviation" by Stephen Gorard of the University of York is excellent argument for the proper use of the mean absolute deviation. He discusses the historical reasons for the dominance of the standard deviation, noting that

The standard deviation, by squaring the values concerned, gives us a distorted view of the amount of dispersion in our figures. The act of squaring makes each unit of distance from the mean exponentially (rather than additively) greater, and the act of square-rooting the sum of squares does not completely eliminate this bias.

He uses this point to show that the standard deviation is more sensitive to noise in the data than the mean absolute deviation and claims that the mean absolute deviation is better suited to all distribution other than the normal distribution. Finally he concludes that the mean absolute deviation has a simpler intuitive interpretation and thus more approachable for students.

So what properties must a metric have to be called a "deviation"? What other alternatives are available for our analysis?

Robust Causality Characterization via Generalized Dispersion Relations

P. Triverio, S. Grivet-Talocia, "Robust Causality Characterization via Generalized Dispersion Relations," IEEE Transactions on Advanced Packaging, VOL. 32, NO. 3, pp. 579-593, August 2008

This extremely well written and organized paper treats the causality of S-parameter data as throughly as any up to this time. He proposes a generalized Hilbert transform, i.e. extending the traditional Hilbert transform by including Lagrange polynomial to minimize the truncation and discretization error of the discrete frequency S-parameter data. He not only discusses this new approach but also bounds the error so that you know exactly the bounds of your assumptions. Given the needed time, I would like to implement his algorithms.

Wavefront Error

Just read a cool article on a subject that I didn't know exist and I bet it will come in handy someday.

IEEE Spectrum Magazine, March 2010, pages 46-53

Wavefront Error of a telescope: Aberrations in the curvature of a lens or mirror can cause telescopes in space and on the ground to suffer from blurry vision.

The guys at JPL have a new way of fixing blurry images.

Hartman screen test: 1904

Shack-Hartmann wavefront sensor: 1960

Gerchberg-Saxton algorithm: 2000s

It sounds like an adaptive telescope optical transfer function identifier. They create non-rigid telescope lenses which they purposely distort to correct for the optical distortion of atmosphere. Can create better images on earth with this approach than Hubble!

They claim that LASIK eye procedures use a form of wavefront distortion sensors to figure out how your eye is deformed!