The Nelson-Nguyen Conjecture via Mean-to-Moments Concentration
En palabras de los autores
An oblivious subspace embedding (OSE) is a distribution over matrices that approximately preserves the squared Euclidean norm of every vector in any fixed low-dimensional subspace. We prove the Nelson-Nguyen conjecture: for every , there exists a distribution that gives an OSE with embedding dimension and column sparsity , with failure probability at most . We first bound the mean spectral error using a trace-moment argument and then upgrade this bound to the desired high-probability guarantee using concentration and resampling. ChatGPT-5.6-Pro was used in proving and writing the results of this manuscript.
Resultado principalEl resumen no menciona limitaciones.
Apareció: martes, 22 de septiembre. arXiv. Preprint, todavía sin revisión por pares.