mlsanityData to 14 Oct 2026

A General Algorithm for Solving Rank-one Matrix Sensing

arXiv 2303.12298 ↗First posted 22 Mar 2023cs.DS cs.LGcited by 15

Not on the map. Why?

Abstract (arXiv)

Matrix sensing has many real-world applications in science and engineering, such as system control, distance embedding, and computer vision. The goal of matrix sensing is to recover a matrix A_star ∈ ℝn × n, based on a sequence of measurements (ui,bi) ∈ ℝn × ℝ such that ui^top A_star ui = bi. Previous work [ZJD15] focused on the scenario where matrix Astar has a small rank, e.g. rank-k. Their analysis heavily relies on the RIP assumption, making it unclear how to generalize to high-rank matrices. In this paper, we relax that rank-k assumption and solve a much more general matrix sensing problem. Given an accuracy parameter δ ∈ (0,1), we can compute A ∈ ℝn × n in widetildeO(m3/2 n2 δ-1 ), such that |ui^top A ui - bi| ≤ δ for all i ∈ [m]. We design an efficient algorithm with provable convergence guarantees using stochastic gradient descent for this problem.

Key facts. Cited by 15 papers in the map (data through 14 Oct 2026). Builds on 19 of its 51 references that are in the map. First posted on arXiv 22 Mar 2023.

Builds on

19 of 51 references.

References · 19

  1. 2018Solving Linear Programs in the Current Matrix Multiplication Timecited by 100
  2. 2015Low-rank Solutions of Linear Matrix Equations via Procrustes Flowcited by 97
  3. 2021Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Timecited by 62
  4. 2020An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applicationscited by 57
  5. 2019Solving Empirical Risk Minimization in the Current Matrix Multiplication Timecited by 53
  6. 2020A Faster Interior Point Method for Semidefinite Programmingcited by 53
  7. 2015A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimizationcited by 50
  8. 2020Faster Dynamic Matrix Inverse for Faster LPscited by 44
  9. 2019A Deterministic Linear Program Solver in Current Matrix Multiplication Timecited by 42
  10. 2022A Faster Small Treewidth SDP Solvercited by 36
  11. 2021Solving SDP Faster: A Robust IPM Framework and Efficient Implementationcited by 33
  12. 2021Does Preprocessing Help Training Over-parameterized Neural Networks?cited by 32
7 more
  1. 2020A Nearly-Linear Time Algorithm for Linear Programs with Small Treewidth: A Multiscale Representation of Robust Central Pathcited by 29
  2. 2022Training Overparametrized Neural Networks in Sublinear Timecited by 22
  3. 2016A Unified Computational and Statistical Framework for Nonconvex Low-Rank Matrix Estimationcited by 21
  4. 2020Solving Tall Dense Linear Programs in Nearly Linear Timecited by 21
  5. 2013ROP: Matrix recovery via rank-one projectionscited by 18
  6. 2015Efficient Inverse Maintenance and Faster Algorithms for Linear Programmingcited by 13
  7. 2018Nonconvex Matrix Factorization from Rank-One Measurementscited by 13

Built on by

Cited by year

Citing papers per year: 2023: 13; 2024: 0; 2025: 2.

15 papers.

Sort:

  1. 2023Attention Scheme Inspired Softmax Regressioncited by 49
  2. 2023A Fast Optimization View: Reformulating Single Layer Attention in LLM Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Timecited by 30
  3. 2023Solving Attention Kernel Regression Problem via Pre-conditionercited by 20
  4. 2023A Unified Scheme of ResNet and Softmaxcited by 12
  5. 2023Toward Highly Efficient and Private Submodular Maximization via Matrix-Based Accelerationcited by 11
  6. 2023Efficient SGD Neural Network Training via Sublinear Activated Neuron Identificationcited by 11
  7. 2023Federated Empirical Risk Minimization via Second-Order Methodcited by 9
  8. 2023Faster Robust Tensor Power Method for Arbitrary Ordercited by 8
  9. 2023Is Solving Graph Neural Tangent Kernel Equivalent to Training Graph Neural Network?cited by 8
  10. 2023Fast and Efficient Matching Algorithm with Deadline Instancescited by 7
  11. 2023The Expressibility of Polynomial based Attention Schemecited by 7
  12. 2025When Can We Solve the Weighted Low Rank Approximation Problem in Truly Subquadratic Time?cited by 3
3 more
  1. 2025Towards Sampling Data Structures for Tensor Products in Turnstile Streamscited by 1
  2. 2023Online Adaptive Mahalanobis Distance Estimationcited by 0
  3. 2023Fast Heavy Inner Product Identification Between Weights and Inputs in Neural Network Trainingcited by 0