FAST AND MEMORY-OPTIMAL DIMENSION REDUCTION USING KAC'S WALK

• 成果类型: Article
• 署名作者: Jain, Vishesh; Pillai, Natesh S.; Sah, Ashwin; Sawhney, Mehtaab; Smith, Aaron
• 署名单位: Stanford University; Harvard University; Massachusetts Institute of Technology (MIT); University of Ottawa
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/22-AAP1784
• 发表日期: 2022
• 页码: 4038-4064
• 关键词: restricted isometry property; johnson-lindenstrauss; random projections; reconstruction; fourier; PROOF

摘要

In this work, we analyze dimension reduction algorithms based on the Kac walk and discrete variants. (1) For n points in R-d, we design an optimal Johnson-Lindenstrauss (JL) transform based on the Kac walk which can be applied to any vector in time O(d log d) for essentially the same restriction on n as in the best-known transforms due to Ailon and Liberty, and Bamberger and Krahmer. Our algorithm is memory-optimal, and outperforms existing algorithms in regimes when n is sufficiently large and the distortion parameter is sufficiently small. In particular, this confirms a conjecture of Ailon and Chazelle, and of Oliveira, in a stronger form. (2) The same construction gives a simple transform with optimal restricted isometry property (RIP) which can be applied in time O(d log d) for essentially the same range of sparsity as in the best-known such transform due to Ailon and Rauhut. (3) We show that by fixing the angle in the Kac walk to be pi/4 throughout, one obtains optimal JL and RIP transforms with almost the same running time, thereby confirming-up to a log log d factor-a conjecture of Avron, Maymounkov, and Toledo. Our moment-based analysis of this modification of the Kac walk may also be of independent interest in connection with repeated averaging processes.