We have not lifted any functions out of this paper's repositories yet, so there is nothing we have run. The repositories linked to it are listed below.
Some links come from the archived Papers with Code dataset (CC BY-SA 4.0): attribution and licence.
Let M be a random (alpha n) x n matrix of rank r<<n, and assume that a uniformly random subset E of its entries is observed. We describe an efficient algorithm that reconstructs M from |E| = O(rn) observed entries with relative root mean square error RMSE <= C(rn/|E|)^0.5 . Further, if r=O(1), M can be reconstructed exactly from |E| = O(n log(n)) entries. These results apply beyond random matrices to general low-rank incoherent matrices. This settles (in the case of bounded rank) a question left open by Candes and Recht and improves over the guarantees for their reconstruction algorithm. The complexity of our algorithm is O(|E|r log(n)), which opens the way to its use for massive data sets. In the process of proving these statements, we obtain a generalization of a celebrated result by Friedman-Kahn-Szemeredi and Feige-Ofek on the spectrum of sparse random matrices.
The same record, over MCP at https://syntology.ai/mcp:
get_harvested_code_for_paper("0901.3150")
get_code_for_paper("0901.3150")
have("0901.3150")
The run record, dated, one paper per request, free:
curl https://syntology.ai/api/ran/0901.3150.json
A badge for a README (the split and the date, never a ratio):
[](https://syntology.ai/paper/0901.3150)
Connect an agent — have() is free.