On randomized sketching algorithms and the Tracy-Widom law.

ABSTRACT: There is an increasing body of work exploring the integration of random projection into algorithms for numerical linear algebra. The primary motivation is to reduce the overall computational cost of processing large datasets. A suitably chosen random projection can be used to embed the original dataset in a lower-dimensional space such that key properties of the original dataset are retained. These algorithms are often referred to as sketching algorithms, as the projected dataset can be used as a compressed representation of the full dataset. We show that random matrix theory, in particular the Tracy-Widom law, is useful for describing the operating characteristics of sketching algorithms in the tall-data regime when the sample size n is much greater than the number of variables

SUBMITTER: Ahfock D 

PROVIDER: S-EPMC9852177 | biostudies-literature | 2023

REPOSITORIES: biostudies-literature