Abstract: Approximate nearest neighbor (ANN) search is a key component in many modern machine learning pipelines; recent use cases include vector databases and retrieval-augmented generation (RAG). We show that high-dimensional ANN search can be performed efficiently by a simple algorithm that combines two elementary machine learning techniques: low-rank matrix factorization and $k$-means clustering. The key idea of the proposed algorithm, called Low-Rank Matrix Factorization for Approximate Nearest Neighbor Search (LoRANN), is that since inner product computation is a multivariate regression problem for which the ordinary least squares (OLS) estimate gives an exact solution, we can approximate the OLS solution by reduced-rank regression. We also introduce a quantized 8-bit version of LoRANN that has a small memory footprint and is particularly efficient for high-dimensional data. The CPU-only version of LoRANN outperforms the leading product quantization-based ANN algorithms, and has faster query times than the leading graph-based ANN library at recall levels under 90% on most of the data sets in our experiments. The GPU implementation of LoRANN outperforms the current state-of-the-art on high-dimensional data sets.