Johnson-Lindenstrauss Lemma and Gordon's Theorem

5 Johnson-Lindenstrauss Lemma and Gordons Theorem 5.1 The Johnson-Lindenstrauss Lemma Suppose one has n points, X = {x1 , . . . , xn }, in Rd (with d large). If d > n, since the points have to lie in a subspace of dimension n it is clear that one can consider the projection f : Rd → Rn of the points to that subspace without distorting the geometry of X. In particular, for every xi and xj , kf (xi ) − f (xj )k2 = kxi − xj k2 , meaning that f is an isometry in X. Suppose now we allow a bit of distortion, and look for f : Rd → Rk that is an −isometry, meaning that (1 − )kxi − xj k2 ≤ kf (xi ) − f (xj )k2 ≤ (1 + )kxi − xj k2 . (48) Can we do better than k = n? In 1984, Johnson and Lindenstrauss [JL84] showed a remarkable Lemma (below) that answers this question positively. Theorem 5.1 (Johnson-Lindenstrauss Lemma [JL84]) For any 0 <  < 1 and for any integer n, let k be such that 1 k≥4 2 log n.  /2 − 3 /3 Then, for any set X of n points in Rd , there is a linear map f : Rd → Rk that is an −isometry for X (see (48)). This map can be found in randomized polynomial time. We borrow, from [DG02], an elementary proof for the Theorem. We need a few concentration of measure bounds, we will omit the proof of those but they are available in [DG02] and are essentially the same ideas as those used to show Hoeffding’s inequality. Lemma 5.2 (see [DG02]) Let y1 , . . . , yd be i.i.d standard Gaussian random variables and  Y = d k (y1 , . . . , yd ). Let g : R → R be the projection into the first k coordinates and Z = g kYY k = 1 kY k (y1 , . . . , yk ) and L = kZk2 . It is clear that EL = k d. In fact, L is very concentrated around its mean • If β < 1,     k k Pr L ≤ β ≤ exp (1 − β + log β) . d 2 • If β > 1,    k k Pr L ≥ β ≤ exp (1 − β + log β) . d 2  Proof. [ of Johnson-Lindenstrauss Lemma ] We will start by showing that, given a pair xi , xj a projection onto a random subspace of dimension k will satisfy (after appropriate scaling) property (48) with high probability. WLOG, we can assume that u = xi − xj has unit norm. Understanding what is the norm of the projection of u on a random subspace of dimension k is the same as understanding the norm of the projection of a (uniformly) random point on S d−1 the unit sphere in Rd on a specific k−dimensional subspace, let’s say the one generated by the first k canonical basis vectors. This means that we are interested in the distribution of the norm of the first k entries of a random vector drawn from the uniform distribution over S d−1 – this distribution is the same as taking a standard Gaussian vector in Rd and normalizing it to the unit sphere. Let g : Rd → Rk be the projection on a random k −dimensional subspace and let f : Rd → Rk kf (xi )−f (xj )k2 defined as f = kd g. Then (by the above discussion), given a pair of distinct xi and xj , kxi −xj k2 has the same distribution as kd L, as defined in Lemma 5.2. Using Lemma 5.2, we have, given a pair xi , xj ,     kf (xi ) − f (xj )k2 k Pr ≤ (1 − ) ≤ exp (1 − (1 − ) + log(1 − )) , kxi − xj k2 2 since, for  ≥ 0, log(1 − ) ≤ − − 2 /2 we have     kf (xi ) − f (xj )k2 k2 Pr ≤ (1 − ) ≤ exp − kxi − xj k2 4 ≤ exp (−2 log n) = 1 . n2 On the other hand,     kf (xi ) − f (xj )k2 k ≤ exp (1 − (1 + ) + log(1 + )) . Pr ≥ (1 + ) 2 kxi − xj k2 since, for  ≥ 0, log(1 + ) ≤  − 2 /2 + 3 /3 we have
!   k 2 − 23 /3 kf (xi ) − f (xj )k2 Prob ≤ (1 − ) ≤ exp − kxi − xj k2 4 ≤ exp (−2 log n) = 1 . n2 By union bound it follows that  kf (xi ) − f (xj )k2 2 Pr ∈ / [1 − , 1 + ] ≤ 2 . 2 kxi − xj k n 
Since there exist n2 such pairs, again, a simple union bound gives   kf (xi ) − f (xj )k2 2 n(n − 1) 1 Pr ∃i,j : ∈ / [1 − , 1 + ] ≤ 2 =1− . 2 kxi − xj k n 2 n Therefore, choosing f as a properly scaled projection onto a random k −dimensional subspace is an − isometry on X (see (48)) with probability at least n1 . We can achieve any desirable constant probability of success by trying O(n) such random projections, meaning we can find an −isometry in randomized polynomial time. 2 Note that by considering k slightly larger one can get a good projection on the first random attempt with very good confidence. In fact, it’s trivial to adapt the proof above to obtain the following Lemma: Lemma 5.3 For any 0 <  < 1, τ > 0, and for any integer n, let k be such that k ≥ (2 + τ ) 2 /2 2 log n. − 3 /3 Then, for any set X of n points in Rd , take f : Rd → Rk to be a suitably scaled projection on a random subspace of dimension k, then f is an −isometry for X (see (48)) with probability at least 1 − n1τ . Lemma 5.3 is quite remarkable. Think about the situation where we are given a high-dimensional data set in a streaming fashion – meaning that we get each data point at a time, consecutively. To run a dimension-reduction technique like PCA or Diffusion maps we would need to wait until we received the last data point and then compute the dimension reduction map (both PCA and Diffusion Maps are, in some sense, data adaptive). Using Lemma 5.3 you can just choose a projection at random in the beginning of the process (all ones needs to know is an estimate of the log of the size of the data set) and just map each point using this projection matrix which can be done online – we don’t need to see the next point to compute the projection of the current data point. Lemma 5.3 ensures that this (seemingly naı̈ve) procedure will, with high probably, not distort the data by more than . 5.1.1 Optimality of the Johnson-Lindenstrauss Lemma It is natural to ask whether the dependency on  and n in Lemma 5.3 can be improved. Noga Alon [Alo03] showed that there are n points for which the smallest  dimension kon which they can 1 be embedded with a distortion as in Lemma 5.3, satisfies k = Ω log(1/) −2 log n , this was recently
improved by Larsen and Nelson [?], for linear maps, to Ω −2 log n , closing the gap.22 5.1.2 Fast Johnson-Lindenstrauss (Disclaimer: the purpose of this section is just to provide a bit of intuition, there is a lot of handwaving!!) Let’s continue thinking about the high-dimensional streaming data. After we draw the random projection matrix, say M , for each data point x, we still have to compute M x which, since M has O(−2 log(n)d) entries, has a computational cost of O(−2 log(n)d). In some applications this might be too expensive, can one do better? There is no hope of (significantly) reducing the number of rows (Recall Open Problem ?? and the lower bound by Alon [Alo03]). The only hope is to speed up the matrix-vector multiplication. If we were able to construct a sparse matrix M then we would definitely speed up the computation of M x but sparse matrices tend to distort sparse vectors, and the data set may contain. Another option would be to exploit the Fast Fourier Transform and compute the Fourier Transform of x (which takes O(d log d) time) and then multiply the Fourier Transform of x by a sparse matrix. However, this again may not work because x might have a sparse Fourier Transform. The solution comes from leveraging an uncertainty principle — it is impossible for both x and the FT of x to be sparse simultaneously. The idea is that if, before one takes the Fourier Transform of x, one flips (randomly) the signs of x, then the probably of obtaining a sparse vector is very small so a sparse matrix can be used for projection. In a nutshell the algorithm has M be a matrix of the form P HD, 22 An earlier version of these notes marked closing the gap as an open problem, this has been corrected. where D is a diagonal matrix that flips the signs of the vector randomly, H is a Fourier Transform (or Hadamard transform) and P a sparse matrix. This method was proposed and analysed in [AC09] and, roughly speaking, achieves a complexity of O(d log d), instead of the classical O(−2 log(n)d). There is a very interesting line of work proposing fast Johnson Lindenstrauss projections based on sparse matrices. In fact, this is, in some sense, the motivation for Open Problem 4.4. in [Ban15d]. We recommend these notes Jelani Nelson’s notes for more on the topic [Nel]. 5.2 Gordon’s Theorem In the last section we showed that, in order to approximately preserve the distances (up to 1 ± ε)
−2 between n points it suffices to randomly project them to Θ  log n dimensions. The key argument was that a random projection approximately preserves the norm of every point in a set S, in this case the set of differences between pairs of n points. What we showed is that, in order
to approximately preserve the norm of every point in S it is enough to project to Θ −2 log |S| dimensions. The question this section is meant to answer is: can this improved if S has a special structure? Given a set S, what is the measure of complexity of S that explains how many dimensions one needs to take on the projection to still approximately preserve the norms of points in S. Was we will see below, this will be captured, via Gordon’s Theorem, by the so called Gaussian Width of S. Definition 5.4 (Gaussian Width) Given a closed set S ⊂ Rd , its gaussian width ω(S) is define as:   ω(S) = E max gdT x , x∈S where gd ∼ N (0, Id×d ). Similarly to what we did in the proof of Theorem 5.1 we will restrict our attention to sets S of unit norm vectors, meaning that S ⊂ Sd−1 . Also, we will focus our attention not in random projections but in the similar model of random linear maps G : Rd → Rk that are given by matrices with i.i.d. gaussian entries. For this reason the following Proposition will be useful: Proposition 5.5 Let gk ∼ N (0, Ik×k ), and define ak := Ekgk k. Then q k k+1 √ k ≤ ak ≤ √ k. We are now ready to present Gordon’s Theorem. Theorem 5.6 (Gordon’s Theorem [Gor88]) Let G ∈ Rk×d a random matrix with independent N (0, 1) entries and S ⊂ Sd−1 be a closed subset of the unit sphere in d dimensions. Then E max x∈S ω(S) 1 Gx ≤ 1 + , ak ak and E min x∈S 1 ω(S) , Gx ≥ 1 − ak ak where ak = Ekgk k and ω(S) is the gaussian width of S. Recall that q k k+1 √ k ≤ ak ≤ √ k. Before proving Gordon’s Theorem we’ll note some of it’s direct implications. It suggest that 1 ak G preserves the norm of the points in S up to 1 ± ω(S) ak , indeed we can make this precise with Gaussian Concentration. Note that the function F (G) = maxx∈S a1k Gx is 1-Lipschitz. Indeed max kG1 x1 k − max kG2 x2 k x1 ∈S x2 ∈S ≤ max |kG1 xk − kG2 xk| ≤ max k(G1 − G2 ) xk x∈S x∈S = kG1 − G2 k ≤ kG1 − G2 kF . Similarly, one can show that F (G) = minx∈S a1k Gx is 1-Lipschitz. Thus, one can use Gaussian Concentration to get:    2 t Prob max kGxk ≥ ak + ω(S) + t ≤ exp − , (49) x∈S 2 and   Prob min kGxk ≤ ak − ω(S) − t x∈S  2 t ≤ exp − . 2 (50) This gives us the following Theorem. Theorem 5.7 Let G ∈ Rk×d a random matrix with independent Nr (0, 1) entries and S ⊂ Sd−1 be ω(S)2 , with probability ≥ 1 − a closed subset of the unit sphere in d dimensions. Then, for ε > a2k    2 2 exp −k ε − ω(S) : ak (1 − ε)kxk ≤ for all x ∈ S. Recall that k − k k+1 1 Gx ≤ (1 + ε)kxk, ak ≤ a2k ≤ k. Proof. This is readily obtained by taking ε = ω(S)+t ak , using (49), (50), and recalling that ak2 ≤ k. 2 p Remark 5.8 Note that a simple use of a union bound23 shows that ω(S) . 2 log |S|, which means that taking k to be of the order of log |S| suffices to ensure that a1k G to have the Johnson Lindenstrauss property. This observation shows that Theorem 5.7 essentially directly implies Theorem 5.1 (although not exacly, since a1k G is not a projection). 23 This follows from the fact that the maximum of n standard gaussian random variables is . p 2 log |S|. 5.2.1 Gordon’s Escape Through a Mesh Theorem Theorem 5.7 suggests that, if ω(S) ≤ ak , a uniformly chosen random subspace of Rn of dimension (n − k) (which can be seen as the nullspace of G) avoids a set S with high probability. This is indeed the case and is known as Gordon’s Escape Through a Mesh Theorem, it’s Corollary 3.4. in Gordon’s original paper [Gor88]. See also [Mix14b] for a description of the proof. We include the Theorem below for the sake of completeness. Theorem 5.9 (Corollary 3.4. in [Gor88]) Let S ⊂ Sd−1 be a closed subset of the unit sphere in d dimensions. If ω(S) < ak , then for a (n − k)-dimensional subspace Λ drawn uniformly from the Grassmanian manifold we have   7 1 2 Prob {Λ ∩ S = 6 ∅} ≤ exp − (ak − ω(S)) , 2 18 where ω(S) is the gaussian width of S and ak = Ekgk k where gk ∼ N (0, Ik×k ). 5.2.2 Proof of Gordon’s Theorem In order to prove this Theorem we will use extensions of the Slepian’s Comparison Lemma. Slepian’s Comparison Lemma, and the closely related Sudakov-Fernique inequality, are crucial tools to compare Gaussian Processes. A Gaussian process is a family of gaussian random variables indexed by some set T , {Xt }t∈T (if T is finite this is simply a gaussian vector). Given a gaussian process Xt , a particular quantity of interest is E [maxt∈T Xt ]. Intuitively, if we have two Gaussian processes Xt and Yt with mean zero E [Xt ] = E [Yt ] = 0, for all t ∈ T , and the same variance, then the process that has the “least correlations” should have a larger maximum (think the maximum entry of vector with i.i.d. gaussian entries versus one always with the same gaussian entry). The following inequality makes this intuition precise and extends it to processes with different variances. 24 Theorem 5.10 (Slepian/Sudakov-Fernique inequality) Let {Xu }u∈U and {Yu }u∈U be two (almost surely bounded) centered Gaussian processes indexed by the same (compact) set U . If, for every u1 , u2 ∈ U : E [Xu1 − Xu2 ]2 ≤ E [Yu1 − Yu2 ]2 , (51) then     E max Xu ≤ E max Yu . u∈U u∈U The following extension is due to Gordon [Gor85, Gor88]. Theorem 5.11 [Theorem A in [Gor88]] Let {Xt,u }(t,u)∈T ×U and {Yt,u }(t,u)∈T ×U be two (almost surely bounded) centered Gaussian processes indexed by the same (compact) sets T and U . If, for every t1 , t2 ∈ T and u1 , u2 ∈ U : E [Xt1 ,u1 − Xt1 ,u2 ]2 ≤ E [Yt1 ,u1 − Yt1 ,u2 ]2 , (52) 24 Although intuitive in some sense, this turns out to be a delicate statement about Gaussian random variables, as it does not hold in general for other distributions. and, for t1 6= t2 , E [Xt1 ,u1 − Xt2 ,u2 ]2 ≥ E [Yt1 ,u1 − Yt2 ,u2 ]2 , then (53)     E min max Xt,u ≤ E min max Yt,u . t∈T u∈U t∈T u∈U Note that Theorem 5.10 easily follows by setting |T | = 1. We are now ready to prove Gordon’s theorem. Proof. [of Theorem 5.6] Let G ∈ Rk×d with i.i.d. N (0, 1) entries. We define two gaussian processes: For v ∈ S ⊂ Sd−1 and u ∈ Sk−1 let g ∼ N (0, Ik×k ) and h ∼ N (0, Id×d ) and define the following processes: Au,v = g T u + hT v, and Bu,v = uT Gv. For all v, v 0 ∈ S ⊂ Sd−1 and u, u0 ∈ Sk−1 , E Av,u − Av0 ,u0 2 − E Bv,u − Bv0 ,u0 2
2
X = 4 − 2 uT u0 + v T v 0 − vi uj − vi0 u0j ij T 0 

 = 4 − 2 u u + v v − 2 − 2 v T v 0 uT u0
= 2 − 2 uT u0 + v T v 0 − uT u0 v T v 0

= 2 1 − uT u0 1 − v T v 0 . 2 T 0
2 2 This means that E Av,u − Av0 ,u0 −E Bv,u − Bv0 ,u0 ≥ 0 and E Av,u − Av0 ,u0 −E Bv,u − Bv0 ,u0 0 if v = v 0 . This means that we can use Theorem 5.11 with X = A and Y = B, to get 2 = E min max Av,u ≤ E min max Bv,u . v∈S u∈Sk−1 v∈S u∈Sk−1 Noting that E min max Bv,u = E min max uT Gv = E min kGv k , v∈S u∈Sk−1 v∈S u∈Sk−1 v∈S and   E min max Av,u = E max g T u + E min hT v = E max g T u − E max(−hT v) = ak − ω(S), v∈S u∈Sk−1 u∈Sk−1 v∈S gives the second part of the Theorem. On the other hand, since E Av,u − Av0 ,u0 Theorem 5.10 with X = B and Y = A, to get 2 v∈S u∈Sk−1 − E Bv,u − Bv0 ,u0 2 ≥ 0 then we can similarly use E max max Av,u ≥ E max max Bv,u . v∈S u∈Sk−1 v∈S u∈Sk−1 Noting that E max max Bv,u = E max max uT Gv = E max kGv k , v∈S u∈Sk−1 and v∈S u∈Sk−1 v∈S   E max max Av,u = E max g T u + E max hT v = ak + ω(S), v∈S u∈Sk−1 v∈S u∈Sk−1 concludes the proof of the Theorem. 2 5.3 Sparse vectors and Low-rank matrices In this Section we illustrate the utility of Gordon’s theorem by undertanding which projections are expected to keep the norm of sparse vectors and low-rank matrices. 5.3.1 Gaussian width of k-sparse vectors Say we have a signal (or image) x ∈ RN that we are interested in measuring with linear measurements yi = aTi x, for ai ∈ RN . In general, it is clear that we would need N measurements to find x. The idea behind Compressed Sensing [CRT06a, Don06] is that one may be able to significantly decrease the number of measurements needed if we know more about the structure of x, a prime example is when x is known to have few non-zero entries (being sparse). Sparse signals do arise in countless applications (for example, images are known to be sparse in the Wavelet basis; in fact this is the basis of the JPEG2000 compression method). We’ll revisit sparse recovery and Compressed Sensing next lecture but for now we’ll see how Gordon’s Theorem can suggest us how many linear measurements are needed in order to reconstruct a sparse vector. An efficient way of representing the measurements is to use a matrix   — aT1 —  — aT —  2   A= , ..   . — aTM — and represent the linear measurements as y = Ax. In order to hope to be able to reconstruct x from y we need that A is injective on sparse vectors. Let us assume that x is s-sparse, meaning that x has at most s non-zero entries (often written as kxk0 ≤ s, where k · k0 is called the 0-norm and counts the number of non-zero entries in a vector25 ). It is also intuitive that, in order for reconstruction to be stable, one would like that not only A is injective in s-sparse vectors but actually almost an isometry, meaning that the `2 distance between Ax1 and Ax2 should be comparable to the distances between x1 and x2 if they are s-sparse. Since the difference between two s-sparse vectors is a 2s-sparse vector, we can alternatively ask for A to keep the norm of 2s sparse vectors. Gordon’s Theorem above suggests that we can take A ∈ RM ×N to have 25 It is important to note that k · k0 is not actually a norm  i.i.d. gaussian entries and to take M ≈ ω (S2s ), where Sk = x : x ∈ SN −1 , kxk0 ≤ k is the set of 2s sparse vectors, and ω (S2s ) the gaussian width of S2s . Proposition 5.12 If s ≤ N , the Gaussian Width ω (Ss ) of Ss , the set of unit-norm vectors that are at most s sparse, satisfies   N ω (Ss ) . s log . s Proof. ω (Ss ) = max v∈SS N −1 , kvk0 ≤s g T v, log  N s  , where g ∼ N (0, IN ×N ). We have ω (Ss ) = max Γ⊂[N ], |Γ|=s kgΓ k, where gΓ is the restriction of g to the set of indices Γ. Given a set Γ, Theorem 4.12 gives n o √ √ Prob kgΓ k2 ≥ s + 2 s t + t ≤ exp(−t). Union bounding over all Γ ⊂ [N ], |Γ| = s gives     √ √ N 2 Prob max kgΓ k ≥ s + 2 s t + t ≤ exp(−t) s Γ⊂[N ], |Γ|=s Taking u such that t = su, gives     
√ N 2 Prob max kgΓ k ≥ s 1 + 2 u + u ≤ exp −su + s log . (54) s Γ⊂[N ], |Γ|=s
Taking u > log Ns it can be readily seen that the typical size of maxΓ⊂[N ], |Γ|=s kgΓ k2 is .
s log Ns . The proof can be finished by integrating (54) in order to get a bound of the expectation of q maxΓ⊂[N ], |Γ|=s kgΓ k2 . 2
N measurements suffice to identify a 2s-sparse vector. As we’ll see, This suggests that ≈ 2s log 2s not only such a number of measurements suffices to identify a sparse vector but also for certain efficient algorithms to do so. 5.3.2 The Restricted Isometry Property and a couple of open problems Matrices perserving the norm of sparse vectors do play a central role in sparse recovery, they are said to satisfy the Restricted Isometry Property. More precisely: Definition 5.13 (The Restricted Isometry Property) An M × N matrix A (with either real or complex valued entries) is said to satisfy the (s, δ)-Restricted Isometry Property (RIP), (1 − δ)kxk2 ≤ kAxk2 ≤ (1 + δ)kxk2 , for all s-sparse x. Using Proposition 5.12 and Theorem 5.7 one can readily
show that matrices with Gaussian entries satisfy the restricted isometry property with M ≈ s log Ns . Theorem 5.14 Let A be an M × N matrix with i.i.d. standard gaussian entries, there exists a constant C such that, if   N M ≥ Cs log , s
then a1M A satisfies the s, 13 -RIP, with high probability. Theorem 5.14 suggests that RIP matrices are abundant for s ≈ M log(N ) ,√however it appears to be very difficult to deterministically construct matrices that are RIP for s  M , known as the square bottleneck [Tao07, BFMW13, BFMM14, BMM14, B+ 11, Mix14a]. The only known unconditional construction that is able to break this bottleneck is due to Bourgain et al. [B+ 11] that achieves 1 s ≈ M 2 +ε for a small, but positive, ε. There is a conditional construction, based on the Paley Equiangular Tight Frame, that will be briefly described in the next Lecture [BFMW13, BMM14]. Open Problem 5.1 Construct deterministic matrices A ∈ CM ×N (or A ∈ CM ×N ) satisfying (s, 13 )M 0.6 . RIP for s & polylog(N Open Problem 5.2 Theorem 5.14 guarantees that if we take A to have i.i.d. Gaussian entries then M it should be RIP for s ≈ log(N ) . If we were able to, given A, certify that it indeed is RIP for some s then one could have a randomized algorithm to build RIP matrices (but that is guaranteed to eventually find one). This motives the following question 1. Let N = 2M , for which s is there a polynomial time
algorithm that is guaranteed to, with high probability, certify that a gaussian matrix A is s, 13 -RIP?
2. In particular, a s, 13 -RIP matrix has to not have s sparse vectors in its nullspace. This motivates a second question: Let N = 2M , for which s is there a polynomial time algorithm that is guaranteed to, with high probability, certify that a gaussian matrix A does not have s-sparse vectors in its nullspace? The second √ question is tightly connected to the question of sparsest vector on a subspace (for which s ≈ M is the best known answer), we refer the reader to [SWW12, QSW14, BKS13b] for more on this problem and recent advances. Note that checking whether a matrix has RIP or not is, in general, NP-hard [BDMS13, TP13]. 5.3.3 Gaussian width of rank-r matrices Another structured set of interest is the set of low rank matrices. Low-rank matrices appear in countless applications, a prime example being the Netflix Prize. In that particular example the matrix in question is a matrix indexed by users of the Netflix service and movies. Given a user and a movie, the corresponding entry of the matrix should correspond to the score that user would attribute to that movie. This matrix is believed to be low-rank. The goal is then to estimate the score for user and movie pairs that have not been rated yet from the ones that have, by exploiting the low-rank matrix structure. This is known as low-rank matrix completion [CT10, CR09, Rec11]. In this short section, we will not address the problem of matrix completion but rather make a comment about the problem of low-rank matrix sensing, where instead of observing some of the entries of the matrix X ∈ Rn1 ×n2 one has access to linear measuremetns of it, of the form yi = Tr(ATi X). In order to understand the number of measurements needed for the measurement procedure to be a nearly isometry for rank r matrices, we can estimate the Gaussian Width of the set of matrices X ∈∈ Rn1 ×n2 whose rank is smaller or equal to 2r (and use Gordon’s Theorem). Proposition 5.15 ω  X : X ∈ Rn1 ×n2 , rank(X) ≤ r
. p r(d1 + d2 ). Proof. ω  X : X ∈ Rn1 ×n2 , rank(X) ≤ r
=E Let X = U ΣV T be the SVD decomposition of X, then 
ω X : X ∈ Rn1 ×n2 , rank(X) ≤ r = E max kXkF =1 rank(X)≤r max Tr(GX). U T U =V T V =Ir×r Σ∈Rr×r diagonal kΣkF =1
Tr(Σ V T GU ). This implies that 
√ √ √ ω X : X ∈ Rn1 ×n2 , rank(X) ≤ r ≤ (Tr Σ) (EkGk) . r ( n1 + n1 ) , where the last inequality follows from bounds on the largest eigenvalue of a Wishart matrix, such as the ones used on Lecture 1. 2