Lower Bounds on Adaptive Sensing for Matrix Recovery

We study lower bounds on adaptive sensing algorithms for recovering low rank matrices using linear measurements. Given an n × n matrix A, a general linear measurement S(A), for an n × 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  that satisfies for a small constant c. Here A F denotes the Frobenius norm ( i,j A 2 i,j ) 1/2 . 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 σ 2 . Candés and Plan (IEEE Trans. Inform. Theory 2011) study non-adaptive algorithms for low rank matrix recovery using random linear measurements. They use the restricted isometry property (RIP) of Random Gaussian Matrices to give tractable algorithms to estimate A from the measurements. At the edge of the noise level where recovery is information-theoretically feasible, it is known that their non-adaptive algorithms need to perform Ω(n 2 ) measurements, which amounts to reading the entire matrix. An important question is whether adaptivity helps in decreasing the overall number of measurements. While for the related problem of sparse recovery, adaptive algorithms have been extensively studied, as far as we are aware adaptive algorithms and lower bounds on them seem largely unexplored for matrix recovery. We show that any adaptive algorithm that uses k linear measurements in each round and outputs an approximation as in (1) with probability ≥ 9/10 must run for t = Ω(log(n 2 /k)/ log log n) rounds. Our lower bound shows that any adaptive algorithm which uses n 2-β (for any constant β > 0) linear measurements in each round must run for Ω(log n/ log log n) rounds to compute a good reconstruction with probability ≥ 9/10. Hence any adaptive algorithm that has o(log n/ log log n) rounds must use an overall Ω(n 2 ) linear measurements. Our techniques also readily extend to obtain lower bounds on adaptive algorithms for tensor recovery. Our hard distribution also allows us to give a 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.