Fast and memory-optimal dimension reduction using Kac's walk

DOI10.1214/22-AAP1784MaRDI QIDQ2090615

Yanyan Li

Publication date: 31 October 2022

Published in: The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2003.10069

zbMATH Keywords

restricted isometry propertyJohnson-Lindenstrauss lemmaKac walk

Mathematics Subject Classification ID

Discrete-time Markov processes on general state spaces (60J05) Randomized algorithms (68W20)

Related Items (1)

Fast Metric Embedding into the Hamming Cube

Uses Software

• Blendenpik

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Kac's walk on \(n\)-sphere mixes in \(n\log n\) steps
• A simple proof of the restricted isometry property for random matrices
• Fast dimension reduction using Rademacher series on dual BCH codes
• Estimation of moments of sums of independent real random variables
• Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
• On the mixing time of Kac's walk and other high-dimensional Gibbs samplers with constraints
• Automorphisms of the extended affine root system and modular property for the flat theta invariants
• A phase transition for repeated averages
• On the convergence to equilibrium of Kac's random walk on matrices
• Fast and RIP-optimal transforms
• Tail bounds via generic chaining
• New and Improved Johnson–Lindenstrauss Embeddings via the Restricted Isometry Property
• Blendenpik: Supercharging LAPACK's Least-Squares Solver
• Sparser Johnson-Lindenstrauss Transforms
• Extensions of Lipschitz mappings into a Hilbert space
• On sparse reconstruction from Fourier and Gaussian measurements
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
• Generating a random permutation with random transpositions
• An elementary proof of a theorem of Johnson and Lindenstrauss
• The Fast Johnson–Lindenstrauss Transform and Approximate Nearest Neighbors
• The Restricted Isometry Property of Subsampled Fourier Matrices
• Compressed sensing

This page was built for publication: Fast and memory-optimal dimension reduction using Kac's walk