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, i.e., provides access to any desired entry of $M'$ by reading only a few entries of the input $M$ (ideally, independent of the matrix dimensions $n$ and $m$).
Our formulation of this problem is inspired by the local reconstruction framework of Saks and Seshadhri (SICOMP, 2010).

Our main result is a local reconstruction algorithm for the case where $\Delta$ is the normalized Hamming distance (between matrices).
Given $M$ that is $\epsilon$-close to a matrix of rank $d<1/\epsilon$ (together with $d$ and $\epsilon$), this algorithm computes with high probability a rank-$d$ matrix $M'$ that is $O(\sqrt{d\epsilon})$-close to $M$.
This is a local algorithm that proceeds in two phases.
The \emph{preprocessing phase} reads only $O(\sqrt{{d}/{\epsilon^3}})$ random entries of $M$,
and stores a small data structure.
The \emph{query phase} deterministically outputs a desired entry $M'_{i,j}$ by reading only the data structure and $2d$ additional entries of $M$.

We also consider local reconstruction in an easier setting, where the algorithm can read an entire matrix column in a single operation. When $\Delta$ is the normalized Hamming distance between vectors,
we derive an algorithm that runs in polynomial time
by applying our main result for matrix reconstruction.
For comparison, when $\Delta$ is the truncated Euclidean distance and $\mathbb{F}=\mathbb{R}$,
we analyze sampling algorithms by using statistical learning tools.

Fixed several bugs in the proof Appeared on Section 4.

We study the problem of \emph{reconstructing a low-rank matrix}, where the input is an $n\times m$ matrix $M$ over a field $\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, i.e., provides access to
any desired entry of $M'$ by reading only a few entries of the input $M$
(ideally, independent of the matrix dimensions $n$ and $m$).
Our formulation of this problem is inspired by the local reconstruction framework of Saks and Seshadhri (SICOMP, 2010).

Our main result is a local reconstruction algorithm for the case
where $\Delta$ is the normalized Hamming distance (between matrices).
Given $M$ that is $\epsilon$-close to a matrix of rank $d<1/\epsilon$
(together with $d$ and $\epsilon$),
this algorithm computes with high probability a rank-$d$ matrix $M'$
that is $O(\sqrt{d\epsilon})$-close to $M$.
This is a local algorithm that proceeds in two phases.
The \emph{preprocessing phase}
reads only $\tO(\sqrt{{d}/{\epsilon^3}})$ random entries of $M$,
%runs in time $\tO\big( \frac{1}{\epsilon} (\frac{(8e)^2\ln^2 d}{ d\epsilon })^{d} \big)$
and stores a small data structure.
The \emph{query phase} deterministically outputs a desired entry $M'_{i,j}$
by reading only the data structure and $2d$ additional entries of $M$.
% runs in time $O(d^2)$

We also consider local reconstruction in an easier setting,
where the algorithm can read an entire matrix column in a single operation.
When $\Delta$ is the normalized Hamming distance between vectors,
we derive an algorithm that runs in polynomial time
by applying our main result for matrix reconstruction.
For comparison, when $\Delta$ is the truncated Euclidean distance and $\F=\R$,
we analyze sampling algorithms by using statistical learning tools.

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, i.e., provides access to any desired entry of $M'$ by reading only a few entries of the input $M$ (ideally, independent of the matrix dimensions $n$ and $m$).
Our formulation of this problem is inspired by the local reconstruction framework of Saks and Seshadhri (SICOMP, 2010).

Our main result is a local reconstruction algorithm for the case where $\Delta$ is the normalized Hamming distance (between matrices).
Given $M$ that is $\epsilon$-close to a matrix of rank $d<1/\epsilon$ (together with $d$ and $\epsilon$), this algorithm computes with high probability a rank-$d$ matrix $M'$ that is $O(\sqrt{d\epsilon})$-close to $M$.
This is a local algorithm that proceeds in two phases.
The \emph{preprocessing phase} reads only $O(\sqrt{{d}/{\epsilon^3}})$ random entries of $M$,
and stores a small data structure.
The \emph{query phase} deterministically outputs a desired entry $M'_{i,j}$ by reading only the data structure and $2d$ additional entries of $M$.

We also consider local reconstruction in an easier setting, where the algorithm can read an entire matrix column in a single operation. When $\Delta$ is the normalized Hamming distance between vectors,
we derive an algorithm that runs in polynomial time
by applying our main result for matrix reconstruction.
For comparison, when $\Delta$ is the truncated Euclidean distance and $\mathbb{F}=\mathbb{R}$,
we analyze sampling algorithms by using statistical learning tools.