A Tight Degree 4 Sum-of-Squares Lower Bound for the Sherrington-Kirkpatrick Hamiltonian
Dmitriy Kunisky Afonso S. Bandeira
cs.DS cond-mat.stat-mech math.OC math.PR

















































theoremTheorem[section]
remark[theorem]Remark
lemma[theorem]Lemma
claim[theorem]Claim
question[theorem]Question
problem[theorem]Problem
definition[theorem]Definition
example[theorem]Example
proposition[theorem]Proposition
corollary[theorem]Corollary
conjecture[theorem]Conjecture

theoremTheoremTheorems
propositionPropositionPropositions
lemmaLemmaLemmas

plain 

*genericthm
namedtheorem[1]
  
   
  












bboldUbboldmn
bbold





















@rlay
@rlay#1#2
   @skip -@th#1###2







































































































































































































































































[1]#1

  





1]
Dmitriy Kunisky Email: kunisky@cims.nyu.edu. Partially supported by NSF grants DMS-1712730 and DMS-1719545.
1,2]
  Afonso S. Bandeira Email: bandeira@cims.nyu.edu. Partially supported by NSF grants DMS-1712730 and DMS-1719545, and by a grant from the Sloan Foundation.

[1]Department of Mathematics, Courant Institute of Mathematical Sciences, New York University
[2]Center for Data Science, New York University





gobble

A Tight Degree 4 Sum-of-Squares Lower Bound for the Sherrington-Kirkpatrick Hamiltonian
    [
    
  First Draft: July 26, 2019 

  Current Draft: August 31, 2020
=======================================================================================


    We show that, if ∈^N × N_ is drawn from the gaussian orthogonal ensemble, then with high probability the degree 4 sum-of-squares relaxation cannot certify an upper bound on the objective N^-1·^⊤ under the constraints x_i^2 - 1 = 0 (i.e. ∈{± 1 }^N) that is asymptotically smaller than λ_max() ≈ 2. We also conjecture a proof technique for lower bounds against sum-of-squares relaxations of any degree held constant as N →∞, by proposing an approximate pseudomoment construction.










arabic



§ INTRODUCTION




 §.§ Algorithms for the Sherrington-Kirkpatrick Hamiltonian


This paper concerns convex relaxations of the following optimization problem:

    𝖬() 1/Nmax_∈{± 1}^N^⊤.

Since the constraint x_i ∈{± 1} may be written x_i^2 - 1 = 0, this is a simple instance of quadratically constrained quadratic programming.
We are moreover interested in a random setting, where ∈^N × N_ is a random matrix drawn from the gaussian orthogonal ensemble (GOE): W_ii∼(0, 2/N) and W_ij = W_ji∼(0, 1/N), with the N(N + 1) / 2 entries on and above the diagonal distributed independently.
We denote this distribution ∼(N).
Under this model, the spectral radius of  is of constant order, and the normalization in (<ref>) is such that 𝖬() also remains of constant order as N →∞, as we will describe below.

The problem 𝖬() for general  includes the problem of finding maximum cuts in graphs (MaxCut), when  is taken to be a graph Laplacian.
Karp's classical result <cit.> therefore implies that computing 𝖬() is 𝖭𝖯-hard in the worst case.
The case ∼(N) is a simple and mathematically elegant example with which we hope to probe the average-case complexity of the same problem, seeking to understand whether the worst-case complexity abates for specific random models of .

We are assisted in this task by the rich history of the random optimization problem 𝖬() in statistical physics: up to a change in sign, its value is the ground-state energy of the Sherrington-Kirkpatrick (SK) model, a prominent mean-field model of spin glasses <cit.>.
In particular, the asymptotics of its expected value have been well-understood at a non-rigorous level since the seminal work of Parisi <cit.>, who developed a system of deep conjectures on the optimization landscape of 𝖬(), which, among other results, allowed him to analytically predict the limit

    lim_N →∞𝖬()  2𝖯_* ≈ 1.5264.

(Standard results from general gaussian process theory also imply strong concentration around the expectation.)
More recently, the computation of this limit has been made mathematically rigorous  as well <cit.>.

From the perspective of computer science and optimization, perhaps the more natural random model of 𝖬() is the case where  is the adjacency matrix or graph Laplacian of a random graph, which gives randomized instances of MaxCut.
A pair of elegant recent works <cit.> showed that, in fact, for sparse random graphs this problem is intimately related to the gaussian setting of the SK model: an interpolation argument may be used to control both the true value and the value of a certain simple semidefinite programming relaxation of 𝖬() for sparse random graphs in terms of the SK model.

Thus, whether motivated by the mathematical interest of the GOE and SK model or the application to MaxCut, we are led to ask:

    Under ∼(N), can 𝖬() be approximated accurately and efficiently?

Of course, knowing the limiting expectation (<ref>) and concentration around this value, it is simple to produce a vacuous algorithm that outputs the value 2𝖯_*.
To capture the difficulty of solving instances of 𝖬() for specific random draws of , we must therefore refine our question.

One way to do this is to ask instead:

    Under ∼(N), can = () ∈{± 1}^N be efficiently computed such that 1/N^⊤≈ 2𝖯_*?

Recently, assuming a widely-believed conjecture from the spin glass literature, Montanari answered this question in the affirmative in <cit.>.
Montanari's result followed a similar one on local search in a simpler “random energy model” <cit.>, and used proof techniques related to those proposed by Subag in <cit.>, who addressed the same question in a continuous setting.

    Conditional on the conjecture that the Parisi distribution has continuous support at sufficiently low temperature in the SK model,[See Assumption 1 of <cit.> and the surrounding citations and discussion for further details.] for any ϵ > 0, there is a polynomial-time algorithm computing = () ∈{± 1}^N such that
    
    lim_N →∞[1/N^⊤≥ 2𝖯_* - ϵ] = 1.



Another way to refine our question is to ask rather for certificates of upper bounds on 𝖬():

    Can c() ∈ be efficiently computed with c() ≥𝖬() and c() ≈ 2𝖯_*?

(Note that we require c() ≥𝖬() to hold for every ; the algorithm is not allowed to “cheat” the random setting by merely outputting a number slightly larger than 2𝖯_*.)
One simple but sub-optimal approach is to form the spectral certificate, which amounts to disregarding the constraint ∈{± 1}^N by taking c() λ_max() ≈ 2.
Recently, Montanari asked[The authors learned of this problem through private communications soon after <cit.> was published. More recently, it was also included in the problem list “AimPL: Phase transitions in randomized computational problems,” available online at .] whether any certification algorithm could improve on this performance, a problem which, besides modest progress that we will review in the following sections, has since remained open to the best of our knowledge.

Our contribution in this paper is to provide evidence that the spectral certificate is asymptotically optimal by showing that the degree 4 sum-of-squares relaxation, a much more sophisticated convex relaxation, achieves the same performance.



 §.§ Conjectural hardness of certification


One step towards making a convincing prediction of whether better-than-spectral certification is possible in the SK model was taken in <cit.>, in which the authors participated.
In this work, we first showed that, if efficient certification below 2 were possible for the SK model, then it would be possible to efficiently perform a certain hypothesis testing task in a variant of a spiked matrix model.
Then, we provided evidence that this hypothesis testing task should be hard using a method based on the low-degree likelihood ratio.
Roughly speaking, this technique takes low-degree polynomials as a proxy for all polynomial-time testing statistics and measures their performance in a convenient smoothed sense, which allows the optimal low-degree polynomial statistic to be identified and analyzed using an orthogonal polynomial decomposition.

This suggests the following conjecture, which would hold conditional on another, quite broad conjecture of <cit.> that the low-degree likelihood ratio analysis is correct for a large class of hypothesis testing problems.

    
    For any ϵ > 0, there does not exist a polynomial-time certification algorithm for () such that c() ≤ 2 - ϵ with high probability.

Unfortunately, though the low-degree likelihood ratio method predicts many known computational thresholds in random problems correctly, at the moment it is only known to imply rather weak lower bounds against specific algorithms—either only lower bounds in expectation or a smoothed L^2 sense, or high-probability lower bounds under quite restrictive assumptions (see, e.g., the recent survey <cit.> by the authors).
In search of further evidence of hardness of certification, we therefore consider concrete algorithms and analyze their performance directly.



 §.§ Basic notions of sum-of-squares relaxations


The main algorithmic approach for certifying bounds on a problem like 𝖬() is to form convex relaxations that may be solved efficiently by standard convex optimization techniques.
First, note that, defining the cut polytope

    ^N 𝖼𝗈𝗇𝗏({^⊤: ∈{± 1}^N}),

we may rewrite 𝖬() as a linear optimization problem over this set of matrices,

    𝖬() = 1/Nmax_∈^N, .

Though ^N is a convex set, it is complex to describe <cit.>, and in particular does not admit a polynomial-time separation oracle unless 𝖯 = 𝖭𝖯 (by the same result of <cit.> mentioned before).
We thus pursue the idea of expanding ^N to a larger convex set that may be described more simply, and over which convex optimization is tractable.

Specifically, we will study the performance of semidefinite programming (SDP) relaxations of 𝖬().
Perhaps the simplest of these is based on the inclusion of sets

    ^N ⊆{∈^N × N_: ≽ 0, () = N}^N_𝗌𝗉𝖾𝖼.

Replacing ^N with ^N_𝗌𝗉𝖾𝖼 in the definition of 𝖬() just computes λ_max(), expressing the spectral certificate as an SDP relaxation.
Thus one consequence of Conjecture <ref> is that this naive relaxation is optimal among the wide variety of SDP relaxations that may be applied to 𝖬().

One broad and successful framework for SDP relaxation of optimization problems through which one might hope to find an improvement is the sum-of-squares (SOS) hierarchy of relaxations <cit.>.
This generates a sequence of convex sets we will denote by _d^N, indexed by a parameter d, an even natural number called the degree, which satisfy <cit.> the strict inclusions

    _2^N ⊃_4^N ⊃⋯⊃_N + {N  odd} = ^N.

Moreover, _d^N is a projection of an affine slice of the positive semidefinite cone of N^d / 2× N^d / 2 real symmetric matrices, whereby optimization over _d^N may be written as an SDP.

Unfortunately, though in this SDP both the dimension of the decision variable and the number of constraints scale polynomially with N, and even if we assume (as will be the case in our application) that the SDP coefficients may be well-approximated with an encoding in polynomially many bits (i.e., are of size bounded by exp(𝗉𝗈𝗅𝗒(N))), it still need not be the case that the SDP can be solved to small additive error in polynomial time, as O'Donnell has pointed out <cit.>.
The key point is that one must further ensure that there exists an optimizer of the SDP whose entries are also of size bounded by exp(𝗉𝗈𝗅𝗒(N)).
Fortunately, the work <cit.> studied this issue for sum-of-squares relaxations of many discrete problems, including our setting of unconstrained optimization over Boolean variables, and showed that this condition is in fact satisfied (see their Corollary 9).
Thus optimization over _d^N may indeed be performed in time N^O(d) with, for instance, the ellipsoid algorithm.

To give a concrete formulation of this SDP, we now describe _d^N in terms of the pseudomoment interpretation of SOS optimization (as derived from the general formulation of SOS in, e.g., <cit.>).
Below we adopt the useful notations of [N]k and [N]≤ k for the sets of subsets of [N] having size k and size at most k (including the empty set), respectively.
We also use the standard notation S  T  (S ∖ T) ∪ (T ∖ S) for the symmetric difference of the sets S and T.


    
    _d^N ⊂^N × N_ is the set of matrices  such that there exists ∈^[N]≤ d / 2×[N]≤ d / 2 having
    
    Z_{i}{j} = M_ij  for all  i, j ∈ [N]

    and satisfying the following properties:
    
    
  * ≽ 0.
    
  * Z_ST only depends on S  T.
    
  * Z_ST = 1 whenever S  T = ∅.
    
    In this case, we say  is a degree d pseudomoment matrix for the constraint polynomials {x_i^2 - 1: i ∈ [N]}⊂[x_1, …, x_N], which extends .[Usually, a degree d pseudomoment matrix must be indexed by all monomials in x_1, …, x_N of degree at most d / 2; however, in our case, the constraint x_i^2 = 1 ensures that the pseudomoments of multilinear monomials fully determine the pseudomoment matrix.]

For the sake of brevity, we will simply refer to such  as a degree d pseudomoment matrix, since we only study optimization over {± 1}^N.

    The degree d sum-of-squares relaxation of 𝖬() is
    
    _d() 1/Nmax_∈_d^N, .


In addition to Montanari's general question on certifying bounds on 𝖬() mentioned before, Jain, Risteski, and Koehler have independently posed the more specific question of determining the asymptotic value of _d() when ∼(N) in <cit.>.

One further simplification of the above setup will also be useful to take into account.

    We call ∈^[N]≤ d / 2×[N]≤ d / 2 a reduced degree d pseudomoment matrix if it satisfies all of the conditions of Definition <ref>, as well as the following additional condition:
    
    
  4. Z_ST = 0 whenever |S  T| is odd.
    

As we show below, because of the invariance of both the constraints x_i^2 - 1 = 0 and the objective function ^⊤ under the map ↦ -, _d^N may be equivalently defined in terms of reduced pseudomoment matrices.

    
    If there exists a degree d pseudomoment matrix extending , then there exists a reduced degree d pseudomoment matrix extending .


    It suffices to show that if ^(0) is a degree d pseudomoment matrix, then the matrix ^(1) of the same shape with entries Z^(1)_ST (-1)^|S  T| Z^(0)_ST is also a degree d pseudomoment matrix, since then 1/2^(0) + 1/2^(1) is a reduced degree d pseudomoment matrix whose minor indexed by [N]1 equals that of ^(0).

    Clearly all of the linear constraints on ^(1) are satisfied, so it suffices to check positive semidefiniteness.
    For this, if ^(1)∈^[N]≤ d / 2, let us define ^(0)∈^[N]≤ d / 2 by x^(0)_S = (-1)^|S|x^(0)_S.
    Then, since (-1)^|S| + |T| = (-1)^|S  T|, we have ^(1)^⊤^(1)^(1) = ^(0)^⊤^(0)^(0)≥ 0, completing the proof.


We will only study degree 2 and degree 4 pseudomoment matrices in detail, so we give more concrete versions of the above conditions for those cases.

    
    _2^N = {∈^N × N_ : ≽ 0, M_ii = 1  for all  i ∈ [N]}.


    
    Let ∈^(N(N + 1) / 2 + 1) × (N(N + 1) / 2 + 1)_, with the row and column indices of  identified with [N]≤ 2, ordered first by size and then in lexicographical order.[For instance, [3]≤ 2 is ordered as ∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}.]
    Then,  is a reduced degree 4 pseudomoment matrix if and only if the following conditions hold:
    
    
  * ≽ 0.
    
  * Z_∅∅ = Z_{i}{i} = Z_{i,j}{i,j} = 1 for all distinct i, j ∈ [N].
    
  * Z_{i}∅ = Z_{i,j}{j} = 0 for all distinct i, j ∈ [N].
    
  * Z_{i, j}{i, k} = Z_{j, k}∅ = Z_{j}{k} for all distinct i, j, k ∈ [N].
    
  * Z_{i,j}{k,ℓ} is invariant under permutations of the indices i, j, k, ℓ.
    




 §.§ Prior work on sum-of-squares lower bounds





  
The Montanari-Sen degree 2 lower bound
The only previous result on SOS relaxations of 𝖬() under ∼(N) that we are aware of is the following result of Montanari and Sen <cit.>, which establishes hardness of certification for degree 2 SOS.

    
    Let ϵ > 0.
    Then,
    
    lim_N →∞[_2() ≥ 2 - ϵ] = 1.



The mechanics of this result will be crucial for proving ours, so let us also review how to construct
feasible points achieving this bound. First, fix a parameter δ∈ (0, 1), and set r = r(N) = δ N.[Following <cit.>, we assume for the sake of simplicity that δ N is an integer; recovering the same results for r = ⌊δ N ⌋ is tedious but straightforward.]
    Then, given ∼(N), let V ⊂^N be the subspace spanned by the r(N) eigenvectors of  having the largest eigenvalues, and let  be the orthogonal projector to V.
    Let ∈^N × N be the diagonal matrix with entries D_ii = P_ii, and define
    
    ^(δ) = ^(δ)() ^-1/2^-1/2.

    (Note that D_ii = 0 if and only if e_i ∈ V^⊥, which almost surely does not occur.)
    Then, ^(δ)() ∈_2^N for any δ∈ (0, 1) almost surely, and for each ϵ > 0 there exists δ∈ (0, 1) such that
    
    lim_N →∞[1/N^(δ)(), ≥ 2 - ϵ] = 1.

We call ^(δ) the Montanari-Sen witness.
This construction will be the basis of ours; indeed, we will show that only a small correction is necessary to make this witness feasible for the degree 4 SOS relaxation as well.



  
Simultaneous work on degree 4 lower bounds
After preparing an earlier version of this manuscript, we learned of the concurrent work <cit.>, the fruit of a parallel research effort in which the same result (Corollary <ref>, stated in the following section) as ours is proved.
Their construction uses the pseudocalibration sum-of-squares heuristic introduced in <cit.>, while our construction is based on more geometric and problem-specific considerations of constraints on the pseudomoment extension matrices described above.
We remark that one important advantage of their work is that its analysis is general enough to apply immediately to problems besides the SK model, such as MaxCut on sparse random graphs.

On the other hand, the output of pseudocalibration in this situation appears to be quite complicated: while the degree 4 pseudomoments constructed in <cit.>, like ours, are low-degree polynomials in the entries of , they are not stated explicitly, and are sums of many more “graphical” terms, simple polynomials in the entries of  described by graphs labelled by matrix indices.
For instance, while the formula we will derive for our degree 4 pseudomoments includes just two types of such polynomials (see our Section <ref>), the analysis of the pseudomoments of <cit.> involves at least 20 types (see their Section 3).
Thus, though it is possible that the degree 4 pseudomoment matrices constructed in our work are close to those constructed in <cit.> (in spectral norm, for example), our approach gives a more explicit and condensed description of a suitable pseudomoment construction.

Furthermore, while both this paper and <cit.> use the idea of an “approximate Cholesky decomposition” of the pseudomoment matrix (also present in earlier works such as <cit.>) for the proofs of positive semidefiniteness, we give in Sections <ref> and <ref> an intuitive probabilistic meaning to the Cholesky factors arising in this argument.
To the best of our knowledge, this is a novel interpretation, which we believe may shed new light on the structure of pseudomoment matrices and simplify some of the ad hoc technicalities arising in the proofs of their positive semidefiniteness.



§ RESULTS


Our main result establishes hardness of certification for degree 4 SOS, by showing that a minor variant of the Montanari-Sen witness admits a degree 4 extension.

    
    Let α, δ∈ (0, 1), and let ^(δ) be as in Theorem <ref>.
    Define
    
    ^(α, δ)()  (1 - α)^(δ)() + α I_N.

    Then,
    
    lim_N →∞[^(α, δ)() ∈_4^N ] = 1.


The theorem says that an arbitrarily small adjustment in the direction the identity matrix (the barycenter of the vertices of the cut polytope) suffices to make the degree 2 Montanari-Sen primal witness admit a degree 4 extension with high probability.[The specific choice of the identity matrix is probably not essential, but is convenient because, as we will see, the degree 4 extension of the identity matrix has an especially simple spectral structure.]
In Conjecture <ref>, we will also propose that the same membership holds with high probability for any SOS relaxation _d^N with constant degree d as N →∞.

Since the degree 2 part of our construction is a simple modification of the Montanari-Sen witness, it is straightforward to apply Theorem <ref> and obtain a lower bound for the degree 4 SOS objective.

    
    Let ϵ > 0.
    Then,
    
    lim_N →∞[_4() ≥ 2 - ϵ] = 1.



    By Theorem <ref>, take δ∈ (0, 1) such that 1/N^(δ)(), ≥ 2 - ϵ / 3 with high probability.
    Let α∈ (0, 1) be small that (1 - α)(2 - ϵ / 3) ≥ 2 - 2 ϵ / 3.
    By Theorem <ref>, with high probability,
    
    _4() ≥1/N^(α, δ)(), ≥ 2 - 2ϵ/3 + 1/Nα( W).

    The random variable ( W) has law (0, 2), so with high probability the last term is smaller than ϵ / 3, and the result follows.




  
Organization
The remainder of the paper gives the proof of Theorem <ref>, and conjectures an extension of the same proof technique to higher degree SOS relaxations.
In Section <ref> we review some preliminary facts and notations.
In Section <ref> we give the motivation and precise statement of our construction of a matrix that is with high probability a degree 4 pseudomoment matrix extending ^(α, δ)().
In Section <ref>, we present a natural conjecture for how this construction can be extended to higher degrees.
Finally, in Sections <ref>, <ref>, and <ref>, we prove that our construction from Section <ref> indeed furnishes a valid degree 4 pseudomoment matrix with high probability.



§ PRELIMINARIES





 §.§ Glossary: variables, parameters, and constants


For reference, we summarize various symbols that will appear throughout.
The following are the general scalar parameters involved.


  * N is a parameter indicating the size of ∼(N) in the problem statement.

  * δ∈ (0, 1) is a fixed parameter not depending on N.

  * r = r(N) δ N, which we assume for the sake of simplicity is an integer.
    This gives the rank of the Montanari-Sen witness that we extend (before modifications that make it have full rank)

  * α∈ (0, 1) is another fixed parameter not depending on N or δ.

  * K is a constant appearing in concentration inequalities, giving polynomial rates of decay of probabilities of the form N^-K. All of the concentration inequalities where K appears hold with any choice of K > 0, but the other constants appearing in those results depend on both K and δ. Thus a typical inequality will take the form

    “[quantity≤ O_δ, K(N)] ≥ 1 - O_δ, K(N^-K). ”

One may think of any concrete choice, e.g. K = 100, throughout.

The following are vectors and matrices associated to the Montanari-Sen construction applied to a specific instance .

    
  * ∈^r × N is the matrix having the top r (unit norm) eigenvectors of  as its rows.
    
  * _1, …, _N ∈^r are the columns of  (not eigenvectors of ).
    
  * = ^⊤ is the orthogonal projector to the top r-dimensional eigenspace of , and also the Gram matrix of the _i.
    
  * _i = _i / _i_2.
    
  * ∈^N × N is a diagonal matrix with D_ii = _i_2^2 = P_ii.
    
  * = ^-1/2∈^r × N is the matrix having the _i as its columns.
    
  * = ^(δ) = ^⊤ = ^-1/2^-1/2 is the Montanari-Sen witness, and also the Gram matrix of the _i. For the sake of brevity, we will often drop the (δ) superscript, as δ will be a constant carried throughout.




 §.§ Other notation




  
Linear algebra The identity matrix in dimension n is denoted I_n, and the all-ones vector is denoted _n.
The Frobenius or entrywise inner product of matrices having the same shape is denoted ,  = (^⊤) = ∑_i, j A_ijB_ij.
The Hadamard or entrywise product of matrices having the same shape is denoted ∘ and has entries (∘)_ij = A_ijB_ij.
Hadamard powers of a matrix are denoted ^∘ k.
The matrix operator norm is denoted _ = max__2 = _2 = 1^⊤.
The vectorized supremum norm is denoted _ℓ^∞ = max_i, j |A_ij|.
The matrix Frobenius norm is denoted _F = , ^1/2.
The group of N × N orthogonal matrices is denoted (N).
The Stiefel manifold of r × N matrices with orthonormal rows is denoted 𝖲𝗍𝗂𝖾𝖿(N, r).



  
Vectorization We describe several ways of vectorizing symmetric matrices. For ∈^n × n_, we let () ∈^n and () ∈^n(n - 1) / 2 be the vectorized diagonal and strict upper triangle of , respectively, with index sets ordered lexicographically.
These two vectors determine a symmetric matrix completely.
It will also be useful to define an isometry between ^n × n_ endowed with the Frobenius inner product and ^n(n + 1) / 2 endowed with the ordinary Euclidean inner product.
This is given by

    () [[      (); √(2)·() ]],

which indeed satisfies (), ()  = ,.
We denote _( I_n) when the dimension n is clear from context, since this is the indicator vector of the diagonal matrix indices.



  
Probability We denote the relation of two random variables X, Y having the same law by X  Y.
The Haar measure on the orthogonal group or Stiefel manifold is denoted 𝖧𝖺𝖺𝗋((N)) or 𝖧𝖺𝖺𝗋(𝖲𝗍𝗂𝖾𝖿(N, r)), respectively, and refers to Haar measure with respect to the action of (N) by right multiplication in the latter case.
We write 𝖴𝗇𝗂𝖿(^N - 1) for the Haar measure on vectors of the unit sphere under the action of (N) by left multiplication, equivalent to 𝖧𝖺𝖺𝗋(𝖲𝗍𝗂𝖾𝖿(N, 1)) (up to transposition).



 §.§ Basic properties of the Montanari-Sen witness


It will be useful to establish some preliminary bounds on and distributional properties of the Montanari-Sen construction described in Theorem <ref>.

First, we use an elegant geometric argument mentioned in <cit.> (but which seems to be well-known folklore) to obtain bounds on the entries of .

    
    For all K > 0,
    
    [max_i, j ∈ [N]{[ |P_ii - δ|         if      i = j;     |P_ij|         if      i ≠ j ]}≤ O_δ, K(√(log N/N)) ] ≥ 1 - O_δ, K(N^-K).



 For the diagonal entries, P_ii = _i_2^2 _0_2^2 for ∼𝖴𝗇𝗂𝖿(^N - 1) and _0 the orthogonal projector onto 𝗌𝗉𝖺𝗇(_1, …, _r).
    Letting ∼( 0,  I_N), we have / _2.
    Writing ^(r) and ^(N - r) for the first r and last N - r coordinates of  respectively, we then have
    
    P_ii^(r)_2^2/^(r)_2^2 + ^(N - r)_2^2,

    where ^(r)_2^2 and ^(N - r)_2^2 are distributed as independent χ^2 random variables with r and N - r degrees of freedom respectively.
    The result then follows from the concentration inequalities of <cit.> for χ^2 random variables.

    For the off-diagonal entries, likewise P_ij = _i, _j _0, _0, where now (, ) are a Haar-distributed two-dimensional orthonormal frame.
    If we draw , ∼( 0,  I_N) independently, then by performing two steps of Gram-Schmidt orthonormalization,
    
    (, ) (/_2,  - , /_2^2/ - , /_2^2_2).

    Thus computing as before we find
    
    P_ij^(r), ^(r) - , ^(r)_2^2/^(r)_2^2 + ^(N - r)_2^2/_2 - , /_2^2_2.

    To control these quantities, we first bound
    
    |^(r), ^(r) - , ^(r)_2^2/^(r)_2^2 + ^(N - r)_2^2/_2 - , /_2^2_2| ≤|^(r), ^(r)| + |, |/_2(_2 - |, |/_2).

    In this expression, every ℓ^2 norm may be controlled by the concentration inequalities of <cit.> as before, and every inner product may be controlled by observing that, when  and  are independent standard gaussian vectors, then , _2 h_1, thus reducing the task of controlling the inner product to controlling an ℓ^2 norm.
    Applying these bounds then gives the result.


The following related results for  follow directly.

    
    For all K > 0,
    
    [max_i, j ∈ [N]{[ |M_ii - 1|         if      i = j;     |M_ij|         if      i ≠ j ]}≤ O_δ, K(√(log N/N)) ] ≥ 1 - O_δ, K(N^-K).



    We have M_ij = P_ij / √(P_iiP_jj), so the result follows from combining Proposition <ref> applied to several entries.



    
    For all K > 0,
    
    [_≤δ^-1 + O_δ, K(√(log N/N))] ≥ 1 - O_δ, K(N^-K).



    = ^-1/2^-1/2, so _≤^-1/2_^2 = (min_i ∈ [N] P_ii)^-1, and the result then follows by Proposition <ref>.




 §.§ Moments of ((N))


The following gives the low-degree moments of Haar-distributed orthogonal matrices.


    
    Let ∼((N)).
    The moment ∏_k = 1^d Q_i_kj_k is zero if any index occurs an odd number of times among either the i_k or j_k.
    The non-zero degree 2 and 4 moments are given by
    
    Q_11^2    = 1/N, 
     Q_11^4    = 3/N(N + 2), 
     Q_11^2Q_12^2    = 1/N(N + 2), 
     Q_11^2Q_22^2    = N + 1/(N - 1)N(N + 2), 
     Q_11Q_12Q_21Q_22   = -1/(N - 1)N(N + 2).





§ DEGREE 4 PSEUDOMOMENT CONSTRUCTION



In this section we outline the main idea in the proof of Theorem <ref>, detailing the construction of a suitable degree 4 pseudomoment matrix and reducing Theorem <ref> to verifying the positive semidefiniteness of this matrix.

First, we give two heuristic lines of reasoning supporting the construction we propose.
The first derives a formula for the degree 4 pseudomoment extension of a highly structured collection of degree 2 pseudomoments and assumes that this formula may be transferred verbatim to the random case.
The second recovers the same formula after applying some simplifying heuristics to a probabilistic argument.

As a preliminary, let us remark that, per Proposition <ref>, we may restrict our attention to reduced degree 4 pseudomoment matrices.
If  is a reduced degree 4 pseudomoment matrix extending , and we divide  into blocks indexed by [N]0, [N]1, and [N]2, where ^[i, j] is the block with rows indexed by [N]i and columns indexed by [N]j, then only the block ^[2, 2] is not determined by the properties of being reduced and extending :

    [ 4pt [ ^[0, 0] ^[0, 1] ^[0, 2]; ^[1, 0] ^[1, 1] ^[1, 2]; ^[2, 0] ^[2, 1] ^[2, 2] ]] = [ 4pt [       1       0    ()^⊤;       0               0;      ()       0 ^[2, 2] ]].

Thus in the sequel we will be justified in saying that an extension  of  is specified just by a particular choice of ^[2, 2].



 §.§ Heuristic 1: evidence from equiangular tight frames




In this section, we review a result from the works <cit.> of the authors', which derived an explicit description of degree 4 extensions of degree 2 pseudomoment matrices for some very structured special cases, that resemble the Montanari-Sen witness in that their degree 2 pseudomoment matrices are constant multiples of orthogonal projectors.

The extra structure that allows this description of the degree 4 pseudomoments to be derived in closed form is described by the following notions from finite frame theory.

    A collection of vectors _1, …, _N ∈^r forms a unit norm tight frame (UNTF) if the following conditions hold.
    
        
  * (Unit Norm) _i_2 = 1 for all i ∈ [N].
        
  * (Tight Frame) ∑_i = 1^N _i_i^⊤ = N/r I_r.
    
    They moreover form an equiangular tight frame (ETF) if the following additional condition holds.
    
    
  3. (Equiangular) There is μ∈ [0, 1] such that |_i, _j  | = μ whenever i ≠ j.
    

ETFs are rare and combinatorially structured objects <cit.>, which do not seem a priori related to the SK problem and the Montanari-Sen witness.
However, it turns out that studying the degree 4 extensions of ETFs gives useful insight into the correct construction of pseudomoments even in the random case.

In general, we showed in <cit.> that degree 4 extensions are related to the following notion from convex geometry.

    Let K ⊆^d be a closed convex set.
    For ∈ K, the perturbation of  in K is the linear subspace
    
    𝗉𝖾𝗋𝗍_K() {∈^d: ± t∈ K  for all  t > 0  sufficiently small }.

    Equivalently, if H is the affine hull of the minimal face of K that  belongs to, then 𝗉𝖾𝗋𝗍_K() = H -.

The relevant case for degree 4 extensions is K = _2^N.
In this case, the following theorem characterizes the perturbation subspace.

    
    Let ∈_2^N have () = r and = ^⊤ for ∈^r × N with unit vector columns _1, …, _N.
    Then,
    
    𝗉𝖾𝗋𝗍__2^N()
             = {^⊤: ∈^r × r_}∩{∈^N × N: () =  0 }
       = {^⊤: ∈^r × r_, _i^⊤_i = 0  for  i ∈ [N] }
       = ^⊤( 𝗌𝗉𝖺𝗇({_1_1^⊤, …, _N_N^⊤})^⊥) .



For ETFs, a degree 4 extension, when any exists, is given explicitly in both spectral and entrywise terms as follows.

    
    Let ∈_2^N be the Gram matrix of an ETF of N vectors in ^r.
    Then, ∈_4^N if and only if N < r(r + 1)/2.
    In this case, a degree 4 extension ∈^(N(N + 1) / 2 + 1) × (N(N + 1) / 2 + 1)_ is given by
    
    ^[2,2] = ()()^⊤ + N^2(1 - 1/r)/r(r + 1) - 2N_(𝗉𝖾𝗋𝗍__2^N())

    and the block structure given in (<ref>).
    The entries of this matrix are given by
    
    Z_{i,j}{k,ℓ}^[2,2]   = r(r - 1)/2/r(r + 1)/2 - N(M_ijM_kℓ + M_ikM_jℓ + M_iℓM_jk) 
       - r^2(1 - 1/N)/r(r + 1)/2 - N∑_m = 1^N M_imM_jmM_kmM_ℓ m.


(The spectral description will be of interest later, to draw a connection to the second heuristic presented in the following section.)

The Montanari-Sen witness  is close to a constant multiple of a projection matrix, since by Proposition <ref> all entries of the normalizing diagonal matrix  are close to δ, so  is a “near-UNTF Gram matrix.”
Also, the off-diagonal entries of  are inner products of random unit vectors _i, which it is reasonable to think are weakly dependent, whereby  should moreover behave like “an ETF in expectation.”

Thus to guess a degree 4 extension for the Montanari-Sen witness , we may be justified in simply trying to apply the combinatorial ETF construction directly.
Since we take r = δ N with r, N →∞, we may also simplify the leading coefficients to their asymptotic values, which gives the prediction

    “Z_{i,j}{k,ℓ}^[2,2] = M_ijM_kℓ + M_ikM_jℓ + M_iℓM_jk - 2 ∑_m = 1^N M_imM_jmM_kmM_ℓ m.”




 §.§ Heuristic 2: conditional covariance of gaussian matrices




We next show another, perhaps more principled argument through which we arrive at the same prediction of degree 4 pseudomoments.
Let us suppose that  is exactly the Gram matrix of a UNTF, i.e. = δ^-1 = δ^-1^⊤ and () = δ_N.
As mentioned above, this is approximately the case for the Montanari-Sen witness, but our heuristic derivation is much simplified if the correction by the diagonal matrix  to form the actual Montanari-Sen witness may be reduced to a constant scaling.

For the computations to come it is more convenient to view ^[2, 2] as being embedded in a larger pseudomoment matrix, indexed by pairs (i, j) ∈ [N]^2.
We denote this matrix by ^𝗆𝗎𝗅𝗍[2, 2], and, following the pseudomoment framework discussed before, set Z^𝗆𝗎𝗅𝗍[2, 2]_(i, j)(k, ℓ) to be the “pseudoexpectation” of the monomial x_ix_jx_kx_ℓ.
In terms of ^[2, 2] and , these entries are

    Z^𝗆𝗎𝗅𝗍[2, 2]_(i, j)(k, ℓ) = {[ Z^[2, 2]_{i, j}{k, ℓ} if  i ≠ j  and  k ≠ℓ,;                  M_ij            if  k = ℓ,;                  M_kℓ            if  i = j. ].

We note that if  is positive semidefinite then so is ^𝗆𝗎𝗅𝗍[2, 2], since, up to removing repeated rows and columns, the latter is equal to the principal minor of the former indexed by {∅}∪[N]2.

Now, we view ^𝗆𝗎𝗅𝗍[2,2], a positive semidefinite N^2 × N^2 matrix, as the degree 2 moment matrix of the entries of a gaussian random matrix: we suppose there exists some ∈^N × N with random jointly gaussian entries such that

    Z_(i,j)(k,ℓ)^𝗆𝗎𝗅𝗍[2,2] =  [A_ijA_kℓ].

We then design  so that ^𝗆𝗎𝗅𝗍[2, 2] automatically satisfies some of the necessary constraints, and hope that the remaining constraints will be approximately satisfied as well.

We begin with a matrix ^(0) having a canonical gaussian distribution for symmetric matrices, the GOE, suitably rescaled to allow us a normalizing degree of freedom later: A_ii^(0)∼(0, 2σ^2) and A_ij^(0) = A_ji^(0)∼(0, σ^2).
Taking  to be symmetric already ensures some of the symmetry conditions that ^𝗆𝗎𝗅𝗍[2,2] must satisfy.
Next, we take  to have the distribution of ^(0), conditional on the following two properties:

    
  * ( I_N - ) = 0.
    
  * A_ii = 1 for all i ∈ [N].

Property 1 ensures that any symmetric matrix formed from ^𝗆𝗎𝗅𝗍[2, 2] by “freezing” one index pair (i, j) and letting the other index pair vary, ^(i, j) (Z_(i, j)(k,ℓ)^𝗆𝗎𝗅𝗍[2, 2])_k, ℓ = 1^N, has row (or column) space contained in that of .
Every ^𝗆𝗎𝗅𝗍[2, 2] constructed as above must have this property, because it has a principal minor of the form

    [[         ^(i, j); ^(i, j)         ]]

whose positive semidefiniteness gives this condition on ^(i, j).
Property 2 ensures that Z_(i,i)(k,ℓ)^𝗆𝗎𝗅𝗍[2,2] does not depend on the index i, which is required by our definition of ^𝗆𝗎𝗅𝗍[2,2] above, and reflects the application of the polynomial constraint x_i^2 = 1 to the monomial x_i^2x_kx_ℓ.

What is the law of the resulting gaussian matrix ?
Conditioning on Property 1 yields the law of ^(0) = (^⊤^(0))^⊤.
By rotational invariance of the GOE, the inner matrix ^⊤^(0)^(1)∈^r × r_ has the same law as the upper left r × r block of ^(0), i.e., a smaller GOE matrix with the same variance scaling of σ^2.

Next, we condition on Property 2, or equivalently condition ^(1) on having _i^⊤^(1)_i = _i_i^⊤, ^(1) = 1.
^(1) has the law of ^-1() for a gaussian vector ∼( 0, 2σ^2  I_r(r + 1) / 2).
Since  is an isometry, we may equivalently condition  on , (_i_i^⊤)  = 1 for each i ∈ [N].
By basic properties of gaussian conditioning, the resulting law is

    (∑_i = 1^N ((^∘ 2)^-1)_i (_i_i^⊤), 2σ^2 ( I -  P)),

where ^∘ 2 is the Gram matrix of the (_i_i^⊤) or equivalently the entrywise square of , and P is the orthogonal projector to the span of the (_i_i^⊤).
Let ^(2) be a matrix with the law of ^-1 applied to the law in (<ref>).

Having finished the conditioning calculations, we may now obtain the statistics of .
Recall that A_ij = _i^⊤^(2)_j = 1/2(_i_j^⊤ + _j_i^⊤), ^(2).
Applying  to each matrix and using the expression derived above, we find the mean and covariance

    [A_ij]    = ∑_m = 1^N ((^∘ 2)^-1)_k P_imP_jm, 
    𝖢𝗈𝗏[A_ij, A_kℓ]    = σ^2/2(_i_j^⊤ + _j_i^⊤)^⊤ ( I -  P)(_k_ℓ^⊤ + _ℓ_k^⊤).

Next, we make two simplifying approximations.
For the means, we approximate

    ^∘ 2≈δ I + δ/r_N_N^⊤,

which gives

    [A_ij] ≈δ^-1P_ij = M_ij.

For the covariances, since under our assumptions we have  (_i_i^⊤)_2 = _i_i^⊤_F = _i_2^2 = δ, we approximate

    ≈δ^-2∑_i = 1^N (_i_i^⊤)(_i_i^⊤)^⊤,

which gives

    𝖢𝗈𝗏[A_ij, A_kℓ] ≈σ^2(P_ikP_jℓ + P_iℓP_jk - 2δ^-2∑_m = 1^N P_imP_jmP_kmP_ℓ m).


Finally, to recover what this prediction implies for the entries of ^𝗆𝗎𝗅𝗍[2,2], we compute

    Z_(i,j)(k,ℓ)^𝗆𝗎𝗅𝗍[2,2]   = [A_ijA_kℓ] 
       = [A_ij][A_kℓ] + 𝖢𝗈𝗏[A_ij, A_kℓ] 
       = M_ijM_kℓ + σ^2(P_ikP_jℓ + P_iℓP_jk - 2δ^-2∑_m = 1^N P_imP_jmP_kmP_ℓ m).

We then choose σ^2 such that Z_(i,i)(i,i)^𝗆𝗎𝗅𝗍[2,2] = 1, which requires σ^2 = δ^-2, and, restricting to i ≠ j and k ≠ℓ, we recover the same formula as (<ref>):

    “Z_{i,j}{k,ℓ}^[2,2] = M_ijM_kℓ + M_ikM_jℓ + M_iℓM_jk - 2 ∑_m = 1^N M_imM_jmM_kmM_ℓ m.”



    It is worth noting the intriguing geometric interpretation of the random matrix  we have constructed: we have =, ( A) = deterministically, and  fluctuates in the linear subspace 𝗉𝖾𝗋𝗍__2^N() (as may be verified from the covariance formula (<ref>) and is intuitive by analogy with the ETF case of Section <ref>).
    Thus,  behaves, roughly speaking, like a random element of _2^N (except that there is no enforcement of positive semidefiniteness), which lies on the same face of _2^N as  and fluctuates gaussianly about  along this face.




 §.§ Precise construction details




Having intuitively motivated the a priori unusual degree 4 pseudomoment formula given (identically) in (<ref>) and (<ref>) in the previous two sections, we now give the precise details of how this may be adjusted to produce an actually valid degree 4 pseudomoment extension of (1 - α) + α I_N, the “nudged” Montanari-Sen witness.
It is instructive to view our construction as first attempting to build an extension of  itself, then introducing the adjustment towards I_N as a necessity to ensure positive semidefiniteness.



  
Step 1: Heuristic pseudomoments

We first build ∈^[N]≤ 2×[N]≤ 2 that is a reasonable prediction of a reduced degree 4 pseudomoment extension of .
Viewing  as a 3 × 3 block matrix as in (<ref>), all blocks but the lower right are prescribed by the properties of being reduced and extending , so we have

    = [ 5pt [       1       0    ()^⊤;       0               0;      ()       0 ^[2, 2] ]].

We complete the definition by defining ^[2,2] using the heuristics described earlier.
Namely, we take

    X^[2, 2]_{i,j}{k,ℓ} M_ijM_kℓ + M_ikM_jℓ + M_iℓM_jk - 2∑_m = 1^N M_imM_jmM_kmM_ℓ m.

Reviewing the constraints required of  per Proposition <ref>, we see that  satisfies the permutation symmetry constraints (Condition 5 in the Proposition) and the normalization and reduction constraints (Conditions 2 and 3, respectively) exactly, and satisfies the other linear constraints which require X^[2, 2]_{i,j}{i,k} = M_jk (Condition 4) approximately.
Finally, the discussion of Sections <ref> and <ref> suggests that  should also be positive semidefinite (Condition 1).



  
Step 2: Correction to satisfy linear constraints

We next correct  to satisfy exactly all linear constraints required for a degree 4 pseudomoment matrix, by adjusting ^[2, 2] to satisfy Condition 4 of Proposition <ref>.
Define an additive correction Δ∈^[N]2×[N]2 by

    Δ_{i,j}{k,ℓ}   = 0  if  |{i, j, k, ℓ}| = 4, 
    Δ_{i,k}{i,ℓ}   = ∑_m = 1 
     m ≠ i^N M_im^2M_kmM_ℓ m.

(Note that the second part of the definition is consistent when k = ℓ regardless of whether we view i or k as the repeated index.)

Then, we set

    + [ 5pt [  0  0  0;  0  0  0;  0  0 2Δ ]],

and  satisfies Conditions 2 through 5 of Proposition <ref> exactly.
However, as we will see, ^[2, 2] is a low-rank matrix, while Δ acts non-trivially on components of the null space of ^[2, 2].
Therefore, even if ≽ 0 (which, as we will see, is nearly true), we will still have ⋡ 0 due to the fluctuations in Δ.



  
Step 3: Correction to satisfy positive semidefiniteness

Finally, we introduce a second correction to counteract the fluctuations in the spectra of ^[2, 2] and Δ.
We note that the identity matrix I_[N]≤ 2 is in fact a valid degree 4 pseudomoment matrix, which extends I_N ∈^N.
Indeed, I_N is a natural choice of a point of ^N towards which to “push”  in order to regularize our construction, because I_N is the barycenter of the vertices of ^N, i.e., I_N = 1/2^N∑_∈{± 1}^N^⊤.

Following this intuition, given a choice of the parameter α∈ (0, 1), we set

    Z
            (1 - α) + α I_[N]≤ 2
       = [ 2pt [                         1                         0               (1 - α)()^⊤;                         0           (1 - α) + α I_N                         0;                 (1 - α)()                         0 (1 - α)^[2, 2] + α I_[N]2 ]].

Clearly,  extends (1 - α) + α I_N ∈_2^N and satisfies all linear constraints on a degree 4 pseudomoment matrix (since both  and I_[N]≤ 2 do so).
Thus to show (1 - α) + α I_N ∈_4^N, it suffices to show ≽ 0, in which case  will be a degree 4 pseudomoment extension.
Theorem <ref> will then be proved if we show that ≽ 0 with high probability.



§ CONJECTURAL HIGHER-DEGREE EXTENSION




Before proceeding to the proofs, we mention that there is a natural extension of the heuristic for pseudomoment construction of Section <ref> that appears promising, though difficult to analyze, for higher-degree SOS relaxations.

The idea is to view higher-order pseudomoments as the second moments of symmetric gaussian tensors, which, as done in Section <ref> for matrices, are formed by conditioning a certain canonical symmetric tensor distribution on desirable properties.
Suppose we want to predict the degree d = 2k pseudomoment extension ^𝗆𝗎𝗅𝗍[k, k]∈^[N]^k × [N]^k of the Montanari-Sen witness ∈_2^N (which, as before, we assume to be an exact unit norm tight frame, i.e., a constant multiple of ), where, extending the case k = 2 from Section <ref>, the entry indexed by i,  j ∈ [N]^k is the pseudoexpectation of ∏_ℓ = 1^kx_i_ℓ∏_ℓ = 1^k x_j_ℓ.
We do this by building a symmetric tensor ^(k)∈𝖲𝗒𝗆^k(^N) with jointly gaussian entries, and setting, for i,  j ∈ [N]^k,

    Z_ i  j^𝗆𝗎𝗅𝗍[k, k] = [A_ i^(k)A_ j^(k)].


To describe the law of ^(k), we first define the following tensorial generalization of the GOE (see, e.g., <cit.> for properties of this distribution analogous to those of the GOE).

    Let ∈ (^N)^⊗ k have i.i.d. entries distributed as (0, 1).
    Then, write ^N, k(σ^2) for the law of ∈𝖲𝗒𝗆^k(^N) ⊂ (^N)^⊗ k defined by
    
    A_ = σ/k!∑_π∈ S_k G_i_π(1)i_π(2)⋯ i_π(k).


Now, we define ^(k) inductively over k as a family of coupled gaussian tensors, and ensure that the pseudomoment matrices thus formed are consistent with one another.
Namely, we proceed as follows.
Let i ∘ j denote the concatenation of finite strings in the alphabet [N].

    
  * Let A^(0)_∅ = 1.
    
  * For k ≥ 1, let ^(k) have the law ^N, k(σ_k^2), conditioned on the following two properties:
        
        
  * (Subspace Property) For i ∈ [N]^k - 1, let ^(k)[ i]  (A_ i ∘ (j)^(k))_j = 1^N ∈^N.
        Then, for all i ∈ [N]^k - 1, ( I -  P)^(k)[ i] =  0.
        
  * (Consistency Property) For i ∈ [N]^k - 2 and j ∈ [N], A^(k)_ i ∘ (jj) = A^(k - 2)_ i.
        
    
The constants σ_k^2 remain as free parameters to be tuned to ensure normalization, as in the case k = 2 from Section <ref>.

Based on this reasonable generalization, we offer two conjectures.
First, we believe that whatever adjustments are necessary to this construction are already captured in the simple adjustment of the Montanari-Sen witness towards the identity matrix given in Theorem <ref>.

    
    For any α, δ∈ (0, 1) and d ∈ 2,
    
    lim_N →∞[ ^(α, δ)() ∈_d^N ] = 1.



More specifically but less formally, we believe the construction presented above is approximately the correct degree d pseudomoment extension.



    For δ∈ (0, 1), let ^(δ) be the Montanari-Sen witness.
    Then, for fixed d ∈ 2 and constants σ_k^2 depending only on δ, with high probability as N →∞, the entries of ^𝗆𝗎𝗅𝗍[k, k] as defined above give a “nearly” valid degree d = 2k pseudomoment extension of ^(δ).


We have tested Conjecture <ref> numerically on Laurent's construction <cit.> of higher-degree pseudomoment matrices extending a deterministic ∈_2^N, which indeed forms the Gram matrix of an ETF.
Laurent's construction shows that certain parity inequalities holding over ^N are not certified by SOS until d ∼ N.
We find that the results, for suitable tuning of σ_k^2, agree with Laurent's construction (with no further adjustment needed).
Thus one pleasant consequence of verifying Conjecture <ref> may be a novel proof of Laurent's theorem, whose original proof involves first predicting the entries of the pseudomoment matrix and then appealing to a technical analysis of hypergeometric functions to verify positive semidefiniteness.

We remark that we have also verified algebraically in our earlier paper <cit.> that, for degree 4, the construction in Theorem <ref> (before simplifying in the N →∞ asymptotic regime) exactly recovers Laurent's construction.
This also would not be the first simplified proof of Laurent's theorem; for instance, the work <cit.> gives a general treatment of sum-of-squares relaxations of combinatorial optimization problems with highly symmetric formulations, and also produces a Cholesky-type decomposition of the relevant pseudomoment matrix.
However, the idea we outline above both would unify such results with those for less symmetric problems, and would give a natural interpretation of the Cholesky factors in such a decomposition as the random variables that are the entries of the tensors ^(k).

Finally, let us remark on what seems to be the major difficulty in analyzing this construction.
By analogy with the analysis in Section <ref>, we are eventually led, in conditioning on the Consistency Property, to attempt to approximate the orthogonal projector to the “repeated indices subspace”

    V^(k)   = 𝗌𝗉𝖺𝗇({_i ⊙_i ⊙_j_1⊙⋯⊙_j_k - 2 : i ∈ [N],  j ∈ [N]^k - 2}) 
       = 𝗌𝗉𝖺𝗇({_i ⊙_i ⊙ A: i ∈ [N],  A ∈𝖲𝗒𝗆^k - 2(^r) }) 
       ⊂𝖲𝗒𝗆^k(^r).

(Here ⊙ denotes the symmetric product of tensors; see, e.g., <cit.> for definitions. We mean “orthogonal projection” with respect to the Frobenius or entrywise inner product of general non-symmetric tensors, into which symmetric tensors are embedded by repeating entries.)
When k = 2, the spanning set consists of the N linearly independent and roughly orthogonal tensors _i^⊙ 2, which allows the orthogonal projection to be estimated by the sum of rank one projections as in (<ref>).
However, when k ≥ 3, there does not appear to be a clear way to choose a convenient approximately-orthogonal basis to carry out the calculation.
The collection of tensors _i^⊙ 2⊙_j_1⊙⋯⊙_j_k - 2 is highly overcomplete, since the _i themselves are an overcomplete set in ^r (and the symmetric tensor product is distributive, so any dependence among the _i is inherited by the ⊙_i for any symmetric tensor ).
Moreover, even the subspaces V^(k)_i _i^⊙ 2⊙𝖲𝗒𝗆^k - 2(^r) intersect non-trivially; for instance, _i^⊙ 2⊙_j^⊙ 2∈ V^(4)_i ∩ V^(4)_j.
Thus it appears that a deeper understanding of the structure of these subspaces of symmetric tensors is required to form the correct higher-degree analogue of (<ref>).



§ PROOF OF POSITIVE SEMIDEFINITENESS: FIRST STEPS




Recall that, in Section <ref>, we built from the Montanari-Sen witness  and an additional constant α∈ (0, 1) the matrix

    = [ 4pt [ ^[0, 0] ^[0, 1] ^[0, 2]; ^[1, 0] ^[1, 1] ^[1, 2]; ^[2, 0] ^[2, 1] ^[2, 2] ]] 
       = [ 2pt [                         1                         0               (1 - α)()^⊤;                         0           (1 - α) + α I_N                         0;                 (1 - α)()                         0 (1 - α)^[2, 2] + α I_[N]2 ]]

and found that to prove Theorem <ref> it suffices to show that ≽ 0 with high probability.
We now give some technical preliminaries for the proof of this.

First, note that, after permuting rows and columns,  is the direct sum of (1 - α) + α I_N, which is positive semidefinite by assumption, with the principal minor of  indexed by {∅}∪[N]2.
Thus to show that ≽ 0 it suffices to show that the latter minor is positive semidefinite.

Second, we may reduce the dimensionality of this remaining task by taking the Schur complement criterion for positive semidefiniteness with respect to the upper left entry, indexed by (∅, ∅), whose value is 1.
The condition of positive semidefiniteness of the Schur complement is then

    / ^[0, 0]
        =  Z^[2, 2] -  Z^[2, 0] Z^[0, 2]
        = α I_N(N - 1)/2 + (1 - α)^[2, 2] - (1 - α)^2()()^⊤
        = α I_N(N - 1)/2 + (1 - α)(^[2, 2] + 2Δ) - (1 - α)^2()()^⊤
       ?≽ 0.

We reorganize this expression as

    / ^[0, 0]   = ^(1) + ^(2),  where 
    ^(1)   = 1/2α I_N(N - 1) / 2
        + (1 - α)(^[2, 2] - (1 - α)()()^⊤_^(1a)), 
    ^(2)   = 1/2α I_N(N - 1) / 2 + 2(1 - α)Δ.

To show ≽ 0, it then suffices to show that both ^(1)≽ 0 and ^(2)≽ 0.
We refer to these as the “main term” and the “correction term,” respectively.

In this decomposition, we split between ^(1) and ^(2) the extra term α I_N(N - 1) / 2 that we introduced when nudging our pseudomoment matrix towards the identity.
This term will act as a “barrier” against small fluctuations that might spoil positive semidefiniteness.
We will show that without this adjustment ^(1) and ^(2) are nearly positive semidefinite already, having the magnitude of their smallest (most negative) eigenvalue tending to zero as N →∞ for any fixed δ.
Thus any choice of α > 0 will suffice to ensure that ≽ 0 with high probability.

More specifically, we will show the following results.

    
    For all δ∈ (0, 1),
    
    lim_N →∞[|min{0, λ_min(^(1a))}| ≤ O_δ(log N/N^1/4)] = 1.




    
    For all δ∈ (0, 1),
    
    lim_N →∞[Δ_≤ O_δ(log^2 N/N^1/4)] = 1.



From Lemmata <ref> and <ref>, it follows that with high probability ≽ 0 for any α∈ (0, 1) fixed as N →∞ (or for α = α(N) decreasing sufficiently slowly with N, though for the sake of simplicity we will not pursue this minor strengthening of the results).
Theorem <ref> then follows.
It remains only to prove the Lemmata; in Section <ref> we will prove Lemma <ref>, and in Section <ref> we will prove Lemma <ref>.



§ PROOF OF POSITIVE SEMIDEFINITENESS: MAIN TERM




In this section we prove Lemma <ref>.
We have

    Z^(1a)_{i,j}{k,ℓ}
       = X^[2, 2]_{i,j}{k,ℓ} - (1 - α)M_ijM_kℓ
       = α M_ijM_kℓ + M_ikM_jℓ + M_iℓM_jk - 2∑_m = 1^N M_imM_jmM_kmM_ℓ m.

Consider the quadratic form ^⊤^(1a), where we think of a_{i,j} = 2A_ij for some symmetric matrix  with () =  0 (i.e., = 2 ·()).
Writing _1, …, _N ∈^N for the columns of ,

    ^⊤^(1a)   = α()^2 + 2() - 2∑_i = 1^N (_i^⊤_i)^2 
       = α(^⊤)^2 + 2^⊤_F^2 - 2∑_i = 1^N (_i^⊤^⊤_i)^2.

Writing the above as a quadratic form in (^⊤), we obtain the following.

    
    Define
    
    ^(1a)α__^⊤ + 2  I_r(r + 1) / 2 - 2 ∑_i = 1^N (_i_i)(_i_i)^⊤.

   (Recall that _( I_r).)
    Then,
    
    λ_min(^(1a)) ≥min{0, λ_min(^(1a))/2min_i ∈ [N]D_ii^2}.



    Since the right-hand side of (<ref>) is at most zero, it suffices to consider the case that λ_min(^(1a)) < 0.
    By (<ref>), we have
    
    ()^⊤^(1a)() = (^⊤)^⊤^(1a)(^⊤).

    Note first that
    
    ^⊤_F^2
             = () 
       = (^-1/2^-1/2^-1/2^-1/2) 
       = , ^-1/2^-1/2^-1/2^-1/2
       ≤(^-1/2^-1/2^-1/2^-1/2) 
       ≤((^-1/2^-1/2)(^-1/2^-1/2)) 
       = ^-1/2^-1/2_F^2 
       ≤_F^2/min_i ∈ [N] D_ii^2.

    Then, recalling that _2^2 = 2_F^2 and (^⊤)_2^2 = ^⊤_F^2, by the variational description of the minimum eigenvalue we have
    
    λ_min(^(1a)) 
       = min_∈^N(N - 1) / 2∖{ 0}^⊤^(1a)/_2^2and noting that, since we assume λ_min(^(1a)) < 0, the  achieving the minimum has ^⊤^(1a) < 0, so we may continue   ≥1/2min_i ∈ [N] D_ii^2min_∈^N(N - 1) / 2∖{ 0}^⊤^(1a)/^⊤_F^2by (<ref>)
       =  1/2min_i ∈ [N] D_ii^2min_∈^N(N - 1) / 2∖{ 0}(^⊤)^⊤^(1a)(^⊤)/(^⊤)_2^2
       ≥λ_min(^(1a))/2min_i ∈ [N] D_ii^2,

    completing the proof.


We will thus focus our attention on ^(1a).
Analyzing the Wishart-type matrix formed by the third term of (<ref>), ∑_i = 1^N (_i_i)(_i_i)^⊤, will be our main difficulty.
Since _i_i^⊤ = 1/r I_r, we center the vectors involved, and decompose this term as

    ^(1a)   = (α - 2N/r^2) __^⊤ + 2  I_r(r + 1) / 2
       + 2/r((∑_i = 1^N _i_i^⊤ - N/r I_r)_^⊤ + _(∑_i = 1^N _i_i^⊤ - N/r I_r)^⊤)_^(1)
       - 2∑_i = 1^N (_i_i - 1/r I_r)(_i_i - 1/r I_r)^⊤_^(2).

The remaining analysis involves a delicate balance between requirements in controlling ^(1) and ^(2).
In order to bound the cross-term ^(1), we will rely on the strong concentration of the eigenvalues of ^⊤ that is created by the dependencies among the _i (this is the “near-UNTF Gram matrix” behavior of ).
In particular, this concentration is much stronger than if _i were replaced with any reasonable distribution of i.i.d. unit vectors, and this portion of our argument would fail for i.i.d. vectors (see Remark <ref>).

On the other hand, in order to bound the term ^(2), we will need to take advantage of the weak dependence of the _i, and formalize the intuition that because N ≪ r(r + 1) / 2 and ^(2) is a sum of weakly dependent rank-one orthogonal projectors, ^(2) should itself behave approximately as an orthogonal projector to a subspace of dimension N (though we will discuss one important caveat to this intuition in Remark <ref>).
Technically, we will appeal to Lipschitz concentration inequalities for the Haar measure on Stiefel manifolds, which capture the heuristic weak dependence of entries of blocks of random orthogonal matrices under the Haar measure.



 §.§ Bounding the cross-term T1



    
    For all K > 0,
    
    [|^(1)| ≼ O_δ, K(log N/N)  I_r(r + 1) / 2 + 2/r__^⊤] ≥ 1 - O_δ, K(N^-K).



    Applying the matrix arithmetic-geometric mean inequality,
    
    |^(1)|
             ≼2/r(∑_i = 1^N _i_i^⊤ - N/r I_r)(∑_i = 1^N _i_i^⊤ - N/r I_r)^⊤
        + 2/r__^⊤
       ≼2/r∑_i = 1^N _i_i^⊤ - N/r I_r_F^2  I_r(r + 1) / 2 + 2/r__^⊤.

    Rewriting the norm appearing in the first term,
    
    ∑_i = 1^N _i_i^⊤ - N/r I_r_F^2
             = ^⊤ - N/r I_r_F^2 
       = ^-1^⊤ - δ^-1 I_r_F^2 
       = ^-1 - δ^-1 I_N_F^2,

    since ^⊤ =  I_r.
    By Proposition <ref>,
    
    [(δ^-1 - O_δ, K(√(log N/N))) I_N≼^-1≼(δ^-1 + O_δ, K(√(log N/N))) I_N] 
       ≥ 1 - O_δ, K(N^-K).

    Thus with at least the same probability we have
    
    ^-1 - δ^-1 I_N_F^2 ≤ O_δ, K(log N),

and the result follows.



    
    Let us contrast the result of this section with the same analysis for i.i.d. vectors.
    The marginal law of each _i is uniform over ^r - 1, so consider taking _i ∼𝖴𝗇𝗂𝖿(^r - 1) independent.
    Then, we compute
    
    ∑_i = 1^N _i_i^⊤ - N/r I_r_F^2
             = N _1_2^4 + N(N - 1)_1, _2 ^2 - N^2/r + N 
       = Ω(N).

    Thus the corresponding cross-term would have largest eigenvalue of order δ^-1, which in particular would not decay with N.

    Consequently, our previous intuition that we should obtain an approximate projector of rank N from ^(2) = ∑_i = 1^N(_i_i^⊤ - 1/r I_r)(_i_i^⊤ - 1/r I_r)^⊤ cannot be correct, since the putative basis vectors (_i_i^⊤ - 1/r I_r) almost sum to zero.
    In the following section, we will show that this is in fact the only linear near-dependence of these vectors, and ^(2) is still an approximate orthogonal projector, only of rank N - 1.




 §.§ Bounding the projection term T2: unnormalized case




Our strategy for bounding ^(2) will proceed in two steps: first, we will bound the same matrix but constructed from the approximately normalized vectors δ^-1/2_1, …, δ^-1/2_N in place of the strictly normalized vectors _1, …, _N, and then we will show that this replacement does not significantly affect the spectrum.
In this section we perform the first, more difficult of these tasks.
We will show the following result.


    
    Let ^ have (δ^-1_i_i^⊤ - 1/r I_r) as its columns.
    Let __N^⊤ I_N - 1/N_N_N^⊤, the orthogonal projector to the subspace orthgonal to _N.
    Then,
    
    [ ^^⊤^ - __N^⊤_≤ O_δ(log N/N^1/4) ] ≥ 1 -  exp(-Ω_δ(N^1/2)).


The argument will use the technique of union bounding over a net.
Our main technical tool will be the following Lipschitz concentration inequality for the Haar measure of the Stiefel manifolds.

Recall that the Stiefel manifolds are defined as:

    𝖲𝗍𝗂𝖾𝖿(N, r) {∈^r × N: ^⊤ =  I_r }.

The Haar measure (𝖲𝗍𝗂𝖾𝖿(N, r)) may be viewed as the measure obtained by restricting ((N)) to the upper r × N matrix block.

These measures enjoy the following concentration inequality when r < N, obtained by standard arguments from logarithmic Sobolev or isoperimetric inequalities for the special orthogonal group 𝒮𝒪(N), of which 𝖲𝗍𝗂𝖾𝖿(N, r) is a quotient when r < N (see, e.g., the discussion following Theorem 2.4 of <cit.>).

    
    Suppose 1 ≤ r < N, and F: 𝖲𝗍𝗂𝖾𝖿(N, r) → has Lipschitz constant at most L when 𝖲𝗍𝗂𝖾𝖿(N, r) is endowed with the metric of the Frobenius matrix norm.
    Then, for an absolute constant C > 0,
    
    _∼(𝖲𝗍𝗂𝖾𝖿(N, r))[|F() -  F()| ≥ t] ≤ 2exp(-CNt^2/L^2).


Note that since we have r = δ N with δ < 1, we will always satisfy the hypothesis r < N; we will use this implicitly without further comment for the remainder of the proof.


    Note that ^_N = (N/r^⊤ - N/r I_r) =  0; thus as suggested already in Remark <ref>, it is impossible for ^ to act on ^N as an approximate isometric embedding, as we might naively expect from its weakly dependent columns.
    Our argument is more natural to carry out if we remove this caveat; therefore, let us define ^_0 to have columns (N/r_i_i^⊤ - 1 - √(δ)/r I_r).
    One may check that ^_0_N_2 = _N_2 = √(N), and that
    
    _0^^⊤_0^ = ^^⊤^ + 1/N_N_N^⊤.

    In particular, _0^^⊤_0^ -  I_N = ^^⊤^ - __N^⊥, so it suffices to show the operator norm bound of (<ref>) for _0^^⊤_0^ -  I_N.

    For ∈^N, let us denote _() for the course of this proof.
    Then,
    
    ^_0    = (δ^-1∑_i = 1^N x_i _i_i^⊤ - 1 - √(δ)/r_N,  I_r) 
       = δ^-1(_^⊤ - 1 - √(δ)/N_N,  I_r).

    For , ∈^N, define
    
    F_, ()    _0^, _0^.

    Then, recalling that ^⊤ is the orthogonal projector to the row space of ,
    
    F_, () 
       = δ^-2_^⊤ - 1 - √(δ)/N_N,  I_r, _^⊤ - 1 - √(δ)/N_N,  I_r 
       = δ^-2[(__) 
        - 1 - √(δ)/N(_N, (_) + _N, (_)) 
        + δ(1 - √(δ))^2/N_N, _N, ].

    Let us denote balls in Euclidean space by
    
    B( x, r) {∈^N :  - _2 ≤ r}.

    Our first goal will be to obtain concentration bounds on F_, () when ∼(𝖲𝗍𝗂𝖾𝖿(N, r)) for each fixed pair (, ) ∈ B( 0, 1)^2, by applying the Lipschitz concentration inequality.

    
        
        Let , ∈ B( 0, 1). Then,
        
    𝖫𝗂𝗉(F_, ) ≤ 4δ^-2[min{_∞, _∞} + 1/√(N)].

    
    
        For _1, _2 ∈𝖲𝗍𝗂𝖾𝖿(N, r), letting _i = _i^⊤_i, we have using (<ref>) and the triangle inequality
        
    δ^2|F_, (_1) - F_, (_2)| 
        = |(__1__1) - (__2__2)
        + (1 - √(δ))|_N, |/N| (_1_y) - (_2_y)| 
        + (1 - √(δ))|_N, |/N| (_1_) - (_2_)|, 
    then using that |_N, | ≤_1 ≤√(N) and likewise for ,   ≤|(__1_(_1 - _2))| + |(_(_1 - _2)__2)| 
       + 1/√(N)(|((_1 - _2)_)| + |((_1 - _2)_)|) 
       ≤ (__1_F + __2_F)_(_1 - _2)_F 
       + 2/√(N)_1 - _2_F.

        Since _i is an orthogonal projector for i ∈{1, 2},
        
    __i_F = _^2, _i ^1/2≤ ([_^2])^1/2≤ 1.

        We bound the other term by
        
    _(_1 - _2)_F = _^2, (_1 - _2)^2 ^1/2≤_∞_1 - _2_F.

      Combining these observations and a symmetric argument with  and  in opposite roles gives
      
    |F_, (_1) - F_, (_2)| ≤ 2δ^-2[min{_∞, _∞} + 1/√(N)]_1 - _2_F.

      Lastly, we bound
      
    _1 - _2_F
               = _1^⊤_1 - _2^⊤_2_F 
       = (_1 - _2)^⊤_1 + _2^⊤ (_1 - _2)_F 
       ≤(_1 - _2)^⊤_1_F + _2^⊤ (_1 - _2)_F 
       = ([(_1 - _2)^⊤_1_1^⊤(_1 - _2)])^1/2
        + ([(_1 - _2)^⊤_2_2^⊤(_1 - _2)])^1/2
       = 2_1 - _2_F,

      where we have used that _1_1^⊤ = _2_2^⊤ =  I_r, and the result follows.
  

    Therefore, and what is crucial to our argument, while for the worst-case ∈ B( 0, 1), namely = _i a standard basis vector, F_, will have Lipschitz constant O(1), for typical ∈ B( 0, 1), F_, will rather have Lipschitz constant O(N^-1/2).
    Moreover, the Lipschitz constant of F_, is comparable to the smaller of the Lipschitz constants of F_, and F_,.

    
        
        For , ∈ B( 0, 1), _∼(𝖲𝗍𝗂𝖾𝖿(N, r)) F_, () = ,  + O_δ(N^-1).
    
    
    We have
    
    δ^2  F_, ()
             = (_^⊤_^⊤) 
        - 1 - √(δ)/N_N, (^⊤_y) 
       - 1 - √(δ)/N_N, (^⊤_x) 
        + δ(1 - √(δ))^2/N_N, _N, ,
            and by either the moment formulae of Proposition <ref> or an argument from orthogonal invariance of Haar measure, we have ^⊤ = δ I_N, whereby   = (_^⊤_^⊤) - δ(1 - δ)/N_N, _N, .

    View ∼(𝖲𝗍𝗂𝖾𝖿(N, r)) as the top r × N block of ∼((N)).
    Then, expanding the first term with the moment formulae of Proposition <ref>,
    
    (_^⊤_^⊤) 
       =  ∑_i, j = 1^N x_iy_j(∑_a, b = 1^r[Q_aiQ_biQ_ajQ_bj]) 
       = ∑_i = 1^N x_iy_i(3r/N(N + 2) + r(r - 1)/N(N + 2)) 
        + ∑_1 ≤ i < j ≤ Nx_iy_j(r/N(N + 2) - r(r - 1)/(N - 1)N(N + 2)) 
       = δ/N + 2(r + 1 + r - 1/N - 1)∑_i = 1^N x_iy_i 
        + δ/N + 2(1 - r - 1/N - 1)(∑_i = 1^N x_i)(∑_i = 1^N y_i) 
       = (δ^2 + O_δ(N^-1)),  + (1 + O_δ(N^-1))δ(1 - δ)/N_N, _N, ,

    and since |, | ≤_2_2 ≤ 1 and |_N, |· |_N, | ≤ N, the result follows.


    Combining Claim <ref>, Claim <ref>, and the concentration result Proposition <ref>, we find the following corollary on pointwise concentration of F_, ().

    
        
        There exist constants C_1, C_2 > 0 depending only on δ such that, for any , ∈ B( 0, 1),
        
    _∼(𝖲𝗍𝗂𝖾𝖿(N, r))[ |_0^, _0^ - , | ≥C_1/N + t] 
       ≤ 2exp(-C_2 N t^2/(min{_∞, _∞} + N^-1/2)^2).

    

        This concludes the first part of the argument.

    The remaining part of the argument is to apply a union bound of the probabilities controlled in Claim <ref> over suitable nets of B( 0, 1).
    We divide our task into a bound over sparse vectors and vectors with bounded largest entry, very similar to the technique in <cit.> and especially <cit.>.
    Introduce a parameter ρ∈ (0, 1) to be chosen later.
    Define
    
    B_s    {∈ B( 0, 1): _0 ≤ρ N }, 
    
          B_b    {∈ B( 0, 1): _∞≤1/√(ρ N)}.

    For any ∈ B( 0, 1), we define = () and = () by thresholding the entries of , setting y_i  x_i {|x_i| > 1/√(ρ N)} and z_i  x_i {|x_i| ≤1/√(ρ N)}.
    Then, =  +, ∈ B_s, and ∈ B_b.

    Introduce another parameter γ∈ (0, 1) to be chosen later.
    Let N_s ⊂ B_s and N_b ⊂ B_b be γ-nets.
    By a standard bound (see, e.g., Lemma 9.5 of <cit.>), we may choose |N_b| ≤exp(2N / γ), and by the same bound applied to each choice of ρ N support coordinates for an element of B_s, we may choose
    
    |N_s| ≤N⌊ρ N ⌋exp(2ρ N/γ) ≤exp(2ρ N/γ + ρ N + log(1/ρ)ρ N).

    To lighten the notation, let us set _0^^⊤_0^ -  I_N.
    The following is an adaptation to our setting of a standard technique for estimating a matrix norm over a net: we first bound
    
    _   = max_∈ B( 0, 1)|^⊤| 
       ≤max_∈ B_s 
    ∈ B_b |( + )^⊤ ( + )| 
       ≤max_∈ B_s |^⊤| + max_∈ B_b |^⊤| + 2max_∈ B_s 
    ∈ B_b|^⊤ | 
       ≤max_∈ N_s |^⊤| + max_∈ N_b |^⊤| + 2max_∈ N_s 
    ∈ N_b |^⊤ | + 12γ_.

    Rearranging this, we obtain
    
    _   ≤1/1 - 12γ[max_∈ N_s |^⊤| + max_∈ N_b |^⊤| + 2max_∈ N_s 
    ∈ N_b |^⊤ |].

    Using Claim <ref> and a union bound, we have that
    
    [_≥4/1 - 12γ(C_1/N + t)] 
       ≤ 2(|N_b| + |N_s| · |N_b|)exp(-C_2 ρ/(1 + √(ρ))^2 N^2 t^2) 
        + 2|N_s|exp(-C_2/2Nt^2) 
       ≤ 3exp(N[2/γ(1 + ρ) + ρ + log(1/ρ)ρ -C_2 ρ/(1 + √(ρ))^2 N t^2]) 
        + 2exp(N[2ρ/γ + ρ + log(1/ρ)ρ-C_2/2t^2]).

    Taking ρ = N^-1/2, t = C_3 N^-1/4log N for a large constant C_3, and γ < 1/12 a small constant, we obtain the result.




 §.§ Bounding the projection term T2: normalization




In this section, we show that the passing from the approximately normalized vectors δ^-1/2_i discussed in the previous section to the exactly normalized vectors _i = _i / _i_2 does not affect the construction of ^(2) very much, as measured by operator norm.


    
    Let ^∈^r(r + 1) / 2 × N have (δ^-1_i_i^⊤ - 1/r I_r) as columns, and let ^∈^r(r + 1) / 2 × N have (_i_i^⊤ - 1/r I_r) as columns.
    Then, for all K > 0,
    
    [ ^ - ^_≤ O_δ, K(log N/N)] ≥ 1 - O_δ, K(N^-K).



    Recall that ∈^N × N is diagonal with D_ii = _i_2^2.
    Then, we may write
    
    ^   = δ^^-1 + δ/r__N^⊤^-1 - 1/r__N^⊤
       = ^ + ^(δ^-1 -  I_N)+ 1/r__N^⊤(δ^-1 -  I_N).

    Therefore,
    
    ^ - ^_   ≤δ^-1 -  I_N_(^ + δ^-1/2) 
       = (max_i ∈ [N]|δ/D_ii - 1|)(^ + δ^-1/2).

    By Lemma <ref> from the previous section, the second term is O_δ(1) with super-polynomially high probability.
    The result then follows by Proposition <ref>.

Next, we translate this result to the Gram matrix ^^⊤^.

    
    In the same setting as Lemma <ref>, for all K > 0,
    
    [ ^^⊤^ - ^^⊤^_≤ O_δ, K(log N/N)] 
       ≥ 1 -  O_δ, K(N^-K).



    We may bound
    
    ^^⊤^ - ^^⊤^_
        = ^^⊤(^ - ^) +  (^ - ^)^⊤^_
       ≤(^_ + ^_)^ - ^_
       ≤(2^_ + ^ - ^_)^ - ^_.

    Then, combining Lemma <ref> and Lemma <ref> gives the result.




 §.§ Final main term bound: proof of Lemma <ref>


We are now ready to complete the proof of Lemma <ref>.
First, we combine Lemma <ref> and Corollary <ref>.
Recall that these showed the following bounds, with high probability:

    ^^⊤^_   ≤ 1 + O_δ(log N/N^1/4), Lemma <ref>
    ^^⊤^ - ^^⊤^_   ≤ O_δ(log N/N). Corollary <ref>

Combining these, we obtain the following bound on ^(2) = ^^^⊤.

    
    For all δ∈ (0, 1),
    
    lim_N →∞[^(2)_≤ 1 + O_δ(log N/N^1/4)] = 1.



Next, we complete the proof of Lemma <ref>.
Recall that

    ^(1a) = (α - 2N/r^2)__^⊤ + 2 I_r(r + 1) / 2 + ^(1) - 2^(2),

and we have gathered the following bounds, holding with high probability:

    |^(1)|    ≼ O_δ(log N/N) I_r(r + 1) / 2 + 2/r__^⊤Lemma <ref>
    
      0 ≼^(2)   ≼(1 + O_δ(log N/N^1/4)) I_r(r + 1) / 2Corollary <ref>

We can therefore control the minimum eigenvalue of ^(1a) by, with high probability,

    ^(1a)≽(α - 2N/r^2 - 2/r)__^⊤ - O_δ(log N/N^1/4) I_r(r + 1) / 2.

The first term is positive semidefinite for sufficiently large N since N / r^2 → 0, and thus we find

    lim_N →∞[λ_min(^(1a)) ≥ -O_δ(log N/N^1/4)] = 1.


Finally, we must convert this to a bound on the smallest eigenvalue of ^(1a).
By Proposition <ref>, letting = ^⊤, we have

    λ_min(^(1a)) ≥min{0, λ_min(^(1a))/2min_i ∈ [N] P_ii^2}.

By Proposition <ref>, with high probability P_ii≥δ^-1 - O_δ(√(log N/N)) for all i ∈ [N].
Substituting this above, we thus find the result of Lemma <ref>,

    lim_N →∞[λ_min(^(1a)) ≥ -O_δ(log N/N^1/4)] = 1.




§ PROOF OF POSITIVE SEMIDEFINITENESS: CORRECTION TERM





    Recall that Δ is non-zero only on pairs of index sets {i,j} and {i,k} that share an index.
    The non-zero entries are given by
    
    Δ_{i,j}{i,k} = ∑_m = 1^N M_im^2M_jmM_km - M_ijM_ik.


    Let us compute the quadratic form of Δ with ∈^N(N - 1) / 2, which we view as having entries a_{i,j} = A_ij for some ∈^r × r_ with ( A) =  0 (i.e. = ()).
    We then have, expanding with a correction for double-counting the diagonal terms,
    
    ^⊤Δ   = ∑_i = 1^N ∑_j = 1^N∑_k = 1^NA_ij{(∑_m = 1^N M_im^2M_jmM_km) - M_ijM_ik}A_ik
        - ∑_1 ≤ i < j ≤ N A_ij^2{(∑_m = 1^NM_im^2M_jm^2) - M_ij^2}
       = ∑_i = 1^N {(∑_m = 1^NM_im^2()_im^2) - ()_ii^2}
        - ∑_1 ≤ i < j ≤ NA_ij^2((^∘ 2)^2 - ^∘ 2)_ij) 
       = ^∘ 2, ()^∘ 2 - (()^∘ 2) - ^∘ 2, (^∘ 2)^2 - ^∘ 2
       = ^∘ 2 -  I_N, ()^∘ 2 - ^∘ 2, (^∘ 2)^2 - ^∘ 2.
            Following the notation of Sections <ref> and <ref>, we let ^^⊤^ be the Gram matrix of (_i_i^⊤ - 1/r I_r), whereby ^∘ 2 =  + 1/r_N_N^⊤, allowing us to continue by expanding the second term   = ^∘ 2 -  I_N, ()^∘ 2 - 1/r^2(_N^⊤_N^⊤)_F^2 + 1/r_F^2 
        - ^∘ 2, ^2 -  +  1/r_N_N^⊤ + 1/r_N_N^⊤.


    We will now use the following inequality that allows us to bound inner products with the Schur square of a matrix by its Frobenius norm:
    
    |^∘ 2, | ≤∑_i, j|Y_ij|X_ij^2 ≤_ℓ^∞_F^2 ≤__F^2.

    (We denote by _ℓ^∞ the vectorized supremum norm.)
    This will result in one term involving _F^2, which we bound by
    
    _F^2 = (^⊤^2) ≤_^2(^⊤) = _^2_F^2.

    Combining these inequalities and noting that _2^2 = 1/2_F^2, we find (for ≠ 0) that
    
    |^⊤Δ|/_2^2   ≤ 2(^∘ 2 -  I_N_ℓ^∞_^2 + 1/r + _N^⊤_N/r^2
        + ^2 - _ + 2√(N)/r_N_2).

    Since () =, we have by Corollary <ref> that, with high probability,
    
    ^∘ 2 -  I_N_ℓ^∞ = max_i, j ∈ [N] 
     i ≠ j |M_ij|^2 ≤ O_δ(log N/N),

    and by Corollary <ref>, _ = O_δ(1) with high probability.

    To control the terms involving , recall that from Lemmata <ref> and <ref> it follows that with high probability
    
    - __N^⊥_≤ O_δ(log N/N^1/4).

    Thus we have, with high probability,
    
    |_N^⊤_N|/r^2   ≤N/r^2 - __N^⊥_ = O_δ(log N/N^5/4), 
    ^2 - _   ≤ 3 - __N^⊥_ +  - __N^⊥_^2 = O_δ(log ^2N/N^1/4), 
    2√(N)/r_N_2    ≤2N/r - __N^⊥_ = O_δ(log N/N^1/4).

    Combining these results, Lemma <ref> follows.



    We outline a simpler argument for Lemma <ref> which suggests a sharper estimate, though it seems more difficult to formalize due to the dependency structure of .
    Since Δ is sparse (with non-zero entries only when the row and column index sets {i,j} and {k,ℓ} share an element), our strategy will be to apply the Gershgorin circle theorem.
    Thus we must bound the diagonal and off-diagonal entries of Δ.

    The summation defining the diagonal entries contains only positive summands, so we have
    
    Δ_{i,j}{i,j} = ∑_m = 1 
     m ≠ i^N M_im^2 M_jm^2 = M_ij^2 + ∑_m = 1 
     m ≠ i, j^N M_im^2 M_jm^2 = O(N^-1),

    using Proposition <ref> to control each term of the sum.
    (We omit bounds expressing “with high probability” statements and indulge in the logarithm-concealing O notation in this informal discussion.)

    The off-diagonal entries of Δ are more difficult to control.
    They are
    
    Δ_{i,j}{i,k} = ∑_m = 1 
     m ≠ i^N M_im^2 M_jmM_km = ∑_m = 1 
     m ≠ i^N M_im^2 M_jmM_km.

    Here, we must capture the cancellations due to random signs: a naive application of the triangle inequality would give |Δ_{i,j}{i,k}| = O(N^-1), which would be insufficient for the Gershgorin circle theorem argument since there are Ω(N) non-zero entries in each row of Δ.
    On the other hand, a scaling like that in the central limit theorem with independent signs would give |Δ_{i,j}{i,k}| = O(N^-3/2), which would suffice, and would give Δ_ = O(N^-1/2), stronger by a factor of N^1/4 than the result of Lemma <ref> (up to logarithmic factors).




§ ACKNOWLEDGEMENTS

tocsectionAcknowledgements

We thank Jess Banks, Ankur Moitra, Andrea Montanari, Cristopher Moore, Tselil Schramm, and Ramon van Handel for useful discussions.
We also thank the authors of <cit.> for generously providing an early version of their manuscript.



tocsectionReferences
alpha


