Lower Bounds on Adaptive Sensing for Matrix Recovery

Praneeth Kacham, David P Woodruff

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…