  We study lower bounds on adaptive sensing algorithms for recovering low rank
matrices using linear measurements. Given an $n \times n$ matrix $A$, a general
linear measurement $S(A)$, for an $n \times n$ matrix $S$, is just the inner
product of $S$ and $A$, each treated as $n^2$-dimensional vectors. By
performing as few linear measurements as possible on a rank-$r$ matrix $A$, we
hope to construct a matrix $\hat{A}$ that satisfies $\|A - \hat{A}\|_F^2 \le
c\|A\|_F^2$, for a small constant $c$. It is commonly assumed that when
measuring $A$ with $S$, the response is corrupted with an independent Gaussian
random variable of mean $0$ and variance $\sigma^2$. Cand\'es and Plan study
non-adaptive algorithms for low rank matrix recovery using random linear
measurements.
  At a certain noise level, it is known that their non-adaptive algorithms need
to perform $\Omega(n^2)$ measurements, which amounts to reading the entire
matrix. An important question is whether adaptivity helps in decreasing the
overall number of measurements. We show that any adaptive algorithm that uses
$k$ linear measurements in each round and outputs an approximation to the
underlying matrix with probability $\ge 9/10$ must run for $t =
\Omega(\log(n^2/k)/\log\log n)$ rounds showing that any adaptive algorithm
which uses $n^{2-\beta}$ linear measurements in each round must run for
$\Omega(\log n/\log\log n)$ rounds to compute a reconstruction with probability
$\ge 9/10$. Hence any adaptive algorithm that has $o(\log n/\log\log n)$ rounds
must use an overall $\Omega(n^2)$ linear measurements. Our techniques also
readily extend to obtain lower bounds on adaptive algorithms for tensor
recovery and obtain measurement-vs-rounds trade-off for many sensing problems
in numerical linear algebra, such as spectral norm low rank approximation,
Frobenius norm low rank approximation, singular vector approximation, and more.
