When Can We Solve the Weighted Low Rank Approximation Problem in Truly Subquadratic Time?
Not on the map. Why?
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.
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
65 of 114 references.
References · 65
- 2017Attention Is All You Needcited by 60,361
- 2024MInference 1.0: Accelerating Pre-filling for Long-Context LLMs via Dynamic Sparse Attentioncited by 383
- 2022Language model compression with weighted low-rank factorizationcited by 195
- 2024Flex Attention: A Programming Model for Generating Optimized Attention Kernelscited by 185
- 2023Fast Attention Requires Bounded Entriescited by 102
- 2018Solving Linear Programs in the Current Matrix Multiplication Timecited by 100
- 2021Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Timecited by 62
- 2020Training (Overparametrized) Neural Networks in Near-Linear Timecited by 58
- 2020An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applicationscited by 57
- 2019Solving Empirical Risk Minimization in the Current Matrix Multiplication Timecited by 53
- 2023Attention Scheme Inspired Softmax Regressioncited by 49
- 2024Why Larger Language Models Do In-context Learning Differently?cited by 45
38 more
- 2020Faster Dynamic Matrix Inverse for Faster LPscited by 44
- 2023Solving Regularized Exp, Cosh and Sinh Regression Problemscited by 44
- 2023How to Capture Higher-order Correlations? Generalizing Matrix Softmax Attention to Kronecker Computationcited by 44
- 2019A Deterministic Linear Program Solver in Current Matrix Multiplication Timecited by 42
- 2015Dropping Convexity for Faster Semi-definite Optimizationcited by 40
- 2024On Statistical Rates and Provably Efficient Criteria of Latent Diffusion Transformers (DiTs)cited by 40
- 2024Do Large Language Models Have Compositional Ability? An Investigation into Limitations and Scalabilitycited by 40
- 2024Discovering the Gems in Early Layers: Accelerating Long-Context LLMs with 1000x Input Token Reductioncited by 39
- 2023Randomized and Deterministic Attention Sparsification Algorithms for Over-parameterized Feature Dimensioncited by 37
- 2022A Faster Small Treewidth SDP Solvercited by 36
- 2023An Iterative Algorithm for Rescaled Hyperbolic Functions Regressioncited by 35
- 2024Conv-Basis: A New Paradigm for Efficient Attention Inference and Gradient Computation in Transformerscited by 32
- 2023Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Timecited by 31
- 2024Computational Limits of Low-Rank Adaptation (LoRA) Fine-Tuning for Transformer Modelscited by 31
- 2024Training Tensor Attention Efficiently: From Cubic to Almost Linear Timecited by 30
- 2022Bypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessingcited by 29
- 2022Faster Algorithm for Structured John Ellipsoid Computationcited by 28
- 2022Sketching for First Order Method: Efficient Algorithm for Low-Bandwidth Channel and Vulnerabilitycited by 25
- 2019A near-optimal algorithm for approximating the John Ellipsoidcited by 23
- 2022Speeding Up Sparsification using Inner Product Search Data Structurescited by 22
- 2022Training Overparametrized Neural Networks in Sublinear Timecited by 22
- 2022A Sublinear Adversarial Training Algorithmcited by 22
- 2022Discrepancy Minimization in Input-Sparsity Timecited by 22
- 2024Fourier Circuits in Neural Networks and Transformers: A Case Study of Modular Arithmetic with Multiple Inputscited by 22
- 2024Multi-Layer Transformers Gradient Can be Approximated in Almost Linear Timecited by 22
- 2024Bypassing the Exponential Dependency: Looped Transformers Efficiently Learn In-context by Multi-step Gradient Descentcited by 22
- 2024Fundamental Limits of Prompt Tuning Transformers: Universality, Capacity and Efficiencycited by 22
- 2024On Statistical Rates of Conditional Diffusion Transformers: Approximation, Estimation and Minimax Optimalitycited by 22
- 2016Recovery guarantee of weighted low-rank approximation via alternating minimizationcited by 20
- 2024Beyond Linear Approximations: A Novel Pruning Approach for Attention Matrixcited by 20
- 2024A Tighter Complexity Analysis of SparseGPTcited by 19
- 2024HSR-Enhanced Sparse Attention Accelerationcited by 19
- 2023A General Algorithm for Solving Rank-one Matrix Sensingcited by 15
- 2024Exploring the Frontiers of Softmax: Provable Optimization, Applications in Diffusion Model, and Beyondcited by 15
- 2022Numerical Optimizations for Weighted Low-rank Estimation on Language Modelcited by 14
- 2022Adaptive and Dynamic Multi-Resolution Hashing for Pairwise Summationscited by 14
- 2025On Computational Limits and Provably Efficient Criteria of Visual Autoregressive Models: A Fine-Grained Complexity Analysiscited by 14
- 2024RoPE Attention Can Be Trained in Almost Linear Timecited by 13
50 most cited of 65 All 65 (JSON)
Built on by
Citing papers per year: 2025: 3.
3 papers.