Mic Talks
Next Talk: Dr. Piyush Sao
August 27, 2026
Exact Limits of Random Projections for Preserving Geometry: Distance Recovery, Nearest-Neighbor Rankings, and Covariance Shape in Gaussian Models
Presented by: Dr. Piyush Sao
ORNL
Hosted by:
Mathematics in Computation Talk Series
Building 5700, Room L204
Thursday | August 27, 2026 | 3:00 – 4:00 p.m.
Abstract: The random-projection guarantee and what it leaves unsaid. The Johnson–Lindenstrauss (JL) lemma is a cornerstone of high-dimensional dimensionality reduction, ensuring that rank-m linear projections preserve pairwise distances within tight relative error bounds. However, in modern high-dimensional statistics, critical geometric decisions – such as nearest-neighbor ordering, statistical inference, and detecting covariance anisotropy – depend on centered fluctuations that are substantially smaller than the baseline distance itself. Standard JL guarantees maintain relative accuracy but say nothing about these local fluctuations, so algorithms that rely on fine structure can fail unexpectedly even when classical JL bounds are satisfied. This talk asks: how much of this fine-grained geometric structure actually survives low-rank linear sketching?
Decomposing Distance Variance, Ranking Failure, and Spectral Contraction. This talk analyzes rank-$m$ linear projections of $d$-dimensional data across both isotropic and anisotropic regimes. For isotropic data, squared distances decompose into independent retained and discarded components, establishing an exact nonlinear recovery ceiling of $m/d$ for distance-feature variance (derived via Laguerre polynomial expansions). In anisotropic settings, distance recovery depends primarily on the squared-eigenvalue mass captured by top-$m$ directions; however, nonlinear features can exceed this linear share when projections retain eigenspaces unevenly. Furthermore, covariance-shape information contracts at rate $(m/d)^2$ – faster than the $m/d$ rate for mean and scale – reflecting a “sphericalization” effect toward isotropy. Strikingly, even when pairwise distances meet standard JL tolerances, low-dimensional projections rank distances no better than chance when $\log n <<m << d$, and fixed-candidate nearest-neighbor overlaps degrade to random chance as $m/d \to 0$.
Implications for High-Dimensional Algorithm Design. These results establish that preserving relative distances is insufficient to preserve local structure. By defining explicit recovery ceilings and contraction rates, the findings demonstrate that tasks such as ranking data and inferring shape require mechanisms beyond a single oblivious projection, including reranking, metric correction, or multiple independent sketches. For general linear maps, three spectral summaries govern these downstream tasks: rank controls optimal nonlinear inference, spectral spread governs uncorrected norm estimation, and small singular values determine stability under additive noise. Together, these principles expose the limits of random projections and guide the design of sketching operators tailored to target applications.
Speaker’s Bio:
Dr. Piyush K. Sao is a Research Scientist in the Computer Science and Mathematics Division at Oak Ridge National Laboratory, where he develops scalable numerical and combinatorial algorithms for high-performance computing platforms. His research spans theoretically optimal, energy-efficient, and fault-tolerant algorithms for sparse and dense linear algebra, graph analytics, and discrete algorithms; his recent work establishes information-theoretic limits of mixed-precision computation, fixed-point emulation, and randomized algorithms for scientific computing and machine learning. Algorithms he co-developed have been incorporated into widely used libraries, including SuperLU DIST and ArborX. He received the 2022 Best Paper Prize of the Society for Industrial and Applied Mathematics Activity Group on Supercomputing, and his work on large-scale knowledge-graph analytics was an Association for Computing Machinery Gordon Bell Prize finalist at SC20 and SC22. He has served on the program committees of the Supercomputing Conference and International Parallel and Distributed Processing Symposium since 2019. He received his Ph.D. in Computational Science and Engineering from Georgia Tech and an undergraduate degree in Electrical Engineering from the Institute of Technology, Madras.
Host:
Elaine Wong, [email protected], 865-341-2325
About the Mathematics in Computation (MiC) Talk Series:
MiC talks are held every Thursday from 3:00 – 4:00 p.m. Eastern Time and are open to the public.
To subscribe to the MiC Talks mailing list, please contact Celeste Mudrich at[email protected].
To see the full list of previous and upcoming seminars, go to https://events.ornl.gov/mictalks/.
The MiC Talks series is a venue for the state of the art in mathematics in computation. The series also fosters collaboration, inspires new research directions, and showcases advances in the use of mathematics and computation in the service of science and engineering.
If you are interested in giving a talk, please contact a member of the MiC Seminar committee.
Elaine Wong, [email protected], 865-341-2325
Pablo Seleson, [email protected], 865-323-2859
Pablo Mariano, [email protected], 865-341-2768
Viktor Reshniak, [email protected], 865-341-4394
Microsoft Teams meeting
Join: https://teams.microsoft.com/meet/249940092818935?p=f6Brf5LOpIVEeA5cbK
Sponsored by Computer Mathematics Division (CSMD)