A Caltech Library Service

Universality laws for randomized dimension reduction, with applications

Oymak, Samet and Tropp, Joel A. (2015) Universality laws for randomized dimension reduction, with applications. . (Unpublished)

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription Paper
Tropp, Joel A.0000-0003-1024-1791
Additional Information:Date: 30 November 2015. Revised 7 August 2017 and 5 September 2017 and 14 September 2017. The authors would like to thank David Donoho, Surya Ganguli, Babak Hassibi, Michael McCoy, Andreas Maurer, Andrea Montanari, Ivan Nourdin, Giovanni Peccati, Adrian Röllin, Jared Tanner, Christos Thrampoulidis, and Madeleine Udell for helpful conversations. We also thank the anonymous reviewers and the editors for their careful reading and suggestions. SO was generously supported by the Simons Institute for the Theory of Computing and NSF award CCF-1217058. JAT gratefully acknowledges support from ONR award N00014-11-1002 and the Gordon & Betty Moore Foundation.
Funding AgencyGrant Number
Office of Naval Research (ONR)N00014-11-1002
Gordon and Betty Moore FoundationUNSPECIFIED
Subject Keywords: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
Classification Code:2010 Mathematics Subject Classification. Primary: 60D05, 60F17. Secondary: 60B20.
Record Number:CaltechAUTHORS:20180831-112137332
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:89338
Deposited By: George Porter
Deposited On:04 Sep 2018 14:49
Last Modified:03 Oct 2019 20:15

Repository Staff Only: item control page