Norming Sets for Tensor and Polynomial Sketching
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913878351282176 |
|---|---|
| author | Zhang, Yifan Kileel, Joe |
| author_facet | Zhang, Yifan Kileel, Joe |
| contents | This paper develops the sketching (i.e., randomized dimension reduction) theory for real algebraic varieties and images of polynomial maps, including, e.g., the set of low rank tensors and tensor networks. Through the lens of norming sets, we provide a framework for controlling the sketching dimension for \textit{any} sketch operator used to embed said sets, including sub-Gaussian, fast Johnson-Lindenstrauss, and tensor structured sketch operators. Leveraging norming set theory, we propose a new sketching method called the median sketch. It embeds such a set $V$ using only $\widetilde{\mathcal{O}}(\dim V)$ tensor structured or sparse linear measurements. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_05174 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Norming Sets for Tensor and Polynomial Sketching Zhang, Yifan Kileel, Joe Numerical Analysis Information Theory Algebraic Geometry This paper develops the sketching (i.e., randomized dimension reduction) theory for real algebraic varieties and images of polynomial maps, including, e.g., the set of low rank tensors and tensor networks. Through the lens of norming sets, we provide a framework for controlling the sketching dimension for \textit{any} sketch operator used to embed said sets, including sub-Gaussian, fast Johnson-Lindenstrauss, and tensor structured sketch operators. Leveraging norming set theory, we propose a new sketching method called the median sketch. It embeds such a set $V$ using only $\widetilde{\mathcal{O}}(\dim V)$ tensor structured or sparse linear measurements. |
| title | Norming Sets for Tensor and Polynomial Sketching |
| topic | Numerical Analysis Information Theory Algebraic Geometry |
| url | https://arxiv.org/abs/2506.05174 |