Lower Bounds on Adaptive Sensing for Matrix Recovery
Authors: Praneeth Kacham
David Woodruff
Venue: NeurIPS 2023 poster (2023)
Keywords: Compressed Sensing
Matrix Recovery
Low rank approximation

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$. Here $|A|\_F$ denotes the Frobenius norm $(\sum_{i,j} A_{i,j}^2)^{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 $\sigma^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 $\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. 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 $\ge 9/10$ must run for $t = \Omega(\log(n^2/k)/\log\log n)$ rounds. Our lower bound shows that any adaptive algorithm which uses $n^{2-\beta}$ ($\beta > 0$ is arbitrary constant) linear measurements in each round must run for $\Omega(\log n/\log\log n)$ rounds. 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.

Lower Bounds on Adaptive Sensing for Matrix Recovery
Praneeth Kacham Computer Science Department Carnegie Mellon University
David Woodruff
Computer Science Department Carniie Mellon University dwoodruf@cs cmu. emu.edu
pkachamê cs. cma. emu
Abstract
We study lower bounds on adaptive sensing algorithms for recovering low rank matrices using linear measurements. Given measurement 5(4), for an n x n matrix S, is just the inner product of and A, each treated as ninddimensional vectors. By performing few linear measurements as possible on rank-r matrix A, we hope construct a matrix A that satisfies
matrix A, general linear
|| Á c||A
(1)
for small constant Here || denotes the Frobenius norm (E.s A 21/2 Is commonly assumed that when measuring A with S, the response is corrupted with an independent Gaussian random variable of mean and variance o²_ Candés and Plan (IEEE Trans. Inform. Theory 201 study non-adaptive algorithms for low rank matrix recovery using random linear measurements. They use the restricted isometry property (RIP) of Random Gaussian Matrices give tractable algorithms to estimate A from the measurements.
At the edge of the noise level where recovery is is known that their non-adaptive algorithms need to perform ?(n²) measurements, which amounts to reading the entire matrix. An important question is whether adaptivity helps 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 linear mcasurements in each round and outputs an approximation as in (1) with probability 2 9/ 10 must run for é = 2[log n /k)/ log log n) rounds. Our lower bound shows that any adaptive algorithm which uses 2- (for any constant 3 > 0) linear measurements each round must run for 2(oog n log log n) rounds compute good reconstruction with probability 2 9/10. Hence any adaptive algorithm that has o(log n/ log log n) rounds must use an overall 2(n²) linear measurements. Our techniques also readily extend to obtain lower bounds on adaptive algorithms for tensor recovery.
feasible, it
Our hard distribution also allows us to give a mcasurement-vs-rroue 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.
trade-off
Introduction
Sparse recovery, also known compressed sensing, is the study of under-determined systems of equations subject to a sparsity constraint. Suppose we know that an unknown vector r E IR"
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

has at most & non-zero entries. We would like use measurement matrix M E R to recover the vector x given measurements y = Mr. The number l of measurements is an important parameter we would like to optimize as it models the equipment cost physical settings and running times in computational settings. Ideally one would like for the number & of measurements to scale proportionally to the sparsity of the unknown vector I.
One way of modeling sparse recovery is as "stable sparse recovery". Here we want a distribution M over k matrices such that for any R", with probability 2 1 5 over M ~ M,, we can construct a vector è from Mæ such that
o - 2 ppp S (1 E)
min r-sparse
||
x'
llp.
Note that the above formulation is more robust as it does not require the underlying vector x' to be exactly r-sparse and instead asks to recover the top r coordinates of x.
(n/r) measurements is both necessary and sufficient [6, 9, 22, 4]. See [23] and references therein for upper and lower bounds for other values of p.
For = 2, it is known that = "reerrrllo(zz
In the same vein, the problem low rank matrix recovery has been studied. See [5, 35] and references therein for earlier work and numerous applications. In this problem, the aim is to recover a low rank matrix using linear mcasurements. Here we want a distribution .M over linear operators M. p=*= - Rt such that for any low rank matrix A, with probability construct matrix Á from (AA) such that the reconstruction error || All is small. Note that a linear operator M R2 - R can be equivalently represented as a matrix M E R such that M . vec(A) = (A) where vec(A) denotes the appropriate flattening of the matrix A into vector. We call the rows of M linear measurements. Without loss of generality, we can assume that the rows of the matrix M are orthonormal, as the responses for non-orthonormal queries can be obtained via simple change of basis.
- over M ~ M, we
In addition, to model the measurement error that occurs in practice, it is standard assumption that when querying with M, we receive M vec(A) + 9. where g is a k-dimensional vector with independent Gaussian random variables of mean 0 and variance o², and we hope to reconstruct A with small error from M veo( A) + g. Clearly, when A has rank r, we need to perform (2(r)) linear measurements, the matrix A has (nr)) independent parameters. Hence, the aim is to perform not many more linear measurements than nr while being able to obtain estimate Å for A with low estimation error.
Given a rank-r matrix A, [5] show that if the k x n²² matrix M is constructed with independent standard Gaussian entries, then with probability 2 1 exp(-cn), estimate Á can be constructed from M vec(A) + g such that A Ál| O(nro² /k). They use the restricted isometry property (RIP) of the Gaussian matrix M to obtain algorithms that give an estimate Å. The error bound is intuitive since the reconstruction error increases with increasing noise and proportionally goes down when the number of measurements & increases.
While we formulated the sparse recovery and matrix recovery problems in non non-adaptive way, there have been works which study adaptive algorithms for sparse recovery. Here we can produce matrices (6) adaptively based on the responses received (1) x, M (2)2),.... M (i-1), 1)=z x and the hope is that allowing for adaptive algorithms with small number of adaptive rounds, obtain algorithms that overall perform fewer linear measurements than non- non-adaptive algorithms with the same reconstruction error. It is additionally assumed that the noise across different rounds is independent. For sparse recovery, in the case of p = 2, it is known that over Olog log n) rounds adaptivity, a total of O( r log log(n log(n/r)) linear measurements suffices [14, 21]. improving over the requirement of Or log(n/r)) linear measurements for non-adaptive algorithms. For a constant 8, for any number of rounds, it is known that Q(r + log log n) linear measurements are required [23]. Recently, [16) gave a lower bound on the total number of measurements if the number of adaptive rounds is constant.
While there has been a lot of interest in adaptive sparse recovery, both from the algorithms and the lower bounds perspective, the adaptive matrix recovery problem surprisingly does not seem to have any lower bounds. In adaptive matrix recovery, similar to adaptive sparse recovery, one is allowed to query matrix (t) in round based on the responses received in the previous rounds, and again the hope is that with more rounds of adaptivity, the total number of linear measurements that is to

---

be performed decreases. There is some work that studies adaptive matrix recovery with rounds of adaptivity (see [34] and references therein) but the full landscape of adaptive algorithms for matrix recovery seems unexplored.
We address this from the lower bounds side in this work. We show lower bounds on adaptive algorithms that recover a rank-r matrix of the form (a/ (o/vn) Σi=1 u, where the coordinates of u, and v; are sampled independently from the standard Gaussian distribution. Without loss of generality', we assume that the measurement matrix M in each round has orthonormal rows. We also assume that for + j. the measurement matrices M (M = 0, i.c., measurements across adaptive rounds are orthonormal, since non-orthonormal measurements can be reconstructed from orthonormal measurement matrices by a change of basis.
We now give an alternate way of looking at the adaptive sparse recovery problem: Fix a set of vectors Wi My and vI,...,y; Ur and let the underlying matrix want recon- struct be (a// (n/vn) Ei=1 dad for a large enough constant a. In round 1, we query a matrix ( Rixn" drawn from an appropriate distribution and receive the response vector r(1)
( vec((a/ vn) Ei=1 u.u,) + +g()) where g(d) a vector of independent Gaussian random variables with mean O and variance o². In round 2, as a function of ( and (1) and our randomness, we query a random matrix (x(())))) E R and receive a response vector 72) = (0(1)) vec((a/ vn) Ei= )ave) g() where g(2) is again vector with independent Gaussian entries and independent of g( and so on. Crucially, using the rotational invariance of Gaus- sian random vectors, if G is an n X n matrix with independent Gaussian random variables with mean 0 and variance o², the response (1) has the same distribution as --vel)))v(((aa)))
E u.d! + G) and as M (2) (r(1)) is chosen to be orthonormal to ( the distribution of (2) conditioned on r()) the same as that of (1())) (vec((a/ VT) E u.u!! G)).
Thus, any adaptive matrix recovery algorithm can be seen as performing non-noisy adaptive measure- ments on the matrix (a/ vn) Σi= u.u, + G where the Gaussian matrix G is sampled independently of the measurement algorithm. From the responses the algorithm receives, it then tries to recon- struct the matrix (a/vn) Σ u.e.". This way of looking at adaptive sparse recovery immediately yields adaptive algorithm: when the smallest singular value of (a/ /n) Ei= uey is a constant times larger than |G'||,, 2, then the power method with a block size of r outputs an approximation of (a/ VT) Ei= ". in (log n) rounds. Note that r matrix-vector products can be implemented using nr linear measurements. More generally, Gu [12] showed that using power iteration with block size of k/n (for & 2 nr), we can obtain an approximation in O(log(2 (n2 /k)) adaptive rounds. Thus the already existing algorithms exhibit no. of measurements vs no. of rounds trade-off.
From results in random matrix theory, we have that ||G||2 F a /nn with high probability. And as we are interested in reconstruction when the vectors U1, u, and UI,..., Ur follow the Gaussian distribution we also have that l|u/|la R [|0/||2 R v simultaneously with large probability. Thus, to make the extraction of (a/ VT) Ei= iasn informaaion-thherreiclllll theoretically possible, we need assume
that a 2 a. Hence, in this work we assume that a = 1 and that a is a large enough constant, and we study lower bounds on adaptive matrix recovery algorithms.
If the vectors U1,..., Uy and U1,..., Or are sampled from the standard n dimensional Gaussian distri- bution and r S n/2, we also have that with high probability (Ca/vn) Σx- d 1l a²nr. Now the algorithms of [5], which use a uniform random Gaussian matrix M with m rows as the measure- ment matrix, for (a/vm) Ei ine reconstruct matrix À such that || (a/ vn) E wa I| <
Gare where 7m is the measurement error. As we assumed above that a = when measuring with a matrix with orthonormal rows, we assume that the measurement error T. when measuring with a Gaussian matrix is n, as each row of M has n² independent Gaussian coordinates and therefore has a norm zo n. Thus, using reconstruction algorithms from [5], we obtain a matrix Á satisfying Á - (a/ vn) E noe l < C=nrr. Now, to make Á (a/vn) E uuu. II S (1/10)l[(a/aa VT) 4.oe P. we need to set m (o(2//a)) Hence, in the parameter regimes we
'In general, the sparse recovery and matrix recovery models, the algorithms may make the same query and obtain responses with independent noise added which can be used to say obtain more accurate result using the median/mean estimator. But all the algorithms we are aware of for sparse recovery and matrix recovery do not explore independence of noise across queries in this way.
3

---

We assume that there is an unknown rank-r matrix A E Raxx to be recovered. Given any linear measurement I²², we receive a response (q. vec(A)) g. where g ~ No, (lll.). We further assume that the noise for two different measurements is independent. Without loss of generality, we study, the algorithms of [5] need to perform (n()) non-adaptive queries, which essentially means that they have to read a constant fraction of the n² entries in the matrix. While the power method performs ((r) linear measurements in each round over (llog n) adaptive rounds oulput an approximation A. The question we ask is:
"Is the power method optimal? Are there algorithms that have o(log n) adaptive rounds and use n 2-88 measurements in each round?"
We answer this question by showing that any algorithm that has o(log n/ log log adaptive rounds must use 2 n= linear measurements, for any constant 9 > 0, in each round. The lower bound shows that power method is essentially optimal if we want to use 2 linear measurements in each round and that any algorithm with o(logn/ n/ log log n) adaptive rounds essentially reads the whole matrix.
We further obtain a rounds vs measurements trade-off for many numerical linear algebra problems in the sensing model. In this model, there is an n X n matrix A with which we can interact only using general linear measurements and we want to solve problems such as spectral norm low rank approximation of A, Frobenius norm low rank approximation of A, etc. In general, numerical linear algebra algorithms assume that they either have access to the entire matrix or that the matrix accessible in the matrix- vector product model where one can query a vector and obtain the result A Recently, the iittoo-mmtrix-vecttee well. Linear measurements are more powerful than both the matrix-vector product model and the vector-matrix-vecd product model. Any matrix vector product A v can be computed using linear measurements of A and any vector vector-matrix vector product T Ar can be computed using a single linear measurement of A. Thus, the model of general linear measurements may lead to faster algorithms.
product model has received significant attention as
For certain problems in numerical linear algebra, general linear measurements are significantly more powerful than the matrix-vector product model. Indeed, for computing the trace of an x matrix A, one can do this exactly with a single deterministic general linear measurement, just by adding up the diagonal entries of A. However, in the matrix-vector product model, it is known that (n)) matrix-vector products are needed to compute the trace exactly [29], even if one uses randomization. A number of problems were studied in the vector-matrix-veet was shown that to approximate the trace of A up to a (1 + e)-factor with probability 1 one needs i(= log queries. This contrasts sharply with the single deterministic general linear measurement for computing the trace exactly. Thus, there are good reasons to conjecture that general linear measurements may lead to algorithms requiring fewer rounds of adaptivity compared to algorithms in the matrix-vector product query model. Surprisingly. our lower bounds show that for many numerical linear algebra problems, linear measurements do not give much advantage over matrix-vector products.
product model in [24]. and in [32]
1.1 Our Results
also assume throughout that all the queries an algorithm makes across all rounds form a matrix with orthonormal rows. Our main result for adaptive matrix sensing is as follows:
Theorem 1.1. There exists constant such that any randomized algorithm which makes k 2 noisy linear measurements of an arbitrary rank-r matrix A with || = =((r) in each of t rounds, and outputs an estimate A satisfying || - Áll < e| with probability 2 9/10 over the randomness of the algorithm and the Gaussian noise, requires i = ((loggn²/k)/ (log I)g.)).
Dependence on noise In our results, we assumed that given linear measurement E R²? the response is distributed as (((g, vec ll)) Our lower bounds also hold when the response is distributed as ((g, vec(A) o² (31g) for any parameter such that d' < a S 1, where é is constant. This can be seen by simply scaling the matrix in the theorem above and adjusting the constants while proving the theorem.

---

Application
Failure Probability
Lower Bound
2- approximate spectral LRA 2- 2-approximate spectral LRA
0.1
clog(n" /k)/ / log log
1/ poly(n)
clog(n2 (onnn///)]]
cloo(n" (k3)
2- a-approximate Schatten p LRA
0.1
(1/p) log ( log
2- 2-approximate Ky-Fan LRA
0.1
clog
log(p) log
1 + /n-approximmte Frobenius LRA
0.1
clog(n" (oggnn/k))/mme log log
0.1-approximate i-th singular vectors
0.1
clog(n (log(n2/k))) /k)) log log n
2-approximate spectral reduced rank regression
0.1
clog(n2//8) /k) log log
Table I: Number of rounds lower bound for algorithms using k general linear measurements in each round. Our bound for 2-approximate spectral LRA algorithm with constant failure probability optimal up to a log log factor, and our 2-approximate spectral low rank approximation (LRA) lower bound for algorithms with failure probability 1/ poly(n) is optimal up to a constant factor.
Tensor Recovery The problem of tensor recovery with linear measurements has also been studied (see [25, 11] and references therein) where given low rank tensor, the task is to recover approxi- mation to the tensor with few linear measurements. Our techniques can also be used to obtain lower bounds adaptive algorithms for tensor recovery. Our main tool, Lemma 3.1, readily extends to tensors of higher orders by using the corresponding tail bounds from [31].
Numerical Linear Algebra We also derive lower bounds for many numerical linear algebra problems in the linear measurements model. Table 1 shows our lower bounds on the number of adaptive rounds required for any randomized algorithm using general linear measurements in each round. See Appendix E for precise statements and proofs.
1.2 Notation
Throughout the paper, use uppercase letters such G, M, Q to denote matrices and lowercase letters such as u, v to denote vectors. For vectors u, u E R", of u and v. For an arbitrary matrix M E mm the vector vec (M) E Rma denotes a flattening of the matrix M with the convention that vec(ue") ) @ v. We use boldface symbols such as M, G, u, denote that these objects explicitly sampled from appropriate distribution. We 9& to denote a multivariate Gaussian in k dimensions where each coordinate is independently sampled from (O, 1). We also use G() to denote a collection of independent multivariate Gaussian random variables of appropriate dimensions.
U E R.* denotes the tensor product
1.3 Our Techniques
Using the rotational invariance of the Gaussian distribution, we argued that any adaptive random- ized low rank matrix recovery algorithm with access to a hidden matrix (a/vn) Ei=1 iayi using noisy linear measurements can be seen as a randomized algorithm that has access to random matrix (a/ /r) Ei= I G' using perfect linear measurements where each coordinate of G is independently sampled from a Gaussian distribution.
Let A be any algorithm that satisfies the matrix recovery guarantees with, say, success probability 9/10. Let A(X, KKo,, a. 7) the output the randomized algorithm A, where the hidden matrix is X, the random seed of A is denoted by a and y denotes the measurement randomness. We have that X has rank r and satisfies || = ((rr), then
Pr Pr is correct) 9/10. ..7
(1/100]| By the above We say A(X, a, a) is correct when the output X satisfies || - < reduction, from A we have randomized algorithm A' that runs on the random matrix X + G with access to exact linear measurements and outputs correct reconstruction X with probability 2 9/10 X has rank r and X|| @(nr). Thus, for all such X,
Pr [A'(X G, is correct] 2 9/10.
G.
5

---

Here denotes the randomness used by the algorithm A'. Now, if X is random matrix constructed as (ar/ (n/vn) Eis1 d with u, v; being random vectors with independent Gaussian entries of mean 0 and variance 1, then with probability 2 99/100, || = (nr).. Thus, Pr.,G, (X
G, or) is correct] 2 8/10. Hence, there exists some fixed a such that
Pr [X + G, is conrect] 2 8/10.
Thus, the existence of a randomized algorithm that solves low rank matrix recovery as in Theorem 1.1 implies the existence of a deterministic algorithm which given access to perfect linear measurements of random matrix (a/ nn) Ei=1 ? + G outputs a reconstruction of (a/vn) Ei= d with probability 2 8/10. This is essentially reduction from randomized algorithms to deterministic algorithms using Yao's lemma. From here on, we prove lower bounds on such deterministic algorithms and conclude the lower bounds in Theorem I.I. For simplicity, we explain the proof of our lower bound for 1 here and extend to general later. We consider the random matrix G + (a/ vn)uu and show how the lower bound proof proceeds.
Note that the matrix A- = G + (no E R=** can be flattened to the vector a = (n) v) E R= Also, general linear measurement, which call a query Q E R=*x can be vectorized to q = vec(Q) E R²* with Q(A) = (q, a). Fix any deterministic algorithm. In the first round, the algorithm starts with a fixed matrix Q() E B&xxn* that corresponds to the queries and receives the response (!)) == aa Then, as a function of the response r()) in the first round, the algorithm picks a matrix (12] in the second round and receives the response 72(2) : (r())((1)))))))))))))) a. Similarly, in the i-th round, the deterministic algorithm picks a matrix ((0(r())) (0(( = Q
(-Dj E R=xn" as a function of ,()),...,,(.... ((-1)) and receives the response r ((-1)- a. Note that we assumed that the query matrices Q(i) chosen by the For a fixed u, v E R", we see that the response (1) = =0)=)(000 Qg + (a/ (a/vm)Q @ v). As the matrix Q(1) has orthonormal rows, the random variable Q = g where 9x ~ NO, 14) is drawn from a mean-zero normal distribution with identity covariance. Thus, for fixed u, u. the distribution of the first round responses to the algorithm is ((aa/ ( (u & v), Jk). Now the key observation is that [l(a/ (nee//))@((( (u & e)ll O(a2k/n) with high probability over the inputs (u, v). This uses recent concentration result for random tensors due to [31], and critically uses the fact that Q() has operator norm 1 and Frobenius norm Vk. This means that for large fraction of (u, u) pairs, the distribution of the responses seen by the algorithm in the first round is close to (0, TR), and therefore just looking at the response r(1), the algorithm cannot have a lot of "information" about which (u, v) pair is involved in the matrix that is unknown to the algorithm. So the query chosen in the second round ((2((r(()) cannot have a "large" value of Q(2) (r (T() @ v) for most inputs (u, v), with a high probability over the Gaussian component of the matrix.
algorithm have orthonormal rows and also that Q( (Q61)T= = 0, i.e., the queries across rounds are also orthonormal.
+ (())) ( v). Crucially, as the queries in round are orthogonal to the queries in round 1, we have by the rotational invariance of the Gaussian distribution that ((2) (, |g is independent of Q(1) g. and that Q (x(1] Ig is distributed as (O, I&). So, for a fixed u, v, conditioned on the first round response r(1), the distribution of the second round response (2( is given by ((aa/ (()
Suppose the value of ((2(rr())( u) is small. Again, (2)
@ v), Ix) P (0, Ix) using the assumption that Q(2) (")]( & v) is small. We again have that for a large fraction of pairs (u, v) for which Q(2) (1 (u & u) is small, the distribution of the second round response is also close to N NO, Iz). Therefore, the algorithm again does not gain a lot of information about which (u, 1) pair is involved in the matrix, and the third round query ((3) (1) (2) cannot have large value of (((())((1)) (x)))(( @ v)l12. The proof proceeds similarly for further rounds.
To formalize the above intuitive idea, we use Bayes risk lower bounds [7]. We show that with a large probability over the input matrix, the squared projection of u @ a onto the query space of the algorithm is upper bounded and we use an iterative argument to show that an upper bound on the information up until round can in turn be used to upper bound the information up until round i + 1. Bayes risk bounds are very general and us obtain upper bounds on the information learned by deterministic learner. Concretely, let θ be a parameter space and P Po 0 E θ } be set

---

of distributions, one for each 0 O. Let w be distribution over O We sample 0 w and then a ~ Po and provide the learner with æ. Given an action space A, the learner uses a deterministic decision rule : X + A to minimize 0-1 loss function L x + { 0, 1 in expectation. i.c. [E L(0, (()))l Let RBaaes((, θ w) = inf, Ee L d())]] be the loss achievable by the best deterministic decision rule d. Bayes risk lower bounds let obtain lower bounds on BBayes.
In our setting after round 1, we have θ { {(,,)) u) u, E R" }. w is the joint distribution of two independent standard Gaussian random variables in I=" and for each (u, 2) E è we let Pav be the distribution of p1)) = 9& + (a/vn) (T)//()))))
(u & v), an action space A of all &e x n² matrices with orthonormal rows (corresponding to the queries in the next round), and define a 0-1 loss function
I((u, v), Q) = { if [Q @ v)13 2 T if [Q & v)1 <
for appropriate threshold parameter T. By setting T appropriately as function tf obtain a Bayes risk lower bound of RBayes 2 1 - 1/ (1002"). ). Thus, we obtain that for any deterministic decision rule d, with probability 2 1 - 1/10t over (2, 2) w. we have
Epm [L((u, v), 0(r )))] 2 1- - 1/10t
and in particular, we have that with probability 2 1 1/10t over (2, v) ~ w.
Pr P0PPut
(1 & v)1 < T 2 1 - 1/106.
The above statement essentially says that with probability 2 1 - 1 1/10t over the inputs (u, v). the second query (x()) chosen by the deterministic algorithm has the property that [[Q()()() & w)ll3 < T with probability 2 1 1/10ft over the Gaussian G. In the second round, restrict our analysis of the algorithm to only those (u, u) which satisfy (2). We again define a distribution w' over the inputs and for each such (u,, v) we define a distribution P... over the round 1 and round responses received by the algorithm. We define a new loss function with parameter 7 = A . T for a multiplicative factor A and again obtain a statement similar to (2) for a large fraction of inputs (u, v) and repeat similar argument for ł rounds and show that there is an 52(1) fraction of the inputs for which the squared norm of the projection of u @ v onto the query space after rounds is bounded by T(t) with high probability over the Gaussian part of the input. This gives the result in Theorem 3.2. Note that Iu @ 0112 (n²) with high probability and for any fixed matrix Q with orthonormal rows, Elll Q(u @ v) 1) = le which corresponds to the amount of "information" the algorithm starts with. As we show that the "information" in each round grows by some multiplicative factor A, a number Q(loga (n² /k)) of rounds is required to obtain an "information" of ( ), which is how we obtain our lower bounds. Here information measured as the squared projection of u 6 v onto the query space of the algorithm.
We also extend our results to identifying a rank r spike (sum of random outer products) corrupted by Gaussian noise. Specifically, we consider the random matrix M = G + (a// vT) Ei= i where all the coordinates of G, u, v, are independently sampled from N (0, We show that if there is an algorithm that uses k iterations in each round and identifies the spike with probabiliiyy 2 9/10, then must run for (2 (n2 /k) log log n) rounds by appealing to the lower bound we described above for the case of r = 1. We show that if there is an algorithm for r > 1 that requires I < Olog(n2 /k:)/ log log n) adaptive rounds, then it can be used to solve the rank spike estimation problem in /. rounds as well which contradicts the lower bound.
We then provide lower bounds on approximate algorithms for host of problems such as spectral norm low rank approximation (LRA), Schatten norm LRA, Ky-Fan norm LRA and reduced rank regression, by showing that algorithms to solve these problems can be used estimate the spike wo in the random matrix G + (a/ Vn)ue and then use the aforementioned lower bounds on algorithms that can estimate the spike. Although our hard distribution is supported on non-symmetric matrices, we are still able to obtain lower bounds for algorithms for spectral norm LRA (rank r 2 2) for symmetric matrices as well by considering a suitably defined symmetric random matrix using
our hard distribution. Let A = G + (a/ (n//V))ur Vn)ue? be the hard distribution in the case of rank = 1.
0
A
We symmetrize the matrix by considering, Asym
This symmetrization, as opposed
A
0
7

---

AAT A A, has the advantage that linear measurement of Asym be obtained from an appropriately transformed linear measurement of A, thereby letting us obtain lower bounds for symmetric instances as well in the linear measurements model. However, we cannot obtain lower bounds for rank 1 spectral norm LRA for symmetric matrices using this symmetrization as the top two singular values of Asym are equal and hence even zero matrix a perfect rank spectral norm LRA for A which does not give any information about the plant u & v.
1.4 Related Work
As discussed, low rank matrix recovery has been extensively studied (see [5] and references therein for earlier work). Relatedly, [13] study the Robust PCA problem where the aim is to estimate the sum of a low rank matrix and sparse matrix from noisy vector products with the hidden matrix. [30] study the Robust PCA problem when given access to linear measurements with the hidden matrix.
For non-adaptive algorithms for low rank matrix recovery with Gaussian errors, [5] show that their selectors based on the restricted isometry property of measurement matrices are optimal up to constant factors in the minimax error sense when the noise follows a Gaussian distribution. Our Theorem 1.1 extends their lower bounds and shows that there is any randomized measurement matrix² M with k rows coupled with recovery algorithm that outputs a reconstruction for any rank matrix with || = (nr), then it must have k 21) We again note that we give lower bounds even for algorithms with multiple adaptive rounds.
Our technique to show lower bounds is to plant low rank matrix (a/ Vn) Ei= in an Gaussian matrix so that any "orthonormal" access to the plant corrupted by independent Gaussian noise. Notably this technique has been employed to obtain lower bounds on adaptive algorithms for sparse recovery in [23]. Even in the non-adaptive setting, Li and Woodruff [18] use the same hard distribution operator norm, and the Ky Fan norms. The technique to show their lower bounds is that a sketching matrix has k S. c/(r2s)) )*) rows", it cannot distinguish between the random matrix G and the random matrix G & +++Ei= u. where all the coordinates of G, U,, U; are drawn uniformly at random. They prove this by showing that drv (L1, L2) small if Li is the distribution M vee(G) and L2 the distribution of M vec(G >E Em= u.v!)) ) for any fixed measurement matrix M with k S c/(r2s") rows. Their techniques do not extend the plant estimation in the distribution G + s Ei= d.ee as the statement they prove only says that over the randomness of G. Ug Ug. the response distribution for G Ei=1 d is close the response distribution for G, but in our case, we want the distributions Lu., and fww to be indistinguishable, where Lu," is the response distribution for G + (a/ (n) Ei u.y!.
do obtain sketching lower bounds for approximating Schatten norms, the
Later, [28] considered the distribution of the symmetric random matrix W + AUUT, where W is the n x n symmetric Wigner matrix (G' + GT )/v2 and U is uniformly random r matrix with orthonormal columns. They focus on obtaining lower bounds on adaptive algorithms that estimate the spike U in the matrix-vector product model. In particular, they show that if Q is basis for the query space spanned by any deterministic algorithm after querying k adaptive matrix-vector queries, then X '-QQUUTT Q) grows as Xk/r. Using this, they show that any algorithm which, given access to an arbitrary symmetric matrix A in the matrix-vectt product query model, must use 2(r log(n)/ /gap) adaptive queries to output an n x r orthonormal matrix V satisfying, for a small enough constant c,
(V, 2 (1 c. gap) Σ x(AA,,
where gap = (A,(A) (A)) We note the above guarantee ntn-standard in the low rank approximation literature, which instead focuses more on approximation algorithms for Frobenius norm and spectral norm LRA. While in the matrix-vectin product model, their hard distribution helps in getting lower bounds for numerical linear algebra problems on symmetric matrices, it seems that our hard distribution G + (a/vn) El= u is easier to understand in the linear measurement model and gives the important property that the noise between rounds is independent, which is
2 Note that we assume a measurement matrix has orthonormal rows and that each measurement corrupted by Gaussian noise variance
Their lower bound is bit more general but state this formulation for simplicity.
8

---

what lets reduce the matrix-recovery problem with noisy measurements spike estimation in G + (o// (n/Vn) Di= u.v!
Recently, Bakshi and Narayanan [1] obtained tight lower bound for rank-1 spectral norm low rank approximation problem in the matrix-vector product model. They show that Q[log n/ vE) matrix vector products are required to obtain + s spectral norm low rank approximation. We stress that while our results are not for + & approximations, they hold in the stronger linear measurements model.
2 Notation and Preliminaries
Given an integer n 2 1, we use [rx] to denote the set {1...., J. For vector v E RR, ||u||2 = (Eie(n) 2/21//2 denotes the Euclidean norm. For a matrix A E Rnxd ||AA| |F denotes the Frobenius
norm (Ei, A22 and ||Al|2 denotes the spectral norm suP2#0 || ///////12222211/ For p 2 2, ||A||s, to denote the Schatten-p norm (E; / and for p E [min(n, d)). we use A| to denote the Ky-Fan p norm >X= F; where dI...., minu(,.d) denote the singular values of the matrix A. Given parameter k. the matrix [A], denotes the best rank approximation for matrix A in Frobenius norm. By the Eckart- Eckart-Young-Misse Young-Mirsky theorem, the best rank k approximation under any unitarily invariant norm, which includes the spectral norm, Frobenius norm, Schatten norms and Ky-Fan norms, is given by truncating the Singular Value Decomposition of the matrix A to top & singular values. We describe the Bayes Risk Lower Bounds that we use to prove Lemma 3.1 in the Appendix. Our presentation based on [7]. Due to space constraints, we have placed all proofs in the appendix.
3 Number of Linear Measurements Versus Number of Adaptive Rounds
We now state the main theorem which shows a lower bound on the number of adaptive rounds required for any deterministic algorithm to estimate the plant when the input random matrix G + (ax/ v Σi= u, We use this theorem to prove Theorem 1.1 and lower bounds for other numerical linear algebra problems.
We prove the lower bound for the rank-r plant estimation by first proving a lower bound on the rank-1 plant estimation and then reducing the rank-1 I recovery problem to rank-r recovery problem. For the rank-1 recovery problem, we prove the following lemma:
Lemma 3.1. Given an integer n, and parameters a 2 10 and ry 2 1, define the n X n random matrix M = G + suv for == a/ /n, where the entries G. v are drawn independently from the distribution N 1). Let Alg be any t-round deterministic algorithm that makes 2 n adaptive linear measurements in each round. Let Q(i) E R denote the matrix of general linear queries made by the algorithm in round j and Q matrix with orthonormal rows such that rowspan(() = rowspan( (()))) +... rowspan (Q(9), Then for all such that ( log(n)) S (Ka2)2)*k S O for universal constant K,
Pr M=G+
[I v)ll < (3K) (1 1/(10>)) 1/ poly(n).
Setting 7 (n)) the theorem shows that if S (log(n2/k)//ogg/// log(a)) for small enough constant c, then for any t-round deterministic algorithm,
Pr
[IIQ(u & v)1 < n² /100] 2 4/5.
(4)
M=
Setting 7 O(), we obtain that if < clog(n2 /k////////// //)///////ol(()/ (a) for small enough constant c, then
Pr [IIQ(u @ 1 < n² /1000 2 1/ poly(n).
M=G+supT
The proof of the above lemma is in Appendix B. The above lemma directly shows lower bounds on any deterministic algorithm that can approximate the rank-1 planted matrix. We show that the lower bounds can be extended to algorithms that estimate the rank-r plant well.

---

Theorem 3.2. Let n. and r n/2 be input parameters and be large enough constant. Lei the random matrix G + (a/vT) Ei :. be the input which can be accessed using linear measurements. If Alg is a t-round adaptive algorithm that uses linear measurements and at the end of I-rounds oulputs a matrix Å such that with probability 2 9/ 10 over the randomness of the input and the internal randomness of the algorithm,
I1A
Σ u sc("rr) 1=1
for small enough constant G, then M(log(n2
/oopg/nn/////////// (log())((a) loglog
Using the reduction from matrix recovery with noisy measurements to plant estimation with exact measurements that we described in the previous sections, we can now prove Theorem 1.1. The proof of Theorem 1.1 is in Appendix D.
Acknowledgements
Pranecth Kacham and David P. Woodruff acknowledge the partial support from a Simons Investigator Award.
References
[1] Ainesh Bakshi and Shyam Narayanan. Krylov methods are (nearly) optimal for low-rank approximation. arXiv preprint arXiv:2304.0319/ 2023. 9
[2] Ainesh Bakshi, Kenneth L. Clarkson, and David Woodruff. Low-rank approximation with 1/e3/3 matrix-vector products. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022, 2022. 25
[3] Mark Braverman, Elad Hazan, Max Simchowitz, and Blake Woodworth. The gradient com- plexity of linear regression. In Conference Learning Theory, pages 627-647. PMLR, 2020. 24
[4] Emmanuel J. Candès and Mark Davenport. How well can we estimate a sparse vector? Appl. Comput. Harmon. Anal., 34(2):317-323, 2013. ISSN 1063-5203. doi: 10.1016f..chaa.212..88 010. 2
[5] Emmanuel J Candès and Yaniy Plan. Tight oracle inequalities for low-rank matrix recovery from minimal number of noisy random measurements. IEEE Transactions on Information Theory, 57(4):2342-2333 201 3, 8
[6] Emmanuel J. Candès, Justin K. Romberg, and Terence Tao. Stable signal recovery from incomplete and inaceurate measurements. Comm. Pure Appl. Math., 1988) 2006. ISSN 0010-3640. doi: 00.1002/ca.20124..
[7] Xi Chen, Adityanand Guntuboyina, and Yuchen Zhang. bayes risk lower bounds. Journal of Machine Learning Research, 17(218):1-55 2016. 6, 9, 13
[8] Simon Foucart and Holger Rauhut. mathematical introduction to compressive sensing. Applied and Numerical Harmonic Analysis. Birkhäuser/Springer, New York, 2013. ISBN 978-0-8176-4947-0; 188-008176-494---11 doi: 00.1007/978-0-8176--888
29
[9] Anna C. Gilbert, Yi Li, Ely Porat, and Martin J. Strauss. Approximate sparse recovery: optimizing time and measurements. SIAM J. Comput., 41(2):436-453 2012. ISSN 0097-5397. doi: 10. 137/100816600 2
[10] Gene H Golub, Franklin T Luk, and Michael L. Overton. A block lanczos method for computing the singular values and corresponding singular vectors of a matrix. ACM Transactions on Mathematical Software (TOMS), 7(2):199-669 1981. 26
10

---

[11] Rachel Grotheer, Shuang Li, Anna Ma, Deanna Needell, and Jing Qin. Iterative hard thresh- olding for low ep-rank tensor models. Linear and Multilinear Algebra, pages 1-17, 2021.
[12] Ming Gu. Subspace iteration randomization and singular value problems. SIAM Journal on Scientific Computing, 37(3):A113-AA1 2015. 3, 23, 26
[13] Wooseok Ha and Rina Foygel Barber. Robust pea with compressed data. Advances in Neural Information Processing Systems, 28, 2015.
[14] Piotr Indyk, Eric Price, and David P. Woodruff. On the power of adaptivity in sparse recovery. In IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011. IEEE Computer Society, 2011 1.
[15] Praneeth Kacham and David Woodruff. Reduced-rank regression with operator norm error. In Conference on Learning Theory, pages 2679-2716 PMLR, 2021. 27
[16] Akshay Kamath and Eric Price. Adaptive sparse recovery with limited adaptivity. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium Discrete Algorithms, pages 2729-2744. SIAM, Philadelphia, PA, 2019, doi: 191113771.78111119754822.
2
[17] Beatrice Laurent and Pascal Massart. Adaptive estimation of a quadratic functional by model selection. Annals of Statistics, pages 1302-1338, 2000. 15, 20, 22
[18] Yi Li and David P. Woodruff. Tight bounds for sketching the operator norm, Schatten norms, and subspace embeddings. In Approximation, randomization, and combinatorial optimization. Algorithms and techniques, volume 60 of L.Plcs. Leibniz Int. Proc. Inform., pages Art. No. 39, 11. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2016.
[19] Yi Li, Huy L. Nguyen, and David Woodruff. On sketching matrix norms and the top singular vector. In Proceedings of the Twenty-Fifte Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 1562-1581. SIAM, 2014. 24
[20] Cameron Musco and Christopher Musco. Randomized block krylov methods for stronger and faster approximate singular value decomposition. Advances in neural information processing systems, 28, 2015. 26, 27
[21] Vasileios Nakos, Xiaofei Shi, David P. Woodruff, and Hongyang Zhang. Improved algorithms for adaptive compressed sensing. In 45th International Colloquium on Automata, Languages, and Programming, volume 107 of LJPles. Leibniz Int. Proc. Inform., pages Art. No. 90, 14. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2018. 2
[22] Eric Price and David P. Woodruff. (1 + a)pprroxieatte sparse recovery. In 201/ IEEE 52nd Annual Symposium on Foundations of Computer Science-FOCS 2011, pages 295-304, IEFE Computer Soc., Los Alamitos, CA, 2011. doi: 10. 10.1109/FCCS.2001.990
[23] Eric Price and David P. Woodruff. Lower bounds for adaptive sparse recovery. In Proceedings of the Twenty-Fourdh Fourth Annual ACM-SIAM Symposium on Discrete Algorithms,, pages 652-663. SIAM, Philadelphia, PA, 2012. 8
[24] Cyrus Rashtchian, David P. Woodruff, and Hanlin Zhu. Vector-matrix-vett vector queries for solving linear algebra, statisties. and graph problems. In Approximatton, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2020, volume 176 of L.Ples, pages 26:1 1-2:200. Schloss Dagstuhl Leibniz-7entrrm für Informatik, 2020.
[25] Holger Rauhut, Reinhold Schneider, and Željka Stojanac Low rank tensor recovery via iterative hard thresholding. Linear Algebra Appl., 523:220 2017. ISSN 0024-3795. doi: 10. 1016 law.aaa......00000 5
[26] Mark Rudelson and Roman Vershynin. Smallest singular value of random rectangular matrix. Communications on Pure and Applied Mathematics: Journal Issued by the Courant Institute of Mathematical Sciences, 62712):1777 2009, 15, 20, 22

---

[27] Arvind K Saibaba. Randomized subspace iteration: Analysis of canonical angles and unitarily invariant norms, SIAM Journal on Matrix Analysis and Applications, 40(1 40(1):23-48, 2019. 25
[28] Max Simchowitz, Ahmed El Alaoui, and Benjamin Recht. Tight query complexity lower bounds for pea via finite sample deformed wigner law. In Proceedings of the 50th Annual ACM SIGACT Symposium Theory of Computing, pages 1249-1259, 2018. 8, 24
[29] Xiaoming Sun, David Woodruff, Guang Yang, and Jialin Zhang. Querying a matrix through matrix-vector products. ACM Trans. Algorithms, 17(4):31:1-31:19, 2021.
[30] Jared Tanner and Simon Vary. Compressed sensing of low-rank plus sparse matrices. Applied and Computational Harmonic Analysis, 2023. 8
[31] Roman Vershynin. Concentration inequalities for random tensors. Bernoulli, 26(4):3139 3162, 2020. 5, 6, 15
[32] Karl Wimmer, Yi Wu, and Peng Zhang. Optimal query complexity for estimating the trace of a matrix. In International Colloquium on Automala, Lunguages, and Programming, pages 1051-1062. Springer, 2014.
[33] David P Woodruff. Sketching as a tool for numerical linear algebra. arXiv preprint 141 2014. 27
[34] Wei Zhang. Taejoon Kim, Guojun Xiong, and Shu-Hung Leung. Leveraging subspace informa- tion for low-rank matrix reconstruction. Signal processing, 163:123-13.. 131, 2019. 3
[35] Kai Zhong, Prateek Jain, and Inderjit S Dhillon. Efficient matrix sensing using rank- I gaus- sian measurements. In International conference on algorithmic learning theory, pages 3-18. Springer, 2015. 2
12

---

A Preliminaries
A.1 Bayes Risk Lower Bounds
Let θ be set of parameters and P { Po 0 O be distributions over Let be the prior distribution on θ known to learner. Suppose & ~ w, and Pg and that the learner is given r. Now the learner wants to learn some information about Let X - A be a mapping from sample z to action space A and L θ x A - 0, be a zero-one loss function. We define
Ex [L, 0 ((r))] = inf Ee [E (())), Bayes 1, = inf / and
0
Ro 0 w) = inf A /
L(0, add))) inf Egaao [I(0,a)].
aEA
We drop θ from the notation when it is clear.
f-divergence Let C denote the set of all convex functions f with f(1) O. Let P and be two distributions with densities p and over a common measure Then we have the f-divergence D₂(PI(Q) defined as
([(P1Q)= (2) qdy + ((x0))(q=0)
using the convention () 0o oc. For log(a), the t f-divergence D)(PlIQ) dxr. (PQ))) the Kullback-Leei Leibler (KI.) divergence. We frequently use dkL Y for some random variables X and Y. which means the KL divergence between the distributions of X and Y.
Now can define the f-informativity of set of distributions P with respect distribution as follows:
(y = =inf D)(PollQ)w(dd) = inf Es (Pyo
We use T(P,w) w) to denote the ʃ-informativity for x log x. We finally have the following theorem from [7].
Theorem A.1. For any 0-1 loss function L.
1y(P, ()) 2 by (RBayes Ro)-
where for a, de (a b) denotes the I-divergence between distributions P, P,Q over (0, with P[1} = a and Q { =
As corollary of the above theorem, (7] prove the following result which is the generalized Fano inequality.
Theorem A.2. For any prior w and 0-1 loss function L,,
RBayes 1 I(P, w) + 1og(1= + Ro)
log(1 - Ro)
A.2 KL Divergence
We state some properties of the Kl.-divergence that we use throughout the paper.
Lemma A.3. Let P and be two random variables with probability measures p and q such that p absolutely continuous with respect q. Let P, with probability measure be the restriction of P to an event &, ie., all E', Pr[P E- = Pr[P E & EE PreP/ E Then
1
dRi. (fll)) - Pr(P E
(dKL (pllg) + 2).
13

---

Proof. For have ((x) p(x)// Pr(P and for E (()) 0. By definition
p(z)
(KL()) = p(x)) log
dæ
g(x)
using the convention 0 log(0/1) 0. Now.
dRi. (fll4) / Pr(P EE
p(x)
p(x)
log
dx
Pr(P E E)g(z)
1 Pr(P EE)
Je p(x) log
p(z)
dr + Pr(P 8)).
((x))
We also have,
dKL [ p(x) log
p(x)
p(x)
de p(x) log
dx
((x))
g(x)
which implies
p(x) ((x))
p(x) ((x)
p(x) log
dr = dea (plla) - p(x)) log
dr.
Thus, is enough to lower bound Js p(x) log (p(x)//(<>)) dar obtain upper bound the left hand side. So,
p(x) ((x))
p(x)
(((x)
p(x) log
dx = Pr(P EE)
log
dx
E Pr(P E Pr((QEE)
p(x))
2 Pr E E log
Pr(P
where the last inequality follows from 1og[2x) being convex. Finally,
((x) log ((x)
(x 9) = Pr(P E
dr + 1og((1/tt((P)))
q(x)
DEE
(p. + Pr(P E)
$ P E)
log(Pr(Q 8)/Pr( Pr(P e E)) +
Pr(P E)
$ Pr(P E) (p. + Pr(P E
+ log(1/ Pr(P e E))
where we used p log(g/p) = (o)(()) + p logpll/1/// 20+1= for 0 1pp051
The following lemma states the chain rule for KL.-divergence.
Lemma A.4 (Chain Rule). Let (X,Y Y) be jointly distributed random variables and Z, W be independent random variables. Then
dxr(( (), W)) = dRi. ( + Ex [dKI (X
The following lemma states the KL-divergence between two multivariate Gaussians. Lemma A.5 (KL-divergence between Gaussians, folklore).
1 dxa E E2)) = llg det
det E2))
+ tr tr(==1E)) 'n) + (/22 - -11) TI) (12 - 11) n]
where n is the dimension of the Gaussian.
In this article, we use the above lemma only for Σ, Σn / which case the above lemma implies
that deL, (N (p1, N I)) (I/2) (22 M1 12
14

---

A.3 Properties of Gaussian random matrices and vectors
We use the following bounds on the norms of Gaussian matrices and vectors throughout the paper:
(i) If g is n-dimensional Gaussian with all its entries independently drawn from ((0, 1), then with probability 2 exp(-e(n)), (n/2) S | < 2)n and (ii) If G is an m x n (m 2 n)
Gaussian matrix with i.i.d. entries from (0, 1), then Pr Pr[l G [ym /n t, Vm vn t
1 - e-pp(- See [26, 17] and references therein for proofs.
Rotational Invariance We frequently use the rotational invariance property of multivariate Gaussian vectors g ~ NNO, In), which implies that for any n x n orthogonal matrix Q inde- pendent of 9. the vector Qg is also distributed as NO,.,.). Additionally, if 91.....9: 9n denote rows the matrix Q with qı chosen arbitrarily independent of and the subsequent vectors q: fr(....... 9:-1, (g1. g).... (9)-1.9)) for arbitrary functions fi satisfying qi 1 91...... - then (4-9 9) is distributed as [00, 1) and is independent of (qn, g)...., (1:-1.))1 We crucially use this property in the proof of Theorem 3.2.
B Proof of Lemma 3.1
First we discuss some notation, distributions and random variables that we use throughout the proof. Fix an arbitrary deterministic algorithm Alg. Let A = G + sue he a fixed realization of the random matrix A. Recall = an. The algorithm Alg queries fixed orthonormal matrix Q(1) and
receives the response (1) = Q(1) vec(A) = Q()) + sQ() (u @ v) where we use g := vec(G).
As Alg is deterministic, in the second round it queries the matrix [r(]] We use ((2)rr() to emphasize that Alg picks Q(2) purely as a function of y((2), It receives the response y
((2)(p-(2) g + (Q(2)(r())) @ v) and picks queries (r.(1),,x(2) for the third round and so on. Using h() = (r(1) r()) to denote the history of the algorithm until the end of round j, we have for O,....t
((-)) == (15+ + s s.u v).
For each j = 1,... L, the randomness of A induces a distribution H1) over histories until round j. Then for and the distribution 4 = H []] { Alg after j rounds conditioned on u = u and v = v where the randomness in the histories is purely from the randomness of G. Recall that without loss of generality, queries made by the algorithm are orthogonal to each other. We first prove tail bound on the amount of information that non-adaptive query matrix can obtain.
u, v } is the distribution of the history of
assume all the general linear
B.1 A Tail Bound
Let and e be independent Gaussian random vectors. Let Q E RRxxn be an arbitrary matrix with orthonormal rows. We have the following lemma.
Lemma B.1. There is small enough universal constant such that for all k. 2 and C satisfying
4k < Ck S 16n?, we have any orthonormal matrix Q buxxn" that
Pr[l Q Σ 8 v.ll > Ck) < exp(-
Proof. By Theorem 1.4 and Remark 1.5 of [31], we have that
ct
PrllQ((u @ 2) 2 ||[]|= + +1 S exp
2n
for all 0 St 2n. Fort = Ck/4, for 4k < Ck < 16n², we have that
Pr|llQ(u 2)|l2 2 VCk < Pr u,v
Q 8 2)|l2
v
Ck/4
u
cCk
exp
8n
which implies, taking 8 = c/8, that Pro, blll & v)ll
Cki - exp(-BCk/m)
15

---

B.2
First Round
Let w(() be the distribution of (u, v) where u and v are random variables that are independently sampled from [O, I.). As already defined, the distribution of the history of the algorithm after the first round for a fixed u, o is given by HuV. We have that HWl is the distribution of the random variable
Q +t S.
Let P!l be the distribution of the above random variable (although P!! = H we distinguish plf) uu and H!l) in later rounds) and let p(1) { ( be the set of distributions for all Then we have
I(pi1), w(l) S E (( ( (Q sQ v) gl
S 8 E (i 110 () (a² /n)kr.
We define the loss function
0 Qf @ v)l 2 fi(a, 7) = Q @ o) < fi 7)
{
Loss (1) ((u,
for Q E Rxxx with orthonormal rows and some function fila, 7) satisfying 4 S fi(a,)) s 16n for parameter 1. From Lemma B.I, we have
(Loss (t) (w)) 2 1 exp(-$fi(an)k/m)
which implies
Bayes 1 (a²/n) + log(2)
(f,(a,,)):// + log(2)
Picking (i(a,))= Ka2?², we have that RBayes - 1/(0002)) Thus with probability 1- 1-1/(10))
over (u, v) w(!), we have that
Pr A (
(2) Ih [( @ v)1 fi k) 2 1/(107)
Let ()) be the set of all (u, v) that satisfy the above property. Let (2 be the distribution of (u, v) ~ w(!) conditioned on (u, v) E Good(!) For each (u, u) E Good let
GoodH (L) inl (2 (n 1) (1, 7)k}
We have for all (u,v) v) E (ood that Pr Ih (1) GoodH > 1 - 1/(10>). The overall conclusion of this is that with a large probability over (u, v) ~ (1) the squared projection of u @ on the query asked by Alg in round 2 small with large probability over G.
B.3 Further Rounds
We first define the following objects inductively.
1. For 2 2, let w(() be the distribution of (u, v) ~ wG-11 conditioned on (u, v) E (5)d So w) is the distribution over only those inputs for which the squared projection
of (8 u on the query space of Alg until round j is small with high probability over G.
2. For (u, v) G-1d
p(i = uu
distribution of h () = (h (i-1) r()i) ~ H(U conditioned on h (1-1) E GoodH(/1) un
p denotes the distribution over histories after round j. conditioned on the queries used until round j not having lot of "information" about
3. Let p() { (P()) (u, v) (o }.
16

---

4. For j 2 1,
Good =
(u, u) E Good(/-1)
Pr K
[IQU+U w)ll < ((a,)))))))))))) - 1/(10))) }
The Good!o denotes those values of (u, v) for which with large probability over G, the queries used by the algorithm until round j + do not have a lot of "information" about u @ v.
5. For (u, Good
GoodH
uu == (hC) = (11611) v() 11-1)) E GoodH(/-1) and [|Q(++)) @ e)12 < ()(a,
GoodH denotes those histories, for which the queries used by the algorithm until round ue
1 do not have lot of "information" about @
6. Let fo K and for j 1, let fa( Ka²>2fz-1(a,, 7) for large enough universal constant K.
Lemma B.2. For all 1 S j satissying fa 7) $ 16n
1.
Pr [(u, E Good! (,,0)~=()))
107
2. For all (u, v) E G))d
Pr hGAP66)
10y uv. () GoodH 21
1
3.
E( (dxL(P!))) [[ s (k//)).
where GU) the joint distribution of independent k-dimensional Gaussian random variables.
Proof. From the previous section, all the above statements hold for j = 1. Now assume that all 1. We prove the statements inductively for round j.
the above statements hold for rounds ...... . Recall w is defined be the distribution of (u, v) wb-11 conditioned on (u, v) Go-d For cach (u, v) E Good we now bound d( GG)), By definition,
d( d(p()) (GD) = dkL((h 6-11) 00 ||( (1) 9
where h0 = (11) vا) ~ p(ù) Note that the marginal distribution of (011) given by conditioning the distribution p the event GoodH(i-1) By Lemma A.4, have
(k2 0-1) ( (( (1)
.....gh! (1)
dkI (1-1) 1[ (1) 9 ))))))) + E,,0-1 [dKL (1 11
dkI.((P66 ((p(()())))))))) GoodH "))(0(11)))) B pli pli- GoodH( [dki. ((r (()())
(6)
Now, using Lemma A.3, we have
deL (P!) ( +2
dxL ((P(( Go <
Prao !~ 1) 1-111 E GoodH(-11
< (5/4)dkz uu (() 5/2.
17

---

Here we used the inductive assumption that Pr 1) (h011) GoodH 2 1
1/(107) 2 9/10 where the last inequality follows as the parameter y 2 1. Next, we upper bound the second term in (6), We have that r00 r (111) Q6 (1 "(g++ ( is distributed as (( ( @ v), Ix) by rotational invariance of the Gaussian distribution. Therefore, ( dx ((r 63 h (19 ) (1/2) (1 & w)113 I (d2/n)5s-1(0;)))
In the last inequality, we used the fact that h 1-1) GoodH uv Finally,
[d(P id(Pud | < (5/4) o) dKL (Plt 1 5/2 + a² ()- - (5/2) () deL (P nu
( + 5/2 + a² f- 7))
as the distribution w(() is obtained by conditioning ((-11 on an event with probability 2 1 1/(10)) 2 1/2 and dki. (-Il-) 2 0. Now, using the inductive assumption, we have
Fl (d( ((P())) [|G()]] < (5/9)])-((4 5/2
S 2a 22 ())((a)))) - f) (k/n))
where we use a 2 15. This proves the third statement in the lemma for round j. We also have, [wl(i, p()) < ((,,))))()) [d[ ((P))) |G s 2a (k/n). We now define loss function LG) and use Bayes risk lower bounds to prove the remaining statements. Let
Loss Loss v), = {1 if [QQ @ v)13 - fj(a,))) if | @ w)1l ff(a,7)k:
where Q TR is an orthonormal matrix with n rows. We have for such that 1j(a,7)b S 16n². Ro (L w()) inf ((. [Loss ((u, Q)1 2 (11 kk/m))
Q
where we use Lemma B.1 and the fact that the distribution w()) is obtained by conditioning w1() on
an event with probability 2 (1 - 1/(10))) which we prove in section B.4. By the generalized Fano inequality, we obtain
Raayes (Loss wi)) 2 + ((w))))p())) + log(2)
log(1 Ro Loss (i) (())
2a. fī-1 7 /k/ log(2)
2 1 Bf (laa,,)k//nnn) + log(1 - 1/(00>))
As = and fo(a, 7) 2 K for a large enough constant K, we have and therefore for K large enough,
(fʃ(,,7) 110 log(1 1/(10)))
Bayes (Loss () ()) 21 100
By definition of Raaess, we conclude that
( [ P00 [Lsss(u, v), Q0+1)) 2 1- 1/(1007
By Markov's inequality, we have that with probability 2 1 1 1111(107) over (u, v) ~ w(), holds that
E P [Loss( v), (1 [1)] 1/(10>)
which is equivalent to
Pr (n @ v)ll < fa 7)ж N 1 - 1/(10y). P()
Thus, we conclude that Pr (u m)) [uu v) Good 11) 2 1 1/(10>) and that for (u, v) G))
we have Pr, x(0) Ih e GoodH wt!
> 1 1/(107).
18

---

B.4 Wrap-up
Let have
satisfy 7)),, 16n By definition, Good C Good(-1) C ... Good!)) We also
w (oo-")GGodd = w Good
Now, using the fact that Good ( Goodli-1)
(1 [u,, v) Goodl
(,, [u, v) E Goo v) Good Pf( [ [u. v) Good (u.))wa)))
Pr
As w()) = w(() (o we have
Pr [1u, v) E Good (u, v) E 11 (u,v)mma(1)
Pr [(, v) E Goodl (u.e)~w(1))
2 (1 - 1/(107))
where the last inequality is from Lemma B.2. Thus, PE( ((2,,) Good 2 (1 1/(107))) Similarly, for (u,o) v) E (ood we have that
Prnw (1) GoodH
Pr (h) E GoodH
Pr A (1-1)
GoodH (1-1)
M(1)
we
(1-11/10 (1-1/(107))
where again, the last inequality follows from Lemma B.2. Thus, Pr # (h() E GoodH () 2
(1 - 1/(10>)). Now, for (u, v) ~ w(l) and () ~ H() we have that with probability 2 (1 1/(10>)) it holds that (u, v) E Good and h GoodH(i). Thus, with probability (1
1/(107)) over the input matrix G i=1 u.o we have that
10 1 0) < Σ [a 7)k s (5, 7)k.
With probability 2 1 - 1/ (n)y using Lemma B.I, (Q(00) (u & w)1 $ A log(n). Using union bound, we obtain that with probability 2 1/(10>)) 1/ (n),
100'+1) [( @ w) < 2// 7)k + Kk log(n)
2kfola, () (Ka2 + Kklog(n)
= (3))
where is a large enough absolute constant which proves the theorem for j such that (Ka? ((log(n)).
C Proof of Theorem 3.2
Suppose Alg is a t round algorithm that uses & liner measurements in each round such that when run on the matrix G + (ne//, it produces a matrix À such that with probability 9/10 over the input matrix,
A - uv 5
for small enough constant By making the algorithm query the vector vec( in round t we can therefore ensure that Q is the overall query space of the algorithm, then
PrillQ(u & e) 2 n² /100 2 4/5.
19

---

By Lemma 3.1, obtain that + ((log(n2/4)/(oggll log log and hence (logg(n2 (k))////////aaa)))// + log n)).
Now suppose Alg, is é round algorithm that uses k linear measurements of the input random matrix G (a/vi) Ei=1 iadi and outputs a matrix À such that with probability 2 9/10 over the inpur,
1 Σ i.
S cn²r
for a small enough constant e. We obtain a lower bound on by reducing the rank-1 1 plant estimation problem to the rank-r plant estimation problem. Suppose the input is the random matrix G (a/ / We sample ug,..., ....
Ur and U2,..... Vr so that the coordinates of these vectors are independent standard Gaussian random variables. Now we note that we can perform arbitrary linear measurements the matrix G+ G+(aaV/i (T) Σn= u since we have access to linear measurements of G + (a/ Vn)uz and we know the vectors U2 up and U2..... Vr. We can then use Algorithm Alg, to obtain a matrix Á such that with probability 2 9/10 over the input and our sampled vectors,
Σ u
-Alli S en²r.
Condition on this event. We have І [A] S 1 - All < en2r which then implies || u.u! -[A]-lIi s 2en3r. Now, let P be the most rank r projection matrix onto the rowspace of the matrix [A], and assume that U and V are matrices with columns given by U1....; U, and vi...., respectively. From above, we get
(T & LUV - [A]r S 2
which then implies that
P)] (I 2en2r.
Mmin
Now, U is an X r matrix with coordinates being independent standard Gaussian random variables.
We have from [26] that if S n/2, then with probability
exp(-n)) m (U) 2 Ci /n. From
[17] also have that with probability > 11 1- exp(-n), c2n < || 12 . [u2 < Cn for a small
enough 0g and large enough C. Conditioned on all these events, we have
(1- P)
< On
[1- P)
t=1
< <I -I < (2mn²r)(Cn) < (26C/c1)n2.
Gn
Hence, at least 9r 11 indices i have the property that (I- (20cC/e))n) )n2 Since the marginal distributions of datn ..... U, -..T are identical, we obtain that with probability 2 8/10,
|u I P)1 < (20cC/e2)n².
Note that rank of P is at most and therefore P QQT for orthonormal matrix Q with at most columns. In the (t + 1) round, we make nr linear measurements the input matrix and obtain the matrix
GQ + (a/vTjuuu
and therefore, we can obtain the matrix M = GP + (a/T////// [M] be the best rank-1 approximation of M in operator norm. We have
[[[M]] (a/ /ne/uulll s [[[M]: M|1a + I|M -
(a/ (a/Vo)uooll
< GGP|| + |GP||| + (a/ (a/vn) (20cC/co)n2
Since, |G]|| < 2/n with probability 1 - exp(- we get
[ - - u < (4/a + / 220cC/c.m
20

---

and
[[Va/a)[M]i- u & 244/a 2 220C//a)))
For large enough and e small enough, by querying the vector veo([M]1)) we can again ensure that if Q is the query space of the algorithm after t + rounds, we have with probability 2 1/2 over the input random matrix that
IQ(uı @ m1)1 2 n²/11 /000.
We again have from Lemma 3.1 that + 2(log (1 /k) (log log + log ax) and therefore that 1 (allogn"/bb/CCe log n + a)g
D Proof of Theorem 1.1 using Theorem 3.2
Let A be any any randomized algorithm that queries orthonormal measurements of the underlying matrix A and outputs reconstruction Á of A satisfying ||-A - All < cl|AI] with probability 2 p. over both the randomness of the algorithm and randomness the measurements. Let Á A(A, where a captures the randomness of the algorithm and captures the randomness in measurements. First we have the following lemma.
Lemma D.1. there is a randomized algorithm A(A, o, 7) such that for all rank matrices A with | | = (nr).
Pr PrIlA(A,0,7) - AIÀ S c|AI|| N P.
0.7
then there is a randomized algorithm A' such that for all A with | O(nr).
Pr [l Alli S c|AI| 2p.
G
Proof. Fix a particular a. The algorithm first queries an orthonormal matrix Q R and receives a random response (()) Q(1). vve(A) + (()) where gf is a vector with independent Gaussian components of mean 0 and variance 1. As function of (1), the algorithm queries an orthonormal matrix (1)() and receives the random response (2) = (r2) vec(A) g(2) where g (2) is again a random Gaussian vector independent of g (1), Importantly,
also have that Q(2) y (1) is orthogonal to the query matrix (() in the first round. The algorithm proceeds in further rounds accordingly where it picks query matrices as a function the responses in all the previous rounds.
Let G be an n x Gaussian matrix with independent entries of mean 0 and variance 1. We now observe that (1) of Gaussian distribution. Now conditioning on (1), obtain that (2) (r)) vec(A) g
has the same distribution as (()) vec(A+G()))) by rotational invariance
has the same distribution as Q(2) (r(()) vee( A + G) as (x() is orthogonal ((1) and hence ((2)(r g independent of (1)) g. again by rotational invariance.
Thus, we can consider a deterministic algorithm A' parameterized by the same a which exactly simulates the behavior of AA performing matrix recovery with noisy measurements. Thus,
PrIlIA'(A G. .) - All < c||A||i] = Pr]lI All < c|lA G
7
Taking expectation over we obtain the result.
Let uy..... u, and U1..... V, be random vectors with coordinates being independent standard normal random variables. Let U be an n x matrix with columns given by uı,..., and V be an n r matrix with columns given by UI,
Claim D.2. If n/2, With high probability,
=
u,
21

---

Proof. Clearly, UV Σ ..d! We have 2nr > | > nr/2 with probability 1 exp(= from [17]. From [26], with probability constant e and as seen in preliminaries, | - n. Thus, conditioned on both these events,
exp( (n)) min z cvn for
|UV 2 min V 2 en(ur (2) 2 (c/2)n²r
and
JUV < | < 8n²r.
Hence |1(a///) Ei= u. = (nr) with large probability. Now, we obtain that
Pr [1(A v Σ Z + -aavv(a/Vn)
Z.u /2 s cll(a/ VT) Σ u. [[
u.v.G,o
(1 cxp(xp((-(n))
Thus, there is some such that
Pr [llAA(aaa///) E iad -G,o) Σ u ccl(a//n)) Σ u 2 p(1 exp(--(n))))
u.e.G
Thus with probability 2 p(1 exp(-O(n))).
IKV7/a)A(((a//n) Σ Ian + G. Σ uu - 2cn2r.
By picking e small enough, we obtain that f ((log(n2) /k/)///////// log log n) for algorithms with success probability p 2 9/10.
E
Applications to Other Problems
E.1 Spectral Low Rank Approximation
Theorem E.1. Given n, LE, a t-round adaptive algorithm that performs k Z nr general linear measurements in each round is such that for every n X matrix A, the algorithm outputs rank
log(n (r2 (k).
matrix B such that with probability 2 99 100, I|A
Bll2 S 20,+1 then t
c log log(n)
We prove the following helper lemma that we use in our proof.
Lemma E.2. If A is rank-r matrix and B is arbitrary matrix satisfying ||A Bll2 then
||A [B]|Il < 2t, where [ denotes the best rank-r approximation of the matrix B in operator norm.
Proof. As A has rank at most r, we have 2 ||A - BlI2 2 B [B, Thus, ||A- [B]rll S ||A 1A--Bl22- IB [B]rlla < 2t.
Proof of Theorem E.I. By standard reduction, it suffices to show that there is distribution on x n matrices for which any t-round deterministic algorithm which makes general linear measurements in each round and outputs 2-approximate spectral rank approximation satisfies t 2 clog(n2/ //)/ log log(n).
Consider the random matrix M G+sue for 500/vm Suppose there is deterministic t-round algorithm Alg that makes k linear measurements and outputs rank-r matrix Alg(M) such that with probability 99/100,
M
Kl|2 < 20, (M) 2|
This implies that ||sueT T - K|12 < 3 Gl|2 and Tanll - K/s|12 - ////
With probability 1 exp(-0
have 2/7z fu/|2///o|la vn/2 and | 12 3/n
simultaneously. By union bound, we have that with probability 0.98, -
-K/s||2 (9/500)n.
22

---

By Lemma 1, we have | (ee7-[[//// -K///] 122 S (9/250)n which implies that 1 1
| T [K/s],ll S 2|lu0* [K/s]1ll2 S (99/250)²n² where used the fact that the matrix uo K//s] has rank at most 2. Let E Rn vec vec((///// (K/s)))/|[ || be unit vector. We can
show that
(g. & 0) 2 n /64
by simple application of the triangle incquality. Thus, using Alg t ++ round algorithm such that the squared projection of u @ v onto the query space is at least 2 n²/66 /64 with probability 2 98/ / 100. By (4), we have that 1 c' log(n") ( /k) log log(n) and therefore we have t 2 clog(n? /k) log log(n) for a small enough constant c.
construct deterministic
The following theorem states our lower bound for algorithms which output spectral LRA for each matrix with high probability.
Theorem E.3. Given n, r Z, a t-round adaptive algorithm that performs k 2 general linear measurements in each round is such that for every n x n. matrix A, the algorithu outputs a rank r matrix B such that with probability 1- poly(n), (n), || B||2 I 20,+1(A) then 2 clog(n2 /k).
Proof of Theorem E.3. The proof of this lemma is similar to that of Theorem E.1. The existence of randomized round algorithm that outputs 2-approximate spectral norm LRA for every instance with probability
1-1, 1/ poly(n) (n) implies the existence of deterministic algorithm that outputs a 2-approximate spectral norm LRA with probability 2 1 - 1/ poly(n) over the distribution of G + (a/ Vn)uv" As in the proof of the Theorem E.I, this algorithm can be used to construct a f + 1 round algorithm that with probability 2 1/ unit vector g satisfying
1/ poly(n) over the matrix G + (ar/ /n)wo", computes
(4, @ u) 2 n² /64.
Now, (5) implies that L +1 e clog(n?/ //k) for a small enough constant c.
For the random matrix M = = ua for a large enough constant a considered in the above theorem, we have that matrix
()) 2 2 with high probability, Now consider the random
M' = M
O 3
0
With high probability, we have o, (M') = (M) 2 (a/2) and I (M') =M')= (2 S 2/n implying 0,++ (.+1(11)))) (M'')aa < 1/2. A proof similar to that of the above theorem now shows that algorithms using Z nr general linear measurements in each round and outputting a 2-approximate rank-r LRA with probability 2 1- 1/ poly(n) for matrices M with 0++1 (M)/o, a lower bound of (log(nn2/8))
S 1/2 have rounds. Moreover for & 2 C're for a large enough constant and O(),, the randomized subspace iteration algorithm starting with subspace of k/n */n-dimensions, after Ollog(z n² /k)) rounds outputs, with probability 2 1 1/ (nly(n), a 2-approximate rank-r spectral norm LRA for all matrices satisfying 0, (M (M) 1/2. See [12, Theorem 5.8] for proof.
Note that the subspace iteration algorithm starting with subspace of k/n-dimensionss performs (k/n). . n general linear measurements in each round. Thus for = 0(1) and k 2 Cnr for a large enough constant C, the lower bound of (2(log(12)) 2/k)) rounds for high probability spectral norm LRA algorithms for "well-conditioned" (0,4//o, < 1/2) instances is tight up to constant factors and shows that general linear measurements offer no improvement over matrix-vector products for well-conditioned problems. Thus we have the following theorem.
Theorem E.4. Any randomized t-round algorithm that with probability > 1 - 1111/ poly (n) outputs 2-approximate rank-r spectral norm LRA for any arbitrary matrix A satisfying o (A)) (A)) 2 2, must have t = 2(log(n /k))), where k 2 nr is the number of linear measurements the algorithu makes in each round.
Moreover, for r O(1), the subspuce iteration algorithm [12] matches the lower bound up to con- stant factors and outputs a 2-approximate spectral norm LRA for all such instances with probability z 1 - 1/ poly(n) in O(log(n') /k)) rounds.
23

---

E.2 Symmetric Spectral Norm Low Rank Approximation
An interesting property of the hard distributions from previous works [28, 3] is that those distributions supported symmetric matrices and they hence obtain lower bounds for algorithms that work even only on symmetric instances. Although our hard distribution is non-symmetric, we can construct distribution supported only on symmetric matrices and show lower bounds algorithms using generalized linear queries for symmetric matrices.
Theorem E.5. Given n. E. t-round adaptive algorithm that performs k 2 general linear measurements in each round is such that for every n x n matrix A. the algorithm outputs a rank 2 2 matrix B such that with probability 2 99/1100, ||
BII2 S 20.++ (A), then t
log(n2/A (k) log log
Proof.
Consider the 2n x 2n random matrix M' defined as
Onxx M
M'
M
Onxn
where M G swn for 500/vn and all coordinates of G, u, are independent standard
Gaussian random variables. We have that for i E [n]. ( any arbitrary generalized linear measurements of the matrix M' can be simulated using 2k general linear measurements of M. Now suppose an algorithm that uses k general linear measurements in each round outputs rank r 2 2 matrix satisfying
(22(M) = 7:(M) and that
|M' K| 20,+1(MM) 20, (M..
Let the matrix K be the form
Ki
K2
K
K3
Ka
As any sub-matrix of K has rank at most that of K, obtain that K2 is rank-r matrix satisfying
|| - K2lla I (M.)
Thus, the existence of t-round deterministic algorithm that uses generalized queries in each round and outputs a constant factor approximation of rank spectral norm LRA, for the random matrix M' with probability 2 99/100 implies the existence of f-round algorithm that uses 2k generalized queries in each round and outputs constant factor approximation of rank-r spectral norm LRA for the random matrix M with probability 2 99/100. Now, as in the proof of Theorem 1. we obtain that
log( (g(nn//2k) /2k)
log(n? /k) log log n
log log
We obtain the proof by appropriately scaling the statement.
The above theorem proves lower bounds for algorithms that solve constant factor rank-r spectral norm Low Rank Approximation (LRA) for all r 2 2 even for symmetric instances. This leaves open just lower bound on algorithms solving rank 1 spectral norm LRA for symmetric instances.
E.3 Schatten Norm Low Rank Approximation
We first note the following lemma which bounds the Schatten-p norm of an n x Gaussian matrix. Lemma E.6 (Equation 3.3 in [19]). If is an n x n matrix with independent entries sampled from (0, 1) and p 2 2, then with probability 2 9/10, |[G||s, S 30n 1/+1/p
We now state the theorem that shows lower bounds for Schatten norm low rank approximation. Theorem E.7. Given n, r E Z,, if a t-round adaptive algorithm that performs k ' nr general linear measurements in each round is such that for every n matrix A, the algorithm outputs rank matrix B such that with probability 2 99/100 we have
| Blls, < 2 min nank X I|A
Xlls, 1|--XI1s..
then
log(n² (n² 2/222/0 /k)
2 + (1/p) log(n) + log log(n)
24

---

Proof. The proof is very similar the proof of Theorem E.1. Let M G sunt for == v for a to be chosen later. Let Alg be t-round deterministic algorithm that outputs a 2-approximate Schatten p-norm low rank approximation for M with probability 2 99/ 100 over M. Then we have
G||s,
|| lue K/s|| -
as miD || + suv xxls, - |G]|s, Using Lemma E.6, with probability 2 9/10 over M, we have that
Σ i K/slls, S 90n 11/p////
By picking a Bn for large enough constant B, we obtain that
luv K/s|l2 & |uvl - K/slls, I (9/250)n.
Similar the proof of Theorem E.I, we can construct unit vector g R²² such that with probability 2 8/10 over M, we have
(a, u & u)² 2 n² /64.
Using (4), we obtain that
log(n2/h) /k)
(ng(n" /k)) (1/p) log(n) log log(n)
1+ c 1 log(a) + log log(n)
In particular, for p (l)og(n)/ log log(n)), this gives a lower bound of (p((2 log(k)/ log(n)))
on number of adaptive rounds required if an algorithm can query & general linear measurements in each round. Recently, Bakshi, Clarkson and Woodruff [2, Algorithm 2] gave algorithm for Schatten-p low rank approximation for arbitrary matrices that runs in Opp log(n))* iterations to output constant factor approximation. For instances with a, (A)/o,+1 (A) = 1 + 2211, Saibaba [27, Theorem 8] showed that randomized subspace iteration gives constant factor approximation to rank-r Schatten-p norm LRA in Ollog(n) iterations using nr linear measurements in each round.
E,4 Ky-Fan Norm Low Rank Approximation
Theorem E.8. Given n, r E Z. if a L-round adaptive algorithm that performs k 2 nr general linear measurements in each round such that, for every n. matrix A, the algorithm outputs rank-r matrix B such that with probability 2 99/100 we have
|| B Fl < min 1|A - X Fl
rank- X
then
log(n2/8)
t 2 log(p) + log log(n)
Proof. Again consider the same instance M = G + swvt with a/ an for chosen later. If K a 2-approximate rank-r low rank approximation of M in Ky-Fan p norm, then
G + swe -K]F, < G||
which by the triangle inequality implies that ||s Σx= p - K 33| As ||]||2 $ 2 with high probability, have that ||G]|F, I 2p n with high probability. Thus,
Tas - K/s|12 S Is Σ I - K/s/lr, < 6pm
"Although their algorithm is stated to 2/2 log2(n) matrix-vector products, this does appear have been optimized, and looking at the analysis it runs in at most //2 log(n) iterations, where each round queries at most matrix- vector products.
25

---

Picking a Bp for large enough constant B, obtain that using the matrix K, construct a unit vector g such that (q, u 6 u)² 2 n²/66 /64, thus showing
log(n2/K)
log(p) log log(n))
round lower bound any algorithm that performs k general linear measurements output 2-approximate rank-r approximation in Ky-Fan p norm.
For (1), the Block Krylov iteration algorithm [20] gives an O(1) approximate solution to the rank-r Ky-Fan norm low rank approximation problem in (log(n)) rounds while querying or general linear measurements in each round. Thus our lower bound on constant approximate algorithms for Ky-Fan norm LRA is optimal up to log log(n) factor for r, = O(1).
E,5 Frobenius Norm Low Rank Approximation
Theorem E.9. Given
matrix A with 0n (A)/o2(A) > if t-round algorithm outputs rank-1 matrix B satisfying || - BlI & (1 + 1/m [| [A]il] with prohability 2 99/100, then we have t 2 clog(n" / log log(n).
First, we prove the following helper lemma. Lemma E.10. Given A E Raxn, if rank matrix B is 1/(n r) approximate rank Frobenius norm LRA, then
|| - B E 20, 20))
Proof. We use the fact [12, Theoem 3.4] that if rank matrix satisfies || [|)-[A],]]
then A BI < [|A-[[]] [A) + is a (nn11nnn/ approximate solution for rank Frobenius
norm LRA, we have
| BlI <
1
I|A [AA]-IÍ
$ ||A [A], 11 + Tr+1 (A)2 +... + on (A)2
--
< ||A [A] + +o++1 (A)²
which implies ||A B - ||4 - [A], 1 + (11) = (
Proof of Theorem E.9. Using the above lemma, have that whenever IA- (1+1/n)]|A-
[A] for rank matrix B, then || B < 2 BIB.. Consider the random matrix M = G + (a/ /n)uuT considered in Theorem E. With probability 2 99/100, we have that a (M) 2 2 by picking a to be large enough constant.
(-round randomized algorithm for (1 (1+1/n)-approxine -apprxximate rank-1 Frobenius norm LRA thus implies the existence of a (t + round deterministic algorithm that with probability 2 98/100 over the random matrix G (a/ V makes general queries such that the squared projection of u onto the query space of the algorithm exceeds n² /64 using similar arguments as in proof of Theorem E. Now, using (4), we obtain that
1 clog(n²/R)) log log(n)
for small enough constant c.
For matrices A with a (A)/oz(A) 2, subspace iteration algorithm gives a + 11/n-approxiiiet solution in ((lg(()) rounds using n-linear measurements [10, 20J. The above lower bound shows that if an algorithm allowed o (Iog(n)) log log(n)) adaptive rounds, then the algorithm has to make 2)2-((1) linear measurements each round, which is almost as many measurements required to read the entire matrix.
26

---

E.6 Lower Bound for Reduced-Rand Regression in Spectral Norm
Given matrices A, B, and a rank parameter r, the reduced-ranke regression problem in spectral norm defined as
min rank-r X
|AX
B12-
Taking A = I, we have that the spectral norm low rank approximation a special case of the reduced- rank regression problem. Thus have the following lower bound the number of rounds of an adaptive algorithm that outputs a 2-approximate solution for the reduced-rank regression problem.
Theorem E.11. If a t-round adaptive algorithm which given arbitrary n. x n matrices A, B and parameter r outputs 2-approxinate solution for the reduced taank regression problem with probabil- ity 2 9/10, then Mlog(n² /k) log log(n)) where is the number of linear measurements of the matrices A and B that the aduptive algorithm performs in each of the L rounds.
With nr adaptive linear measurements in each round, the above theorem gives lower bound of ([log(n/r)) log log(n)) on the number of rounds required to obtain a factor 2 approximation. Kacham and Woodruff [15] give an algorithm for reduced-rank regression that outputs constant factor approximations to the reduced-rank problem in (poly [[ooly(log/u n:) (ignoring polylogarithmic factors from condition numbers) adaptive rounds using nr linear measurements in each round.
If the matrix B = M + P has the structure of a planted matrix studied in this paper with P being rank r matrix and ||||2 > 10 [B] and if the matrix well conditioned, then we can find an (1) approximate solution to reduced-rank regression problem in (log((n) + log(1) ( (12/OPT)) rounds, where OPT the optimal value of the reduced-rad -ran regression problem.
First, we find a rank r matrix P' such that | - P'I|2 < B [B]rlla in O(log(n) adaptive rounds using the Block Krylov iteration algorithm of [20], which queries linear measurements in each round. Now, for any matrix X,
||AX P' = AX B112 + B 1'11 ||AX B112 = OPT.
Let P' = USVT be the singular value decomposition with matrix UE having columns. Then using high precision regression routines (see [33] and references therein), we find matrix X such that
|AX AA+UEI
=||>>| V 10re||P112.
in 0(log(1/e) /e)) iterations, where each iteration queries nr linear measurements. Again, using the triangle inequality, have
||ÄVV P'Il = ||X UE|12 < |AAUUE - UE
If X* is the optimal solution for the reduced rank regression problem, we have
I = ||AA + UEVT UEVV
||AX" - -P'112
||XX - B1I2 + 2 OPT = OPPT
We also have | AX||2 < |AA+US AXI|F S O(Vre( We (OPT/[PP|2)>/K<> /r for a large enough constant K and obtain that |AAAUE- AX S OPT. Overall, we have |AÄVT Bl|2 < | - P'Il2 + OPT < OPT. Thus we obtain approximate solution in ((log(n)
(PP)) iterations given that A is well-conditioned and B is of the form M + P with |||| 2 10 [0]Ml| 2/2 for a rank matrix P. Thus the lower bound is near optimal for algorithms that output (l)) approximate solution for planted models and well-conditioned coefficient matrices.
E.7 Lower Bound for Approximating the i-th Singular Vectors
Theorem F.12. Ifa t-round algorithm, given n x n matrix A and i [m)], outputs unit vectors vl. and vy such that with probability 9/10.
||44 - u,112 < 1/10 and Dlll/ - vell2 S 1/10
27

---

where ui and oi are respectively the i-th left and right singular vectors of the matrix A, then t t= =(lgggnn) 2 /k)/ log log(n)), where l is the number of linear measurements the algorithm performs on the matrix A in each of the rounds.
We also have a = M[ogg(2) (k)) lower bound on the number of rounds required for an adaptive algorithm to compute approximations to the i-th left and right singular vectors with probability 2 11--1 1/ poly(n).
Proof. Consider the n X n random matrix M = G (a/ Vn)uuT for a large enough constant o. The existence of a t-round algorithm as in the statement implies that there is deterministic t-round algorithm that outputs approximations to singular vectors of the matrix M with probability 2 9/10, We then have that ||||G]|| S [I(a//n)ww) /n)ww' ll2 and ||a]|2, ||o|22 2 v5/2 with large probability. Condition on this event. Let E R" be the top right singular vector of the matrix M. We have
(9/10) 10)ll(aa/ /V)uu ||2 = ((a//))uoTll 112 ||G||2 s
|| II(G + (a/ (a/vn)ww")or 101l/2
By the triangle inequality, we have I1(a/ he//Vnn)(vtir o1)ll2
II(G + (a//n)uuu ))1 ||uull
2 (//1))l((//m)ur) ll2 - (1/10)l((a/ /n)ua//
= (8/10) (a/vn)]lulllll))
Thus, we obtain that l0 [TT1l 2 4/5|/e/12. Similarly, if un is the top left singular vector, we have that |u un| > 4/5//uu|2 Suppose vf is a unit vector such that ||u - of [11 < 1/10. Then, |u 2 2lla 2 (7/10)||oll- Similarly, |u [TT1] 2 (7/10) which implies
lo byl - (wi & v 2 0)² = (u1, u) ()),,) ?= (49/100) ||| 2 n²/10.
Thus, with a large probability over the random matrix M. approximations to the top left and right singular vectors of the matrix M can be used to construct an n di-diimnniooaal unit vector g such that (q, u @ 0²² 2 n² /10. Thus, we have a t + round deterministic algorithm such that the squared projection of u @ v onto the query space of the algorithm 2 n²²/10 '10 with probability 2 8/10 over the random matrix M. Now, (4) implies that t constant c.
clog(n²/k) log log(n) for a small enough
To extend the above lower bound to approximating i-th singular vector for all S n/2, we can use the following instance:
M 0
0 S
M'
where M is the (n/2) (n/2) random matrix G (a/ (la////// n/2)wo= and S is a deterministic diagonal matrix chosen such that the top singular vectors of M correspond to i-th singular vectors of the matrix M'. If S is chosen to be the diagonal matrix with - 1 values equal of the entries are set to O, we have that with high probability that the i-th left and right singular vectors of M' correspond to the top left and right singular vectors of M as || 1|2 S 1 with high probability. Now the existence of a t-round randomized algorithm to approximate i-th left and right singular vectors of an n X n matrix for S n/2 with probability 2 9/10 implies
10 and the rest
that there is a deterministic t-round algorithm that approximates the top left and right singular vectors of the (n/2) x (n/2) matrix M with probability 2 8/10. From the above argument we have 1+1 1 = (0lloo(nn/2200000000000001000011 22/ / log log(n//)) = 2(log(n2) /k)/ log log(n)).
For 2 n/2, we can do a similar reduction. We have that the top left singular vector in of the (n/2) x (n/2) matrix Mi is same as the top singular (eigen-) vector of the matrix M M and with high probability is equal to the last singular (eigen-) vector of the matrix (100na²) MMM-MMM MM' Using the same trick as above, we can create an
matrix such that the i-th singular vector for i 2 n/2 corresponds to Un. Instead of MM T if we use the matrix M' T M, then we can make the top right singular vector U1 of the matrix M correspond to the i-th singular vector of an n X n matrix. Thus, for all i E [n], we have an M(log n /k) log log(n)) lower bound for any randomized algorithm that computes the i-th left and right singular vectors of an arbitrary n x n matrix A using k linear measurements of A in each round of the algorithm.
The lower bounds for algorithms that output approximations to singular vectors with probability > 1 1/ (nly(n) follow similarly using the high probability lower bounds from (5).
L
28

---

E.8 Lower Bounds for Sparse Matrices
The following theorem gives lower bound of (log(mm/k) rounds on adaptive algorithms that compute 2-approximate spectral norm LRA for matrices with most m nonzero entries.
Theorem E.13. Any l. round randomized algorithu that computes, given arbitrary with at most mn nonzero entries, 2-approximate runk r spectral norm LRA of with probability Z 1 1-1/ poly(m) (m). must have t [m (m/ (/)),, where k is the number of general linear measurements queried by the algorithm in each of the t rounds.
matrix A
Proof. We consider the distribution of the vm v /m random matrix G (a/m!//))) for large enough constant a and embed this instance into an n x n matrix. Clearly, all the matrices drawn from this distribution have most nonzero entries. And from Theorem E.3, any deterministic algorithm using& k linear measurements in each round and computing a 2-approximate spectral norm approximation for matrix drawn from this distribution, with probability use ((log(((mm) /k)) = [2(log(m/k) rounds.
1/ poly(m), must
Thus by Yao's minimax lemma, any randomized algorithm that outputs 2-approximate spectral norm approximation with probability 2 - 1/ poly(m) for an arbitrary matrix with m nonzero entries must use ((log(m/A) /)) rounds.
The above theorem implics that any algorithm with only O(1) adaptive rounds must query (2m) linear measurements. This lower bound tight up to constant factors with 2m linear measurements, since the m non-zero entries of any arbitrary matrix can be computed in just round using a Vandermonde matrix [8, Theorem 2.14].
29


Reviews:
[{"review_id": "471KRfPvPH", "reviewer": "Reviewer_NmzP", "summary": "This paper studies the problem of low-rank matrix reconstruction from linear measurements, which is a matrix generalization of the well known sparse reconstruction setting. The provide new lower bounds for this problem under different error metrics, such as the Frobenius norm, essentially showing that non-trivial reconstruction error is impossible unless $\\Omega(\\log n)$ adaptive rounds of measurements are made. The hard instance is a rank-1 matrix planted into i.i.d Gaussian noise.", "questions": "Is there any potential connection between this work and the hardness results used in [1] for matrix completion based on planted clique (or the references within)? Are there any implications for matrix completion?\n\n[1] Yudong Chen, Incoherence-Optimal Matrix Completion, IEEE Transactions on Information Theory, 2015", "limitations": "NA", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The problem solved is fundamental and to the best of my knowledge the contributions are new and generally applicable.\n- The technical steps are clearly explained and well written, and look sound.", "weaknesses": "- The presentation in Section 1 and 1.3 could be improved. While I like that the explanation goes into technical detail, it could be significantly improved by having an outline of the 2-3 most significant contributions and a more modular presentation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "- Thanks for the comments and question. Since the value of an entry of a matrix can be computed using a linear measurement, it is indeed true that lower bounds on linear measurements must also carry over to the matrix completion setting. As our lower bounds are in the “noisy” linear measurements model, they are not quite applicable to your reference that studies the recovery of exact matrices using the entries that are randomly observed. When there is no noise, an $n \\times n$ rank-$r$ matrix can be recovered using only $O(nr)$ linear measurements over two adaptive rounds as follows: In the first round, compute $AS$ where $S$ is an $n \\times O(r)$ matrix with independent Gaussian entries. Note that $AS$ can be computed using $O(nr)$ linear measurements. We can show that with a large probability $\\text{rank}(AS) = \\text{rank}(A)$ and hence the column space of $AS$ is the same as the column space of $A$. If then $U$ is an orthonormal basis for the column space of $A$, we can compute $U^T A$ using another $O(nr)$ linear measurements. So in the noiseless setting, we can recover the rank $r$ matrix using only $O(nr)$ linear measurements over 2 rounds as opposed to lower bounds in our setting that says one needs ~ $O(n^2)$ measurements if we want to recover the matrix in $o(\\log n/ \\log \\log n)$ rounds.\n\n- In the relevant setting of matrix recovery with noise (e.g., [1]), the previous works seem to study only very low noise regimes. So the tightness of the results cannot be inferred from our lower bounds.\n\n[1] Candes, Emmanuel J., and Yaniv Plan. \"Matrix completion with noise.\" Proceedings of the IEEE 98.6 (2010): 925-936.\n"}, {"review_id": "oQJvusbbWR", "reviewer": "Reviewer_m7zx", "summary": "\nIn this paper, the authors discuss the power of adaptive algorithms in low-rank approximation. This is a setting where one observes general linear measurements of a matrix and wants to produce the best r-rank approximation of it.\n\nIt is known that non-adaptive algorithms need order n^2 measurements and that with log n rounds a spectral algo works with nearly linear measurements.\n\nThe authors discuss whether something can be done with o(log n) rounds.\n## Contribution\n\nThe authors prove that for an algo that works with o(log n/log log n) rounds, we need order n^{2-o(1)} measurements.\n\n\n", "questions": "It seems that for the lower bound the authors only assume that the target matrix is r-rank Gaussian spike plus Gaussian noise. Is that true? \n\nIf so, please highlight it as this is a rather simple \"bad\" example to build a lower bound, which makes the result even more appealing.", "limitations": "See above.", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "The authors point to the interesting importance of having access to approx log n rounds, as they prove that having access to o(log n/log log n) rounds is like having one round in terms of measurement complexity. I find the contribution clean, correct, and interesting. ", "weaknesses": "It is a little bit disappointing that the authors cannot only assume o(log n) rounds, and need to assume o(log n/log log n) rounds. Could they comment more on that weakness?\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "- $o(\\log n)$ vs $o(\\log n / \\log\\log n)$: Our Bayes risk analysis, which union bounds over the information growth in each of the rounds, is what leads to the $\\Omega(\\log n/\\log \\log n)$ rounds lower bounds instead of the more desirable $\\Omega(\\log n)$ rounds lower bound. However, we do note that, as stated in Eq (5), if we want algorithms that succeed with probability $\\ge 1 - 1/\\text{poly}(n)$, we can obtain an $\\Omega(\\log n)$ adaptive round lower bound on any algorithm that uses $n^{2 - \\beta}$ linear measurements in each round. \n- Hard instance being rank-$r$ gaussian + Gaussian: Yes, the distribution of matrices for which we prove the lower bound is a rank-$r$ Gaussian (sum of $r$ outer products of independent Gaussian vectors) + another Gaussian. We will highlight this. \n"}, {"review_id": "8jSiKiV4hn", "reviewer": "Reviewer_cbbb", "summary": "This paper focuses on investigating the lower bound of the adaptive low-rank matrix sensing problem. Specifically, the authors demonstrate that when the noise level significantly exceeds the signal, any adaptive algorithm requiring fewer than $o(\\log(n)/\\log\\log n)$ rounds must utilize at least $\\Omega(n^2)$ linear measurements in total. This finding highlights an intriguing trade-off between the number of measurements and the number of rounds in various matrix sensing problems within numerical linear algebra.\n\nThe paper presents a clear message, and the theoretical results are robust and captivating. However, one aspect worth considering is the general interest in the noise level examined in this study.", "questions": "The authors make an assumption that $M^{(i)}$ represents an orthonormal basis and argue that this assumption does not affect the generality of their approach due to the possibility of a change of basis. However, it is important to consider whether this change of basis has any impact on the homogeneous noise level, i.e., $Ag$ for a Gaussian vector $g$ is not a homogeneous Gaussian vector anymore if $A$ is not unitary. It would be valuable for the authors to provide further elaboration on this point.", "limitations": "I do not forsee any potential negative societal impact of this work. ", "rating": 5, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "- The theoretical results are very sound\n- The presentation is very clean and easy to follow\n- The adaptive settings of matrix recovery is of general interest", "weaknesses": "This paper examines the case where the noise level is assumed to be $O(1)$, while the signal of each entry is considered to be $O(1/\\sqrt{N})$. It is worth noting that in a more typical scenario where both signals and noises are of magnitude $O(1)$, a single round with $\\Omega(nr)$ measurements, as presented in [5], would suffice. This raises questions about the significance of studying this extreme case and the role that $\\sigma_l$ plays in the lower-bound tradeoff.\n\nTo provide more justifications for studying this extreme case, it would be beneficial for the authors to elaborate on the motivations and implications behind their choice of noise and signal levels. By offering insights into why this specific scenario is relevant and shedding light on the insights gained from this extreme case analysis, the authors can strengthen the value and message of their paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "- Noise level: You are correct that the lower bounds we study are in the high-noise regime. A main reason for this is that adaptivity does not reduce the number of linear measurements by a large factor in the low noise regime since the non-adaptive sensing algorithms already recover the low rank matrix using a number of linear measurements of approximately $O(nr)$, up to some small multiplicative factors. So, it does seem that  adaptive algorithms are majorly helpful only in the high noise regime, which is where the study of measurements vs rounds tradeoff becomes interesting. While not exactly related to matrix recovery, [1] studies the performance of data-aware projection algorithms when the matrix is corrupted with a large noise.\n- Orthonormality of the measurements: We will elaborate on this. You are correct that the assumption about orthonormal measurements is not without loss of generality. For example, the standard assumptions in matrix recovery allow the same linear measurement to be performed multiple times and obtain results with independent noise in each of the measurements whereas our lower bounds which assume that the measurements are orthonormal does not account for this scenario. We will emphasize this in the next version. We do note that this loss of generality is not an issue for the lower bounds that we present for other problems such as spectral norm low rank approximation, etc.\n\n[1] Abdullah, Amirali, et al. \"Spectral approaches to nearest neighbor search.\" 2014 IEEE 55th Annual Symposium on Foundations of Computer Science. IEEE, 2014.\n"}, {"review_id": "k7Zrlq2H7C", "reviewer": "Reviewer_Txfq", "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.\n\nThis 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.\n\nTechnically, 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.\n", "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? \n\n2. It would be better to show some known upper bounds for the problems in Table 1.\n\n3. Line 52: $M\\in \\mathbb{R}^{n\\times n} \\rightarrow \\mathbb{R}^t$. $t$ should be $k$.\n", "limitations": "N/A.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "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. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "- Uniform number of measurements: We note that our lower bound says that even when one is allowed $n^{2 - \\beta}$ linear measurements in *each* round, the algorithm must use $o(\\log n/ \\log \\log n)$ rounds to be able to approximate the matrix. So, allowing for the number of measurements to be adaptively chosen in each round does not seem to modify the results. \n- Known Upper bounds: In the appendix, we show that under certain conditions, the 2-approximate spectral norm approximation problem can be solved in $O(\\log n^2/k)$ rounds using $k$ linear measurements in each round using the subspace iteration algorithm. We will include a discussion in the paper on the upper bounds for other problems and add references to them.\n"}]

Author rebuttal:

Meta-review: In this paper, the authors investigated fundamental lower bounds for adaptive sensing in noisy low-rank matrix recovery problems, focusing on the interplay between adaptivity and sample complexity.  When the signal-to-noise is approaching the information-theoretic limit, it was shown previously that non-adaptive sensing algorithms require n^2 measurements, which can be improved with the aid of log n rounds of adaptive sensing. It is then natural to ask whether log n rounds of adaptive sensing is necessary. The authors tackled this issue by developing a lower bound showing that: any algorithm that uses no more than o(log n / loglog n) rounds of adaptive sensing necessarily requires at least n^{2-o(1)} measurements, thus justifying the provable benefits of adaptive sensing. It would be nice if the authors could further extend their theory to accommodate o(log n) rounds of adaptivity, so as to fully close the gap.
Decision: Accept (poster)