Subspace embeddings with the rerandomized SRHT
This work studies subspace embeddings obtained by two normalized real Walsh transforms, two independent sign diagonals, and uniform coordinate sampling without replacement. The main result shows that the prescribed sample size $k=\min\{n,\lceil Cr/\varepsilon^2\rceil\}$, for a universal constant $C$, suffices to preserve all squared norms on each fixed $r$-dimensional subspace within $1\pm\varepsilon$ with probability at least $0.99$. The result holds for every ambient Walsh dimension and all ranks, and answers Problem TR-01 in the Open Problems in Numerical Linear Algebra repository. The…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.13946
curl -X POST /api/v1/records/arxiv/2609.13946/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.13946/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'