content_image/417249.jpg
# Note on sampling without replacing from a finite collection o f matrices 

Institute for Theoretical Physics, Leibniz University Hannover, 30167 Hannover, Germany ∗ 

David Gross and Vincent Nesme 

This technical note supplies an affirmative answer to a quest ion raised in a recent pre-print in the context of a “matrix recovery” problem. Assume one samples m Hermitian matrices X$_{1}$,. ..,X m with replacement from a finite collection. The deviation of the sum X$_{1}$ +$_{· · ·}$+ X m from its expected value in terms of the operator norm can be estimated by an “operator Chernoff-bound” due to Ahls wede and Winter. The question arose whether the bounds obtained this way continue to hold if the matrices are sampled without replacement. We remark that a positive answer is implied by a classical argument by Hoeffding. Some consequences for the matrix recovery problem are sketched. 

This is a technical comment on [1]. While we provide a (minimal) introduction, readers not familiar with [1] may fi nd the present note hard to follow. 

The low-rank matrix recovery problem [1–10] is: Recon- struct a low-rank matrix ρ from m randomly selected matrix elements. The more general version introduced in [1] reads: Reconstruct ρ from m randomly selected expansion coeffi- cients with respect to any fixed matrix basis. 

Let us consider what seems to be the most mundane aspect of the problem: the way in which the m coefficients are “ran- domly selected”. Assume we are dealing with an n × n matrix ρ . The statement of the matrix recovery problem calls for us to sample m of the n 2 coefficients characterizing ρ without replacing . This yields a random subset Ω consisting of m of the n 2 coefficients, from which the matrix ρ is then to be re- covered. 

Due to the requirement that the drawn coefficients be dis- tinct, the m samples are not independent. Their dependency turns out to impede the technical analysis of the recovery al- gorithms. In order to avoid this complication, most authors chose to first analyze a variant where the revealed coefficien ts are drawn independently and then, in a second step, relate the modified question to the original one. Two such proxies for sampling without replacement have been discussed: 

1. The Bernoulli model [3, 4, 10]. Here, each of the n 2 co- efficients is assumed to be known with probability m n $_{2}$. Thus the number of revealed coefficients is itself a random variab le (with expectation value m ). The minor draw-back of this ap- proach is that, with finite probability, significantly more t han m coefficients will be uncovered. These possible violations o f the rules of the original problem have to be factored in, when the success probability of the algorithm is computed. 

2. The i.i.d. approach [1, 8, 9]. The known coefficients are obtained by sampling m times with replacement. The draw- back here is that, with fairly high probability, some coeffi- cients will be selected more than once. To understand why 

## A. Motivation 

this is undesirable, we need to recall some technical defini- tions from [1]. 

Let A$_{1}$, . . ., A$_{m}$ be random variables taking values in [1 , n $^{2}$] . For now, assume the A$_{i}$ ’s are distributed uniformly and independently. Let { w$_{a}$ } n 2 a =1 be an orthonormal Hermi- tian basis in the space of n × n -matrices. A central object in the analysis is the sampling operator , defined as 

If the A$_{i}$ are all distinct, then m n 2 R is a projection opera- tor. If, on the other hand, some basis elements occur more than once, the spectrum of the sampling operator will be more complicated. More importantly, the operator norm ‖ m n 2 R‖ may become fairly large. The latter effect is undesirable, as the logarithm of the operator norm appears as a multiplica- tive constant in the final bound on the number of coefficients which need to be known in order for the reconstruction pro- cess to be successful. 

There seem to be three ways to cope with this problem. First, use the worst-case estimate ‖ m n 2 R‖ ≤ m (done in Sec- tion II.C of [1]). Second, use the fact that the operator norm is very likely to be of order O (log n ) (suggested at the end of Section II.C in [1] and implemented in later versions of [9]). Third, prove that the arguments in [1] remain valid when the A$_{i}$ ’s are chosen without replacement. Supplying such a proof is the purpose of the present note. 

Following earlier work [3, 4], Ref. [1] reduces the analy- sis of the matrix recovery problem to the problem of control- ling the operator norm of various linear functions of R (c.f. Lemma 4 and Lemma 6 of [1]). This, in turn, is done by employing a large-deviation bound for the sum of indepen- dent matrix-valued random variables, which was derived in [11]. Below, we point out that in some situations this bound remains valid when the random variables are not independent, but represent sampling without replacing. 

Let C be a finite set. For 1 ≤ m ≤ | C | , let X$_{i}$ be a random variable taking values in C with uniform proba- bility. We assume that all the X$_{i}$ are independent, so that X = 〈 X$_{1}$, . . ., X$_{m}$ 〉 is a C $^{m}$-valued random vector model- ing sampling with replacement from C . Likewise, let Y = 

<img src='content_image/417249.jpg'>

## B. Statement 

