Fetching the paper…
Reading the bibliography…
Given a matrix $M\in \mathbb{R}^{m\times n}$, the low rank matrix completion problem asks us to find a rank-$k$ approximation of $M$ as $UV^\top$ for $U\in \mathbb{R}^{m\times k}$ and $V\in \mathbb{R}^{n\times k}$ by only observing a few entries specified by a set of entries $\Omega\subseteq [m]\times [n]$.
Das asymptotische verteilungsgesetz der eigenwerte linearer partieller differentialgleichungen (mit einer anwendung auf die theorie der hohlraumstrahlung)
H. Weyl · 1912
Earlier work this paper cites.
Perturbation theory for pseudo-inverses
Per-Åke Wedin · 1973
Earlier work this paper cites.
A method for solving the convex programming problem with convergence rate O ( 1 k 2 ) {O}(\frac{1}{k^{2}})
Yu E Nesterov · 1983
Earlier work this paper cites.
Matrix completion problems: a survey
Charles R Johnson · 1990
Earlier work this paper cites.
The geometry of graphs and some of its algorithmic applications
N. Linial, E. London, and Y. Rabinovich · 1994
Earlier work this paper cites.
Fast maximum margin matrix factorization for collaborative prediction
Jasson D. M. Rennie and Nathan Srebro · 2005
Earlier work this paper cites.
Theory of semidefinite programming for sensor network localization
Anthony Man-Cho So and Yinyu Ye · 2005
Earlier work this paper cites.
Matrix factorization techniques for recommender systems
Yehuda Koren, Robert Bell, and Chris Volinsky · 2009
Earlier work this paper cites.
Matrix completion from a few entries
Raghunandan H. Keshavan, Sewoong Oh, and Andrea Montanari · 2009
Earlier work this paper cites.
The bellkor solution to the netflix grand prize
Yehuda Koren · 2009
Earlier work this paper cites.
Blendenpik: Supercharging lapack’s least-squares solver
Haim Avron, Petar Maymounkov, and Sivan Toledo · 2010
Earlier work this paper cites.
The power of convex relaxation: Near-optimal matrix completion
Emmanuel J. Candès and Terence Tao · 2010
Earlier work this paper cites.
The optimal perturbation bounds of the moore–penrose inverse under the frobenius norm
Lingsheng Meng and Bing Zheng · 2010
Earlier work this paper cites.
Robust principal component analysis?
Emmanuel J. Candès, Xiaodong Li, Yi Ma, and John Wright · 2011
Earlier work this paper cites.
Can matrix coherence be efficiently and accurately estimated?
Mehryar Mohri and Ameet Talwalkar · 2011
Earlier work this paper cites.
A simpler approach to matrix completion
Benjamin Recht · 2011
Earlier work this paper cites.
Graph sparsification by effective resistances
Daniel A Spielman and Nikhil Srivastava · 2011
Earlier work this paper cites.
Improved analysis of the subsampled randomized hadamard transform
Joel A. Tropp · 2011
Earlier work this paper cites.
Exact matrix completion via convex optimization
Emmanuel Candès and Benjamin Recht · 2012
Earlier work this paper cites.
On traffic matrix completion in the internet
Gonca Gürsun and Mark Crovella · 2012
Earlier work this paper cites.
Sampling methods for the nystrom method
Sanjiv Kumar, Mehryar Mohri, and Ameet Talwalkar · 2012
Earlier work this paper cites.
Low-rank approximation and regression in input sparsity time
Kenneth L Clarkson and David P Woodruff · 2013
Earlier work this paper cites.
Noisy matrix completion using alternating minimization
Suriya Gunasekar, Ayan Acharya, Neeraj Gaur, and Joydeep Ghosh · 2013
Cited alongside, same era.
Low-rank matrix completion using alternating minimization
Prateek Jain, Praneeth Netrapalli, and Sujay Sanghavi · 2013
Cited alongside, same era.
Faster ridge regression via the subsampled randomized hadamard transform
Yichao Lu, Paramveer Dhillon, Dean P Foster, and Lyle Ungar · 2013
Cited alongside, same era.
Osnap: Faster numerical linear algebra algorithms via sparser subspace embeddings
Jelani Nelson and Huy L Nguyên · 2013
Cited alongside, same era.
Angles between subspaces and their tangents
Peizhen Zhu and Andrew V Knyazev · 2013
Cited alongside, same era.
Optimal cur matrix decompositions
Christos Boutsidis and David P Woodruff · 2014
Cited alongside, same era.
Low rank approximation with entrywise l1-norm error
Zhao Song, David P Woodruff, and Peilin Zhong · 2017
Later among the works it cites.
Sketching for kronecker product regression and p-splines
Huaian Diao, Zhao Song, Wen Sun, and David Woodruff · 2018
Later among the works it cites.
A near-optimal algorithm for approximating the john ellipsoid
Michael B Cohen, Ben Cousins, Yin Tat Lee, and Xin Yang · 2019
Later among the works it cites.
Optimal sketching for kronecker product regression and low rank approximation
Huaian Diao, Rajesh Jayaram, Zhao Song, Wen Sun, and David Woodruff · 2019
Later among the works it cites.
Solving empirical risk minimization in the current matrix multiplication time
Yin Tat Lee, Zhao Song, and Qiuyi Zhang · 2019
Later among the works it cites.
Low-rank matrix completion: A contemporary survey
Luong Trung Nguyen, Junhan Kim, and Byonghyo Shim · 2019
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Understanding alternating minimization for matrix completion
Moritz Hardt · 2014
Cited alongside, same era.
Computational limits for matrix completion
Moritz Hardt, Raghu Meka, Prasad Raghavendra, and Benjamin Weitz · 2014
Cited alongside, same era.
Fast matrix completion without the condition number
Moritz Hardt and Mary Wootters · 2014
Cited alongside, same era.
Lsrn: A parallel iterative solver for strongly over- or underdetermined systems
Xiangrui Meng, Michael A. Saunders, and Michael W. Mahoney · 2014
Cited alongside, same era.
Fast exact matrix completion with finite samples
Prateek Jain and Praneeth Netrapalli · 2015
Cited alongside, same era.
Randomized block krylov methods for stronger and faster approximate singular value decomposition
Cameron Musco and Christopher Musco · 2015
Cited alongside, same era.
Later among the works it cites.
Average case column subset selection for entrywise ℓ 1 \ell_{1} -norm loss
Zhao Song, David Woodruff, and Peilin Zhong · 2019
Later among the works it cites.
Towards a zero-one law for column subset selection
Zhao Song, David Woodruff, and Peilin Zhong · 2019
Later among the works it cites.
Relative error tensor low rank approximation
Zhao Song, David P Woodruff, and Peilin Zhong · 2019
Later among the works it cites.
A faster interior point method for semidefinite programming
Haotian Jiang, Tarun Kathuria, Yin Tat Lee, Swati Padmanabhan, and Zhao Song · 2020
Later among the works it cites.
Matrix completion using alternating minimization for distribution system state estimation
Yajing Liu, April Sagan, Andrey Bernstein, Rui Yang, Xinyang Zhou, and Yingchen Zhang · 2020
Later among the works it cites.
Fast sketching of polynomial kernels of polynomial degree
Zhao Song, David Woodruff, Zheng Yu, and Lichen Zhang · 2021
Later among the works it cites.
Oblivious sketching-based central path method for linear programming
Zhao Song and Zheng Yu · 2021
Later among the works it cites.
Breaking the linear iteration cost barrier for some well-known conditional gradient methods using maxip data-structures
Zhaozhuo Xu, Zhao Song, and Anshumali Shrivastava · 2021
Later among the works it cites.
Solving sdp faster: A robust ipm framework and efficient implementation
Baihe Huang, Shunhua Jiang, Zhao Song, Runzhou Tao, and Ruizhe Zhang · 2022
Later among the works it cites.
Dynamic tensor product regression
Aravind Reddy, Zhao Song, and Lichen Zhang · 2022
Later among the works it cites.
Faster matrix multiplication via asymmetric hashing
Ran Duan, Hongxun Wu, and Renfei Zhou · 2023
Closest in time.
Matrix completion in almost-verification time
Jonathan Kelner, Jerry Li, Allen Liu, Aaron Sidford, and Kevin Tian · 2023
Closest in time.
Semi-random sparse recovery in nearly linear time
Jonathan Kelner, Jerry Li, Allen Liu, Aaron Sidford, and Kevin Tian · 2023
Closest in time.
An online and unified algorithm for projection matrix vector multiplication with application to empirical risk minimization
Lianke Qin, Zhao Song, Lichen Zhang, and Danyang Zhuo · 2023
Closest in time.
A tale of two efficient value iteration algorithms for solving linear mdps with large action space
Zhaozhuo Xu, Zhao Song, and Anshumali Shrivastava · 2023
Closest in time.