Principal Component Analysis in High Dimensions and the Spike Model

1 Principal Component Analysis in High Dimensions and the Spike Model 1.1 Dimension Reduction and PCA When faced with a high dimensional dataset, a natural approach is to try to reduce its dimension, either by projecting it to a lower dimension space or by finding a better representation for the data. During this course we will see a few different ways of doing dimension reduction. We will start with Principal Component Analysis (PCA). In fact, PCA continues to be one of the best (and simplest) tools for exploratory data analysis. Remarkably, it dates back to a 1901 paper by Karl Pearson [Pea01]! Let’s say we have n data points x1 , . . . , xn in Rp , for some p, and we are interested in (linearly) projecting the data to d < p dimensions. This is particularly useful if, say, one wants to visualize the data in two or three dimensions. There are a couple of different ways we can try to choose this projection: 1. Finding the d-dimensional affine subspace for which the projections of x1 , . . . , xn on it best approximate the original points x1 , . . . , xn . 2. Finding the d dimensional projection of x1 , . . . , xn that preserved as much variance of the data as possible. As we will see below, these two approaches are equivalent and they correspond to Principal Component Analysis. Before proceeding, we recall a couple of simple statistical quantities associated with x1 , . . . , xn , that will reappear below. Given x1 , . . . , xn we define its sample mean as n 1X xk , n (4) 1 X (xk − µn ) (xk − µn )T . n−1 (5) µn = k=1 and its sample covariance as n Σn = k=1 Remark 1.1 If x1 , . . . , xn are independently sampled from a distribution, µn and Σn are unbiased estimators for, respectively, the mean and covariance of the distribution. We will start with the first interpretation of PCA and then show that it is equivalent to the second. 1.1.1 PCA as best d-dimensional affine fit We are trying to approximate each xk by xk ≈ µ + d X i=1 (βk )i vi , (6) where v1 , . . . , vd is an orthonormal basis for the d-dimensional subspace, µ ∈ Rp represents the translation, and βk corresponds to the coefficients of xk . If we represent the subspace by V = [v1 · · · vd ] ∈ Rp×d then we can rewrite (7) as xk ≈ µ + V β k , (7) where V T V = Id×d as the vectors vi are orthonormal. We will measure goodness of fit in terms of least squares and attempt to solve n X min µ, V, βk V T V =I k=1 kxk − (µ + V βk )k22 (8) We start by optimizing for µ. It is easy to see that the first order conditions for µ correspond to ∇µ n X kxk − (µ + V βk )k22 = 0 ⇔ k=1 n X (xk − (µ + V βk )) = 0. k=1 Thus, the optimal value µ∗ of µ satisfies n X ! − nµ∗ − V xk k=1 Because Pn k=1 βk n X ! βk = 0. k=1 = 0 we have that the optimal µ is given by n 1X µ = x k = µn , n ∗ k=1 the sample mean. We can then proceed on finding the solution for (9) by solving min n X V, βk V T V =I k=1 kxk − µn − V βk k22 . (9) Let us proceed by optimizing for βk . Since the problem decouples for each k, we can focus on, for each k, 2 d X 2 min kxk − µn − V βk k2 = min xk − µn − (βk )i vi . (10) βk βk i=1 2 Since v1 , . . . , vd are orthonormal, it is easy to see that the solution is given by (βk∗ )i = viT (xk − µn ) which can be succinctly written as βk = V T (xk − µn ). Thus, (9) is equivalent to min V TV =I n X k=1 (xk − µn ) − V V T (xk − µn ) 2 . 2 (11) Note that (xk − µn ) − V V T (xk − µn ) 2 2 = (xk − µn )T (xk − µn ) −2 (xk − µn )T V V T (xk − µn )
+ (xk − µn )T V V T V V T (xk − µn ) = (xk − µn )T (xk − µn ) − (xk − µn )T V V T (xk − µn ) . Since (xk − µn )T (xk − µn ) does not depend on V , minimizing (9) is equivalent to max V T V =I n X (xk − µn )T V V T (xk − µn ) . (12) k=1 A few more simple algebraic manipulations using properties of the trace: n X T T (xk − µn ) V V (xk − µn ) = k=1 n X h i T T Tr (xk − µn ) V V (xk − µn ) k=1 = n X h i Tr V T (xk − µn ) (xk − µn )T V k=1 " = Tr V T n X # (xk − µn ) (xk − µn )T V k=1   = (n − 1) Tr V T Σn V . This means that the solution to (13) is given by   max Tr V T Σn V . V T V =I (13) As we saw above (recall (2)) the solution is given by V = [v1 , · · · , vd ] where v1 , . . . , vd correspond to the d leading eigenvectors of Σn . Let us first show that interpretation (2) of finding the d-dimensional projection of x1 , . . . , xn that preserves the most variance also arrives to the optimization problem (13). 1.1.2 PCA as d-dimensional projection that preserves the most variance We aim to find an orthonormal basis v1 , . . . , vd (organized as V = [v1 , . . . , vd ] with V T V = Id×d ) of a d-dimensional space such that the projection of x1 , . . . , xn projected on this subspace has the most variance. Equivalently we can ask for the points  T n   v1 xk    ..  ,  .      T vd xk k=1 to have as much variance as possible. Hence, we are interested in solving max n X V T V =I k=1 n 1X T V xr V xk − n T 2 . (14) r=1 k=1 Note that n X n 1X T V xk − V xr n T 2 = r=1 n X V T (xk − µn ) 2
= Tr V T Σn V , k=1 showing that (14) is equivalent to (13) and that the two interpretations of PCA are indeed equivalent. 1.1.3 Finding the Principal Components When given a dataset x1 , . . . , xn ∈ Rp , in order to compute the Principal Components one needs to find the leading eigenvectors of n 1 X Σn = (xk − µn ) (xk − µn )T . n−1 k=1 A naive way of doing this would be to construct Σn (which takes O(np2 ) work) and then finding its 3 spectral decomposition (which  2 takes
O(p ) work). This means that the computational complexity of 3 this procedure is O max np , p (see [HJ85] and/or [Gol96]). An alternative is to use the Singular Value Decomposition (1). Let X = [x1 · · · xn ] recall that, Σn =

T 1 X − µn 1T X − µn 1T . n Let us take the SVD of X − µn 1T = UL DURT with UL ∈ O(p), D diagonal, and URT UR = I. Then, Σn =

T 1 X − µn 1T X − µn 1T = UL DURT UR DULT = UL D2 ULT , n meaning that UL correspond to the eigenvectors of Σn . Computing the SVD of X − µn 1T takes O(min n2 p, p2 n) but if one is interested in simply computing the top d eigenvectors then this computational costs reduces to O(dnp). This can be further improved with randomized algorithms.
There are randomized algorithms that compute an approximate solution in O pn log d + (p + n)d2 time (see for example [HMT09, RST09, MM15]).1 1.1.4 Which d should we pick? Given a dataset, if the objective is to visualize it then picking d = 2 or d = 3 might make the most sense. However, PCA is useful for many other purposes, for example: (1) often times the data belongs to a lower dimensional space but is corrupted by high dimensional noise. When using PCA it is oftentimess possible to reduce the noise while keeping the signal. (2) One may be interested in running an algorithm that would be too computationally expensive to run in high dimensions, 1 If there is time, we might discuss some of these methods later in the course. dimension reduction may help there, etc. In these applications (and many others) it is not clear how to pick d. (+) If we denote the k-th largest eigenvalue of Σn as λk (Σn ), then the k-th principal component has (+) λk (Σn ) Tr(Σn ) proportion of the variance. 2 A fairly popular heuristic is to try to choose the cut-off at a component that has significantly more variance than the one immediately after. This is usually visualized by a scree plot: a plot of the values of the ordered eigenvalues. Here is an example: a It is common to then try to identify an “elbow” on the scree plot to choose the cut-off. In the next Section we will look into random matrix theory to try to understand better the behavior of the eigenvalues of Σn and it will help us understand when to cut-off. 1.1.5 A related open problem We now show an interesting open problem posed by Mallat and Zeitouni at [MZ11] Open Problem 1.1 (Mallat and Zeitouni [MZ11]) Let g ∼ N (0, Σ) be a gaussian random vector in Rp with a known covariance matrix Σ and d < p. Now, for any orthonormal basis V = [v1 , . . . , vp ] of Rp , consider the following random variable ΓV : Given a draw of the random vector g, ΓV is the squared `2 norm of the largest projection of g on a subspace generated by d elements of the basis V . The question is: What is the basis V for which E [ΓV ] is maximized? 2 Note that Tr (Σn ) = Pp k=1 λk (Σn ). The conjecture in [MZ11] is that the optimal basis is the eigendecomposition of Σ. It is known that this is the case for d = 1 (see [MZ11]) but the question remains open for d > 1. It is not very difficult to see that one can assume, without loss of generality, that Σ is diagonal. A particularly intuitive way of stating the problem is: 1. Given Σ ∈ Rp×p and d 2. Pick an orthonormal basis v1 , . . . , vp 3. Given g ∼ N (0, Σ) 4. Pick d elements ṽ1 , . . . , ṽd of the basis
2 P 5. Score: di=1 ṽiT g The objective is to pick the basis in order to maximize the expected value of the Score. Notice that if the steps of the procedure were taken in a slightly different order on which step 4 would take place before having access to the draw of g (step 3) then the best basis is indeed the eigenbasis of Σ and the best subset of the basis is simply the leading eigenvectors (notice the resemblance with PCA, as described above). More formally, we can write the problem as finding    X
2    argmax E  max viT g  , V ∈Rp×p V T V =I S ⊂[p] |S |=d i∈S where g ∼ N (0, Σ). The observation regarding the different ordering of the steps amounts to saying that the eigenbasis of Σ is the optimal solution for   " # X
2   argmax  max E viT g . V ∈Rp×p V T V =I 1.2 S⊂[p] |S|=d i∈S PCA in high dimensions and Marcenko-Pastur Let us assume that the data points x1 , . . . , xn ∈ Rp are independent draws of a gaussian random variable g ∼ N (0, Σ) for some covariance Σ ∈ Rp×p . In this case when we use PCA we are hoping to find low dimensional structure in the distribution, which should correspond to large eigenvalues of Σ (and their corresponding eigenvectors). For this reason (and since PCA depends on the spectral properties of Σn ) we would like to understand whether the spectral properties of Σn (eigenvalues and eigenvectors) are close to the ones of Σ. Since EΣn = Σ, if p is fixed and n → ∞ the law of large numbers guarantees that indeed Σn → Σ. However, in many modern applications it is not uncommon to have p in the order of n (or, sometimes, even larger!). For example, if our dataset is composed by images then n is the number of images and p the number of pixels per image; it is conceivable that the number of pixels be on the order of the number of images in a set. Unfortunately, in that case, it is no longer clear that Σn → Σ. Dealing with this type of difficulties is the realm of high dimensional statistics. For simplicity we will instead try to understand the spectral properties of Sn = 1 XX T . n n Since x ∼ N (0, Σ) we know that µn → 0 (and, clearly, n−1 → 1) the spectral properties of Sn will be 3 essentially the same as Σn . Let us start by looking into a simple example, Σ = I. In that case, the distribution has no low dimensional structure, as the distribution is rotation invariant. The following is a histogram (left) and a scree plot of the eigenvalues of a sample of Sn (when Σ = I) for p = 500 and n = 1000. The red line is the eigenvalue distribution predicted by the Marchenko-Pastur distribution (15), that we will discuss below. As one can see in the image, there are many eigenvalues considerably larger than 1 (and some considerably larger than others). Notice that , if given this profile of eigenvalues of Σn one could potentially be led to believe that the data has low dimensional structure, when in truth the distribution it was drawn from is isotropic. Understanding the distribution of eigenvalues of random matrices is in the core of Random Matrix Theory (there are many good books on Random Matrix Theory, e.g. [Tao12] and [AGZ10]). This particular limiting distribution was first established in 1967 by Marchenko and Pastur [MP67] and is now referred to as the Marchenko-Pastur distribution. They showed that, if p and n are both going to ∞ with their ratio fixed p/n = γ ≤ 1, the sample distribution of the eigenvalues of Sn (like the histogram above), in the limit, will be p (γ+ − λ) (λ − γ− ) 1 dFγ (λ) = 1[γ− ,γ+ ] (λ)dλ, (15) 2π γλ 3 In this case, Sn is actually the Maximum likelihood estimator for Σ, we’ll talk about Maximum likelihood estimation later in the course. with support [γ− , γ+ ]. This is plotted as the red line in the figure above. Remark 1.2 We will not show the proof of the Marchenko-Pastur Theorem here (you can see, for example, [Bai99] for several different proofs of it), but an approach to a proof is using the so-called moment method. The core of the idea is to note that one can compute moments of the eigenvalue distribution in two ways and note that (in the limit) for any k, " k # Z γ+ p   1 1 1 1X k T k E Tr XX = E Tr Sn = E λi (Sn ) = λk dFγ (λ), p n p p γ− i=1 h
k i and that the quantities p1 E Tr n1 XX T can be estimated (these estimates rely essentially in combinatorics). The distribution dFγ (λ) can then be computed from its moments. 1.2.1 A related open problem Open Problem 1.2 (Monotonicity of singular values [BKS13a]) Consider the setting above but with p = n, then X ∈ Rn×n is a matrix with iid N (0, 1) entries. Let   1 σi √ X , n denote the i-th singular value4 of √1 X, n and define n "  1X αR (n) := E σi n i=1 as the expected value of the average singular value of The conjecture is that, for every n ≥ 1, 1 √ X n # , √1 X. n αR (n + 1) ≥ αR (n). Moreover, for the analogous quantity αC (n) defined over the complex numbers, meaning simply that each entry of X is an iid complex valued standard gaussian CN (0, 1) the reverse inequality is conjectured for all n ≥ 1: αC (n + 1) ≤ αC (n). Notice that the singular values of √1 X n  σi 4 The i-th diagonal element of Σ in the SVD are simply the square roots of the eigenvalues of Sn , 1 √ X n √1 X n  = = U ΣV . p λi (Sn ). This means that we can compute αR in the limit (since we know the limiting distribution of λi (Sn )) and get (since p = n we have γ = 1, γ− = 0, and γ+ = 2) p Z 2 Z 2 1 1 (2 − λ) λ 1 8 = ≈ 0.8488. lim αR (n) = λ 2 dF1 (λ) = λ2 n→∞ λ 3π 2π 0 0 Also, αR (1) simply corresponds to the expected value of the absolute value of a standard gaussian g r αR (1) = E|g| = 2 ≈ 0.7990, π which is compatible with the conjecture. On the complex valued side, the Marchenko-Pastur distribution also holds for the complex valued case and so limn→∞ αC (n) = limn→∞ αR (n) and αC (1) can also be easily calculated and seen to be larger than the limit. 1.3 Spike Models and BBP transition What if there actually is some (linear) low dimensional structure on the data? When can we expect to capture it with PCA? A particularly simple, yet relevant, example to analyse is when the covariance matrix Σ is an identity with a rank 1 perturbation, which we refer to as a spike model Σ = I + βvv T , for v a unit norm vector and β ≥ 0. √ One way to think about this instance is as each data point x consisting of a signal part βg0 v √ where g0 is a one-dimensional standard gaussian (a gaussian multiple of a fixed vector βv and a √ noise part g ∼ N (0, I) (independent of g0 . Then x = g + βg0 v is a gaussian random variable x ∼ N (0, I + βvv T ). A natural question is whether this rank 1 perturbation can be seen in Sn . Let us build some intuition with an example, the following is the histogram of the eigenvalues of a sample of Sn for p = 500, n = 1000, v is the first element of the canonical basis v = e1 , and β = 1.5: The images suggests that there is an eigenvalue of Sn that “pops out” of the support of the Marchenko-Pastur distribution (below we will estimate the location of this eigenvalue, and that estimate corresponds to the red “x”). It is worth noticing that the largest eigenvalues of Σ is simply 1 + β = 2.5 while the largest eigenvalue of Sn appears considerably larger than that. Let us try now the same experiment for β = 0.5: and it appears that, for β = 0.5, the distribution of the eigenvalues appears to be undistinguishable from when Σ = I. This motivates the following question: Question 1.3 For which values of γ and β do we expect to see an eigenvalue of Sn popping out of the support of the Marchenko-Pastur distribution, and what is the limit value that we expect it to take? As we will see below, there is a critical value of β below which we don’t expect to see a change in the distribution of eivenalues and above which we expect one of the eigenvalues to pop out of the support, this is known as BBP transition (after Baik, Ben Arous, and Péché [BBAP05]). There are many very nice papers about this and similar phenomena, including [Pau, Joh01, BBAP05, Pau07, BS05, Kar05, BGN11, BGN12].5 In what follows we will find the critical value of β and estimate the location of the largest eigenvalue of Sn . While the argument we will use can be made precise (and is borrowed from [Pau]) we will be ignoring a few details for the sake of exposition. In short, the argument below can be transformed into a rigorous proof, but it is not one at the present form! First of all, it is not difficult to see that we can assume that v = e1 (since everything else is rotation invariant). We want to understand the behavior of the leading eigenvalue of n Sn = 1X 1 xi xTi = XX T , n n i=1 5 Notice that the Marchenko-Pastur theorem does not imply that all eigenvalues are actually in the support of the Marchenk-Pastur distribution, it just rules out that a non-vanishing proportion are. However, it is possible to show that indeed, in the limit, all eigenvalues will be in the support (see, for example, [Pau]). where X = [x1 , . . . , xn ] ∈ Rp×n . We can write X as  √ X= 1 + βZ1T Z2T  , where Z1 ∈ Rn×1 and Z2 ∈ Rn×(p−1) , both populated with i.i.d. standard gaussian entries (N (0, 1)). Then,   √ TZ 1 1 (1 + β)Z1T Z1 1 + βZ 2 T 1 √ Sn = XX = . 1 + βZ2T Z1 Z2T Z2 n n   v1 ˆ Now, let λ and v = where v2 ∈ Rp−1 and v1 ∈ R, denote, respectively, an eigenvalue and v2 associated eigenvector for Sn . By the definition of eigenvalue and eigenvector we have      √ TZ 1 (1 + β)Z1T Z1 1 + βZ v v 2 1 1 1 ˆ √ , =λ 1 + βZ2T Z1 Z2T Z2 v2 v2 n which can be rewritten as 1 1p ˆ 1 (1 + β)Z1T Z1 v1 + 1 + βZ1T Z2 v2 = λv n n 1p 1 ˆ 2. 1 + βZ2T Z1 v1 + Z2T Z2 v2 = λv n n (16) (17) (17) is equivalent to 1p 1 + βZ2T Z1 v1 = n   1 T λ̂ I − Z2 Z2 v2 . n ˆ I − 1 Z T Z2 is invertible (this won’t be justified here, but it is in [Pau]) then we can rewrite it as If λ n 2  v2 = ˆ I − 1 Z T Z2 λ n 2 −1 1p 1 + βZ2T Z1 v1 , n which we can then plug in (16) to get  −1 1 1p 1 T 1p T T ˆ ˆ 1 (1 + β)Z1 Z1 v1 + 1 + βZ1 Z2 λ I − Z2 Z2 1 + βZ2T Z1 v1 = λv n n n n If v1 6= 0 (again, not properly justified here, see [Pau]) then this means that  −1 1 1p 1 T 1p T T ˆ ˆ λ = (1 + β)Z1 Z1 + 1 + βZ1 Z2 λ I − Z2 Z2 1 + βZ2T Z1 n n n n (18) First observation is that because Z1 ∈ Rn has standard gaussian entries then n1 Z1T Z1 → 1, meaning that " #  −1 1 1 1 ˆ = (1 + β) 1 + Z T Z2 λ ˆ I − Z T Z2 λ Z T Z1 . (19) n 1 n 2 n 2 Consider the SVD of Z2 = U ΣV T where U ∈ Rn×p and V ∈ Rp×p have orthonormal columns (meaning that U T U = Ip×p and V T V = Ip×p ), and Σ is a diagonal matrix. Take D = n1 Σ2 then 1 T 1 Z Z2 = V Σ2 V T = V DV T , n 2 n meaning that the diagonal entries of D correspond to the eigenvalues of n1 Z2T Z2 which we expect to 1 be distributed (in the limit) according to the Marchenko-Pastur distribution for p− n ≈ γ. Replacing back in (19)   −1 1 √ T  1 T √ 1/2 T T 1/2 T ˆ ˆ λ = (1 + β) 1 + Z1 nU D V λ I −V DV nU D V Z1 n n    − 1
T
1 ˆ I −V DV T = (1 + β) 1 + V D1/2 U T Z1 U T Z1 D1/2 V T λ n   i −1
T 1/2 T  h
1 T T 1/2 T ˆ = (1 + β) 1 + U Z1 D V V λ I −D V VD U Z1 n   h i−1
T
1 ˆ I −D = (1 + β) 1 + U T Z1 D1/2 λ D1/2 U T Z1 . n Since the columns of U are orthonormal, g := U T Z1 ∈ Rp−1 is an isotropic gaussian (g ∼ N (0, 1)), in fact,
T   Egg T = EU T Z1 U T Z1 = EU T Z1 Z1T U = U T E Z1 Z1T U = U T U = I(p−1)×(p−1) . We proceed  h i−1 1 ˆ I −D λ̂ = (1 + β) 1 + g T D1/2 λ D1/2 g n   p−1 X D 1 jj  gj2 = (1 + β) 1 + n λ̂ − Djj  j=1 Because we expect the diagonal entries of D to be distributed according to the Marchenko-Pastur distribution and g to be independent to it we expect that (again, not properly justified here, see [Pau]) p−1 1 X 2 Dj j gj → ˆ − Djj p−1 λ Z j=1 γ+ γ− x dFγ (x). ˆ λ−x ˆ We thus get an equation for λ:  Z λ̂ = (1 + β) 1 + γ γ+ γ− x ˆ−x λ  dFγ (x) , which can be easily solved with the help of a program that computes integrals symbolically (such as Mathematica) to give (you can also see [Pau] for a derivation):   γ λ̂ = (1 + β) 1 + , (20) β which is particularly elegant (specially considering the size of some the equations used in the derivation). √ An important thing to notice is that for β = γ we have   γ √ √ λ̂ = (1 + γ) 1 + √ = (1 + γ)2 = γ+ , γ √ suggesting that β = γ is the critical point. Indeed this is the case and it is possible to make the above argument rigorous6 and show that in the model described above, √ • If β ≤ γ then λmax (Sn ) → γ+ , • and if β > √ γ then   γ > γ+ . λmax (Sn ) → (1 + β) 1 + β Another important question is wether the leading eigenvector actually correlates with the planted perturbation (in this case e1 ). Turns out that very similar techniques can answer this question as well [Pau] and show that the leading eigenvector vmax of Sn will be non-trivially correlated with e1 if √ and only if β > γ, more precisely: √ • If β ≤ γ then |hvmax , e1 i|2 → 0, • and if β > √ γ then 2 |hvmax , e1 i| → 1.3.1 γ β2 − βγ 1− 1 . A brief mention of Wigner matrices Another very important random matrix model is the Wigner matrix (and it will show up later in this course). Given an integer n, a standard gaussian Wigner matrix W ∈ Rn×n is a symmetric matrix with independent N (0, 1) entries (except for the fact that Wij = Wji ). In the limit, the eigenvalues of √1n W are distributed according to the so-called semi-circular law dSC(x) = 1 p 4 − x2 1[−2,2] (x)dx, 2π and there is also a BBP like transition for this matrix ensemble [FP06]. More precisely, if v is a unit-norm vector in Rn and ξ ≥ 0 then the largest eigenvalue of √1n W + ξvv T satisfies 6 Note that in the argument above it wasn’t even completely clear where it was used that the eigenvalue was actually the leading one. In the actual proof one first needs to make sure that there is an eigenvalue outside of the support and the proof only holds for that one, you can see [Pau] • If ξ ≤ 1 then  λmax 1 √ W + ξvv T n  → 2, • and if ξ > 1 then  λmax 1.3.2 1 √ W + ξvv T n  1 →ξ+ . ξ (21) An open problem about spike models Open Problem 1.3 (Spike Model for cut–SDP [MS15]. As since been solved [MS15]) Let W denote a symmetric Wigner matrix with i.i.d. entries Wij ∼ N (0, 1). Also, given B ∈ Rn×n symmetric, define: Q(B) = max {Tr(BX) : X  0, Xii = 1} . Define q(ξ) as 1 q(ξ) = lim EQ n→∞ n  ξ T 1 11 + √ W n n  . What is the value of ξ∗ , defined as ξ∗ = inf {ξ ≥ 0 : q(ξ) > 2}. It is known that, if 0 ≤ ξ ≤ 1, q(ξ) = 2 [MS15]. One can show that n1 Q(B) ≤ λmax (B). In fact, max {Tr(BX) : X  0, Xii = 1} ≤ max {Tr(BX) : X  0, Tr X = n} . It is also not difficult to show (hint: take the spectral decomposition of X) that ) ( n X max Tr(BX) : X  0, Xii = n = λmax (B). i=1 This means that for ξ > 1, q(ξ) ≤ ξ + 1ξ . Remark 1.4 Optimization problems of the type of max {Tr(BX) : X  0, Xii = 1} are semidefinite programs, they will be a major player later in the course! h  i Since n1 E Tr 11T nξ 11T + √1n W ≈ ξ, by taking X = 11T we expect that q(ξ) ≥ ξ. These observations imply that 1 ≤ ξ∗ < 2 (see [MS15]). A reasonable conjecture is that it is equal to 1. This would imply that a certain semidefinite programming based algorithm for clustering under the Stochastic Block Model on 2 clusters (we will discuss these things later in the course) is optimal for detection (see [MS15]).7 Remark 1.5 We remark that Open Problem 1.3 as since been solved [MS15]. 7 Later in the course we will discuss clustering under the Stochastic Block Model quite thoroughly, and will see how this same SDP is known to be optimal for exact recovery [ABH14, HWX14, Ban15c].