Dimension reduction is the process of embedding high-dimensional data into a
lower dimensional space to facilitate its analysis. In the Euclidean setting,
one fundamental technique for dimension reduction is to apply a random linear
map to the data. This dimension reduction procedure succeeds when it preserves
certain geometric features of the set.
The question is how large the embedding dimension must be to ensure that
randomized dimension reduction succeeds with high probability.
This paper studies a natural family of randomized dimension reduction maps
and a large class of data sets. It proves that there is a phase transition in
the success probability of the dimension reduction map as the embedding
dimension increases. For a given data set, the location of the phase transition
is the same for all maps in this family. Furthermore, each map has the same
stability properties, as quantified through the restricted minimum singular
value. These results can be viewed as new universality laws in high-dimensional
stochastic geometry.
Universality laws for randomized dimension reduction have many applications
in applied mathematics, signal processing, and statistics. They yield design
principles for numerical linear algebra algorithms, for compressed sensing
measurement ensembles, and for random linear codes. Furthermore, these results
have implications for the performance of statistical estimation methods under a
large class of random experimental designs.

该论文研究了一类随机降维映射及其在高维随机几何学中的新普适性，证明在特定数据集上降维成功的概率存在相变现象，从而为数值线性代数算法、压缩感知、随机线性编码等提供了设计原则，并在随机实验设计下为统计估计方法的性能提供了启示。