# When Can We Solve the Weighted Low Rank Approximation Problem in Truly Subquadratic Time?

arXiv: https://arxiv.org/abs/2502.16912 · HTML: https://mlsanity.com/paper/2502.16912/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 65 of its 114 references that are in the map.
- First posted on arXiv 24 Feb 2025.

## Builds on (most cited first, 30 of 65)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [MInference 1.0: Accelerating Pre-filling for Long-Context LLMs via Dynamic Sparse Attention](https://mlsanity.com/paper/2407.02490/) (2024)
- [Language model compression with weighted low-rank factorization](https://mlsanity.com/paper/2207.00112/) (2022)
- [Flex Attention: A Programming Model for Generating Optimized Attention Kernels](https://mlsanity.com/paper/2412.05496/) (2024)
- [Fast Attention Requires Bounded Entries](https://mlsanity.com/paper/2302.13214/) (2023)
- [Solving Linear Programs in the Current Matrix Multiplication Time](https://mlsanity.com/paper/1810.07896/) (2018)
- [Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Time](https://mlsanity.com/paper/2112.07628/) (2021)
- [Training (Overparametrized) Neural Networks in Near-Linear Time](https://mlsanity.com/paper/2006.11648/) (2020)
- [An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applications](https://mlsanity.com/paper/2004.04250/) (2020)
- [Solving Empirical Risk Minimization in the Current Matrix Multiplication Time](https://mlsanity.com/paper/1905.04447/) (2019)
- [Attention Scheme Inspired Softmax Regression](https://mlsanity.com/paper/2304.10411/) (2023)
- [Why Larger Language Models Do In-context Learning Differently?](https://mlsanity.com/paper/2405.19592/) (2024)
- [Faster Dynamic Matrix Inverse for Faster LPs](https://mlsanity.com/paper/2004.07470/) (2020)
- [Solving Regularized Exp, Cosh and Sinh Regression Problems](https://mlsanity.com/paper/2303.15725/) (2023)
- [How to Capture Higher-order Correlations? Generalizing Matrix Softmax Attention to Kronecker Computation](https://mlsanity.com/paper/2310.04064/) (2023)
- [A Deterministic Linear Program Solver in Current Matrix Multiplication Time](https://mlsanity.com/paper/1910.11957/) (2019)
- [Dropping Convexity for Faster Semi-definite Optimization](https://mlsanity.com/paper/1509.03917/) (2015)
- [On Statistical Rates and Provably Efficient Criteria of Latent Diffusion Transformers (DiTs)](https://mlsanity.com/paper/2407.01079/) (2024)
- [Do Large Language Models Have Compositional Ability? An Investigation into Limitations and Scalability](https://mlsanity.com/paper/2407.15720/) (2024)
- [Discovering the Gems in Early Layers: Accelerating Long-Context LLMs with 1000x Input Token Reduction](https://mlsanity.com/paper/2409.17422/) (2024)
- [Randomized and Deterministic Attention Sparsification Algorithms for Over-parameterized Feature Dimension](https://mlsanity.com/paper/2304.04397/) (2023)
- [A Faster Small Treewidth SDP Solver](https://mlsanity.com/paper/2211.06033/) (2022)
- [An Iterative Algorithm for Rescaled Hyperbolic Functions Regression](https://mlsanity.com/paper/2305.00660/) (2023)
- [Conv-Basis: A New Paradigm for Efficient Attention Inference and Gradient Computation in Transformers](https://mlsanity.com/paper/2405.05219/) (2024)
- [Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time](https://mlsanity.com/paper/2302.11068/) (2023)
- [Computational Limits of Low-Rank Adaptation (LoRA) Fine-Tuning for Transformer Models](https://mlsanity.com/paper/2406.03136/) (2024)
- [Training Tensor Attention Efficiently: From Cubic to Almost Linear Time](https://mlsanity.com/paper/2405.16411/) (2024)
- [Bypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessing](https://mlsanity.com/paper/2211.14227/) (2022)
- [Faster Algorithm for Structured John Ellipsoid Computation](https://mlsanity.com/paper/2211.14407/) (2022)
- [Sketching for First Order Method: Efficient Algorithm for Low-Bandwidth Channel and Vulnerability](https://mlsanity.com/paper/2210.08371/) (2022)

## Built on by (most cited first, 3 of 3)

- [Theoretical Guarantees for High Order Trajectory Refinement in Generative Flows](https://mlsanity.com/paper/2503.09069/) (2025)
- [Only Large Weights (And Not Skip Connections) Can Prevent the Perils of Rank Collapse](https://mlsanity.com/paper/2505.16284/) (2025)
- [Scaling Law Phenomena Across Regression Paradigms: Multiple and Kernel Approaches](https://mlsanity.com/paper/2503.01314/) (2025)

## Abstract (arXiv)

The weighted low-rank approximation problem is a fundamental numerical linear algebra problem and has many applications in machine learning. Given a n × n weight matrix W and a n × n matrix A, the goal is to find two low-rank matrices U, V ∈ ℝn × k such that the cost of | W circ (U V^top - A) |F2 is minimized. Previous work has to pay Omega(n2) time when matrices A and W are dense, e.g., having Omega(n2) non-zero entries. In this work, we show that there is a certain regime, even if A and W are dense, we can still hope to solve the weighted low-rank approximation problem in almost linear n1+o(1) time.