Lower Bounds on Adaptive Sensing for Matrix Recovery

Praneeth Kacham, David P. Woodruff

Abstract

In the field of matrix recovery, the potential benefits of adaptive sensing—where measurement directions are chosen based on previous results—have remained a significant open question. This work establishes fundamental lower bounds on the number of rounds required for adaptive sensing, demonstrating that even with the flexibility of adaptivity, a logarithmic number of rounds is necessary to recover a low-rank matrix unless the total number of measurements approaches the size of the matrix itself. These results effectively prove that the classic power iteration method is near-optimal for spectral low-rank approximation and related tasks.

Introduction

Matrix recovery involves reconstructing a low-rank $n \times n$ matrix from a limited set of linear measurements. This task is critical in domains like medical imaging, sensor networks, and recommendation systems, where acquiring measurements is often costly or time-consuming. While non-adaptive sensing (choosing all measurements upfront) is well-understood, adaptive sensing offers the theoretical possibility of reducing the total measurement count by refining queries based on intermediate results.

While adaptivity provides substantial gains in sparse vector recovery (compressed sensing), its impact on matrix recovery has been less clear. This paper addresses whether adaptivity can circumvent the standard measurement barriers and what trade-offs exist between the number of adaptive rounds and the measurements taken per round.

Methodology: Information-Theoretic Lower Bounds

The authors employ a rigorous information-theoretic framework to derive lower bounds. The core of their approach is the construction of a "hard distribution" designed to be the worst-case scenario for any recovery algorithm.

The Hard Distribution

The researchers hide a low-rank "spike"—a matrix formed by the outer product of random Gaussian vectors—within a larger matrix of standard Gaussian noise ($N(0,1)$). To distinguish this signal from the noise, an algorithm must accumulate enough "information."

Information Growth and Rotational Invariance

The study defines "information" as the squared projection of the hidden signal onto the subspace spanned by the algorithm's queries. By leveraging the rotational invariance of Gaussian noise, the authors prove that an algorithm's queries are essentially obscured by noise until a significant number of rounds have passed. Specifically, they show that in each adaptive round, the information can only grow by a small multiplicative factor. This limits how quickly an algorithm can "zoom in" on the hidden signal.

Key Insights: The Power Method and the $n^2$ Barrier

The most significant finding is that existing iterative methods, such as the Power Method, are essentially optimal. The Power Method typically requires $O(\log n)$ rounds to converge; the authors show that no adaptive algorithm can significantly beat this without resorting to an impractical number of measurements.

The Round-Measurement Trade-off

The paper formalizes a strict trade-off: to minimize the number of rounds ($t$), an algorithm must drastically increase the number of measurements ($k$) per round. To surpass the $\Omega(n^2)$ total measurement barrier—where one might as well have measured the entire matrix—an algorithm must utilize at least $\Omega(\log n / \log \log n)$ rounds.

Linear Measurements vs. Matrix-Vector Products

A surprising result of this analysis is that general linear measurements do not offer a substantial advantage over simpler matrix-vector products for problems like Spectral Low-Rank Approximation (LRA). This suggests that the structural constraints of the matrix recovery problem are more influential than the sophistication of the measurement type.

Quantitative Results

The paper establishes several concrete lower bounds for various matrix tasks:

  • General Matrix Recovery: For a constant factor approximation using $k$ measurements per round, the required rounds are $t = \Omega\left(\frac{\log(n^2/k)}{\log \log n}\right)$.
  • Spectral LRA: For 2-approximate spectral LRA, the bound is similarly $\Omega\left(\frac{\log(n^2/k)}{\log \log n}\right)$. If high-probability success ($1 - 1/poly(n)$) is required, the bound tightens to $\Omega(\log(n^2/k))$.
  • Singular Vector Approximation: Approximating the $i$-th singular vector follows the same logarithmic round complexity requirements.

Limitations and Future Outlook

While these bounds provide a near-complete picture, some gaps remain. The bounds for constant failure probability are optimal only up to a $\log \log n$ factor. Additionally, a specific lower bound for rank-1 spectral LRA on symmetric matrices remains an open question. Finally, while Gaussian noise is the standard benchmark, future research could explore how these fundamental limits shift under different noise distributions, such as heavy-tailed models.

Conclusion

By establishing these lower bounds, the authors provide a theoretical ceiling for the efficiency of adaptive sensing in matrix recovery. The results reinforce the importance of classical iterative methods and provide a clear mathematical framework for understanding the inherent complexity of recovering low-rank structures from noisy, linear observations.

Summary updated

Abstract

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.
BibTeX
@inproceedings{kacham2023lower,
  author = {Praneeth Kacham and David P. Woodruff},
  title = {{Lower Bounds on Adaptive Sensing for Matrix Recovery}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2023},
  url = {https://openreview.net/forum?id=gWzyuurlhu},
}
Figure