arXiv:1001.2738v2 [cs.IT] 6 May 2010 Note on sampling without replacing from a finite collection o f matrices David Gross and Vincent Nesme Institute for Theoretical Physics, Leibniz University Hannover, 30167 Hannover, Germany ∗ 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. 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 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. 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. 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 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 = $^{∗}$Electronic address: www.itp.uni-hannover.de/˜davidg 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. 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. A. Motivation R : ρ ↦→ n 2 m m ∑ i =1 tr( ρw$_{A}$$_{i}$ ) w$_{A}$$_{i}$. (1) B. Statement