  We study low rank matrix and tensor completion and propose novel algorithms
that employ adaptive sampling schemes to obtain strong performance guarantees.
Our algorithms exploit adaptivity to identify entries that are highly
informative for learning the column space of the matrix (tensor) and
consequently, our results hold even when the row space is highly coherent, in
contrast with previous analyses. In the absence of noise, we show that one can
exactly recover a $n \times n$ matrix of rank $r$ from merely $\Omega(n
r^{3/2}\log(r))$ matrix entries. We also show that one can recover an order $T$
tensor using $\Omega(n r^{T-1/2}T^2 \log(r))$ entries. For noisy recovery, our
algorithm consistently estimates a low rank matrix corrupted with noise using
$\Omega(n r^{3/2} \textrm{polylog}(n))$ entries. We complement our study with
simulations that verify our theory and demonstrate the scalability of our
algorithms.
