Subspace embeddings with the rerandomized SRHT

DOI10.48550/arXiv.2609.13946MaRDI QIDQ7345572zbMATH OpenarXivFDO

Authors Yuning Yang

Publication date 12 September 2026

Published in arXiv

Tldr We study subspace embeddings using normalized real Walsh transforms, independent sign diagonals, and uniform coordinate sampling without replacement; we show that $k=\min\{n,\lceil Cr/\varepsilon^2\rceil\}$ suffices to preserve all squared norms on each fixed r-dimensional subspace within $1\pm\varepsilon$ with probability at least 0.99 for a universal constant C and every ambient Walsh dimension and rank, answering Problem TR-01 in the Open Problems in Numerical Linear Algebra repository

Full work available at URL https://doi.org/10.48550/arXiv.2609.13946

arXiv classification

math.NA

Cites work

• Compatible circuit decompositions of 4‐regular graphs
• Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
• Fluctuation moments induced by conjugation with asymptotically liberating random matrix ensembles
• Generic MANOVA limit theorems for products of projections
• Improved analysis of the subsampled randomized Hadamard transform
• Improved matrix algorithms via the subsampled randomized Hadamard transform
• Linear Systems and Eigenvalue Problems: Open Questions from a Simons Workshop
• Lower bounds for oblivious subspace embeddings
• On a Method of Calculation of Semi-Invariants
• Optimal Embedding Dimension for Sparse Subspace Embeddings
• Sharp bounds for sums associated to graphs of matrices
• Traffic distributions and independence: permutation invariant random matrices and the three notions of independence
• Two Subspaces

This page was built for publication: Subspace embeddings with the rerandomized SRHT

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7345572)