graphs http://people.csail.mit.edu/jaffer/CNS/PSFCDR

The Performance of Space-Filling Curves for Dimension Reduction


Motivation

Color Space Dimension Reduction explores methods of dimension reduction, focusing on space-filling curves. For the purpose of presenting colors for selection, the space-filling curve attributed to Hilbert seems to perform better than the curve due to Peano. Can that difference be quantified?

The goal of dimension reduction is to find a mapping from a higher-dimensional space to a lower-dimensional space where points which are close in the higher-dimensional space map to points which are close in the other space.

Apparatus

Procedure

Method

Measurements

Analysis

The Z-curve has the widest spread and is particularly poor in 2-dimensions (the top plot). Worse still is that most unit length scalar edges map to coordinates which are more than one unit separated. Thus the average displacement for unit edges averages above 1.6 for 2-dimensions and above 1.35 for the other ranks.

The ratios for all three functions quickly approach their low, asymptotic values as the rank is increased. For the Peano and Hilbert curves the traces for ranks 6 and 9 are coincident.

The space-filling curve attributed to Peano maps scalar unit lengths to unit Euclidean lengths, giving optimal behavior for the shortest length. In fact all horizontal segments are exactly unit length. The vertical segments run 2 and 5 units; raising the averages in that range.

The space-filling curve attributed to Hilbert edges out the Peano curve to have the best performance of those measured. Color-Space Dimension Reduction also finds the Hilbert curve (slightly) better than Peano's. And [Bongki 2001] rates it best as well.

Logarithmic Measurements

Plotting the (logarithm of) average Euclidean-distance versus the (logarithm of) scalar-distance out to longer distances seems to indicate that the roughness of the high rank curves does not become smooth asymptotically.

Copyright © 2005, 2009 Aubrey Jaffer

I am a guest and not a member of the MIT Computer Science and Artificial Intelligence Laboratory.  My actions and comments do not reflect in any way on MIT.
Computer Natural Science
agj @ alum.mit.edu
Go Figure!