Summary
Sparse recovery for vectors has been studied for a long time. It has been shown that allowing adaptive queries will give extra power to reduce the number of queries. We also have upper and lower bounds in this setting. More recently, sparse recovery for low-rank matrices has also been extensively studied. With non-adaptive queries, $\Omega(n^2)$ queries are necessary. With adaptive queries, based on the power method, we get an algorithm with $O(nr)$ linear measurements in each round over $O(\log n)$ adaptive rounds. It is an interesting question to see if the power method is optimal in this setting.
This paper gives an affirmative answer to this question by showing a measurement-vs-rounds trade-off for recovering low-rank matrices using linear measurements. More specifically, let $A$ be an $n$-by-$n$ matrix with rank $r$. In each round, the algorithm can make $k$ queries. Each query is an $n$-by-$n$ matrix $S$, and the answer is $\langle S, A\rangle$ with some Gaussian noise. The goal is to reconstruct a matrix $\hat{A}$ such that $\|\hat{A}-A\|_F\leq c\|A\|_F$. The main result of this paper is that any adaptive algorithm which uses $n^{2-\beta}$ linear measurements in each round must run for $o(\log n/ \log \log n)$ rounds to compute a good reconstruction with high probability. Their techniques also apply to obtain measurements-vs-rounds trade-offs for other numerical linear algebra problems, including low-rank approximation in several different norms, singular vector approximation, etc.
Technically, the construction of the hard instance is $A=\frac{\alpha}{\sqrt{n}}\sum_{i=1}^r u_iv_i^\top$, where $u_i,v_i$ are independent, Gaussian random vectors. In the proof of their main result, they first reduce to show the lower bound for a deterministic algorithm with perfect linear measurements of the random matrix $\frac{\alpha}{\sqrt{n}}\sum_{i=1}^r u_iv_i^\top+G$, where $G$ is a Gaussian matrix, outputting a reconstruction of $\frac{\alpha}{\sqrt{n}}\sum_{i=1}^r u_iv_i^\top$. The key observation is that the distribution of the responses in the first round is close to $N(0, I_k)$, and therefore the algorithm cannot have a lot of “information” about the target matrix. The proof relies on a random tensor concentration result and Bayes risk lower bounds.
Strengths
This paper fills a gap in the field of sparse recovery and makes significant progress in understanding the limitations of adaptive queries in solving numerical linear algebra problems. Their main result is the lower bound for the sparse recovery of low-rank matrices, nearly matching the upper bound via the power method. Even if they use some techniques in prior works, the proofs are still non-trivial. This paper is well-motivated, and the idea of their techniques and proofs are clearly presented. Most of the claims are sound to me.
Weaknesses
For the applications, it is difficult to judge the significance since there is not enough comparison between the results in this paper and prior works. It seems that some applications are for the regimes incomparable to the previous literature.
Questions
1. Does the lower bound require that all the iterations take $k$ queries uniformly? What if the algorithm can adaptively decide the number of queries in each iteration?
2. It would be better to show some known upper bounds for the problems in Table 1.
3. Line 52: $M\in \mathbb{R}^{n\times n} \rightarrow \mathbb{R}^t$. $t$ should be $k$.
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.