Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > SUB-LINEAR ALGORITHM:
Reports tagged with Sub-linear Algorithm:
TR15-128 | 10th August 2015
Roee David, Elazar Goldenberg, Robert Krauthgamer

Local Reconstruction of Low-Rank Matrices and Subspaces

Revisions: 2

We study the problem of \emph{reconstructing a low-rank matrix}, where the input is an $n\times m$ matrix $M$ over a field $\mathbb{F}$ and the goal is to reconstruct a (near-optimal) matrix $M'$ that is low-rank and close to $M$ under some distance function $\Delta$.
Furthermore, the reconstruction must be local, ... more >>>




ISSN 1433-8092 | Imprint