Universality laws for randomized dimension reduction, with applications
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.
Code (0)
등록된 구현이 없습니다.
Tasks
compressed sensingDimensionality ReductionSimilar Papers 제목 키워드 기반
Theory of Dual-sparse Regularized Randomized Reduction
In this paper, we study randomized reduction methods, which reduce high-dimensional features into low-dimensional space by randomized methods (e.g., random projection, random hashing), for large-scale high-dimensional cl…
General ClassificationOn relative universality, regression operator, and conditional independence
The notion of relative universality with respect to a {\sigma}-field was introduced to establish the unbiasedness and Fisher consistency of an estimator in nonlinear sufficient dimension reduction. However, there is a ga…
Causal InferenceDimensionality ReductionregressionvalidRandomized Dimension Reduction on Massive Data
Scalability of statistical estimators is of increasing importance in modern applications and dimension reduction is often used to extract relevant information from data. A variety of popular dimension reduction approache…
Dimensionality ReductionregressionNeural Scaling Universality: If Exponents Are Fixed, Time to Understand Coefficients
Neural scaling laws describe how pre-training loss decays as power laws with training time, model size, and compute. This position paper argues that the exponents of these power laws are fixed by generic mechanisms: a on…
Adaptive Randomized Dimension Reduction on Massive Data
The scalability of statistical estimators is of increasing importance in modern applications. One approach to implementing scalable algorithms is to compress data into a low dimensional latent space using dimension reduc…
Dimensionality Reductionparameter estimation