Universality laws for randomized dimension reduction, with applications

作     者：Oymak, Samet Tropp, Joel A. 

作者机构：Simons Inst Theory Comp Melvin Calvin Lab Berkeley CA 94720 USA CALTECH Comp & Math Sci 1200 E Calif BlvdMC 305-16 Pasadena CA 91125 USA 

出 版 物：《INFORMATION AND INFERENCE-A JOURNAL OF THE IMA》 (信息和推理)

年 卷 期：2018年第7卷第3期

页      面：337-446页

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

基　　金：NSF [CCF-1217058] ONR Award [N00014-11-1002] Gordon & Betty Moore Foundation Simons Institute for the Theory of Computing 

主　　题：conic geometry convex geometry dimension reduction invariance principle limit theorem random code random matrix randomized numerical linear algebra signal reconstruction statistical estimation stochastic geometry universality 

摘      要：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 article 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 minimum RSV. 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.