Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2512.23756 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917174974611456 |
|---|---|
| author | Mackenzie, Pierre |
| author_facet | Mackenzie, Pierre |
| contents | The Johnson-Lindenstrauss (JL) theorem states that a set of points in high-dimensional space can be embedded into a lower-dimensional space while approximately preserving pairwise distances with high probability Johnson and Lindenstrauss (1984). The standard JL theorem uses dense random matrices with Gaussian entries. However, for some applications, sparse random matrices are preferred as they allow for faster matrix-vector multiplication. I outline the constructions and proofs introduced by Achlioptas (2003) and the contemporary standard by Kane and Nelson (2014). Further, I implement and empirically compare these sparse constructions with standard Gaussian JL matrices. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_23756 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Sparse Random Matrices for Dimensionality Reduction Mackenzie, Pierre Data Structures and Algorithms The Johnson-Lindenstrauss (JL) theorem states that a set of points in high-dimensional space can be embedded into a lower-dimensional space while approximately preserving pairwise distances with high probability Johnson and Lindenstrauss (1984). The standard JL theorem uses dense random matrices with Gaussian entries. However, for some applications, sparse random matrices are preferred as they allow for faster matrix-vector multiplication. I outline the constructions and proofs introduced by Achlioptas (2003) and the contemporary standard by Kane and Nelson (2014). Further, I implement and empirically compare these sparse constructions with standard Gaussian JL matrices. |
| title | Sparse Random Matrices for Dimensionality Reduction |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2512.23756 |