Norming Sets for Tensor and Polynomial Sketching
By: Yifan Zhang, Joe Kileel
Potential Business Impact:
Makes complex math shapes easier for computers.
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.
Similar Papers
Polynomial meshes on algebraic sets
Numerical Analysis
Helps computers guess math problems better.
Tensor Sketch: Fast and Scalable Polynomial Kernel Approximation
Data Structures and Algorithms
Speeds up computer learning with complex math.
Variational analysis of determinantal varieties
Optimization and Control
Makes computers better at finding simple patterns.