What is meant by "scale" in the 2008 t-SNE paper?

Question

I am trying to understand the use of the term “scale” in the 2008 van der Maaten and Hinton t-sne paper.

I’m not sure I exactly understand what they mean by their use of the term “scale”, for example - when they say the t-sne map

reveals structure at many different scales.

Is this term used in the same sense when they also talk about the crowding problem and discuss data in 2D that may be linear on a small scale, but are embedded in a higher D space?

Does “scales” have the same meaning in this sentence?

The volume of a sphere centered on datapoint $i$ scales as $r^m$, where $r$ is the radius and $m$ the dimensionality of the sphere.

I’m a psychometrician by training and I’m wondering if what I think of as scale may not correspond to what computer scientists mean by scale.

Answer 1

Different scales in this case is referring to different orders of magnitude. During dimensionality reduction, t-SNE tries to conserves structure you would see looking at the data on a high level, but at the same time tries to keep structures that only appear if you would "zoom in". Consider for example two clusters of points in 3D space: When reducing to 2D, t-SNE would keep the circle structure of the elements in the second cluster, while separating the two main clusters as well. This is a trivial example but the same would be true in higher dimensionality and much bigger differences of size between different structures.

The second meaning is different. Here it means "how fast does it grow", in reference to big O notation:

Big O notation characterizes functions according to their growth rates: different functions with the same growth rate may be represented using the same O notation.