Norming Sets for Tensor and Polynomial Sketching
Journal:
arXiv
Published Date:
Jun 5, 2025
Abstract
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.
