Tensor principal component analysis via sum-of-squares proofs

1 Introduction

• Tensor PCA seeks a direction maximizing a higher-order moment, but unlike ordinary PCA its general optimization problem is NP-hard, motivating average-case algorithms for structured statistical instances.The asymmetric model is T = τ·v^⊗3 + A, with unit v, τ ≥ 0, and iid standard Gaussian noise; the symmetric variant imposes permutation symmetry on A.Source: §1 · pp. 3–4

1.1 Results

• Degree-4 SoS recovers correlation 1 − O(ε) when τ ≥ n^3/4(log n)^1/4/ε, certifying that vectors far from the output have substantially smaller MLE objective.The guarantee holds for both asymmetric and symmetric models with probability 1 − O(n^-10), and applies when rounding any relaxation solution with objective at least (1 − o(1))τ.Source: §1.1 · p. 4
• A matching degree-4 limitation occurs at τ ≤ O(n^3/4/log(n)^1/4), where a planted-vector-independent relaxation solution prevents reliable recovery from that solution.The lower bound holds with probability 1 − O(n^-10), showing that substantially improving the SoS guarantee requires methods beyond this relaxation level.Source: §1.1 · p. 5
• A shifted matrix power-iteration algorithm achieves recovery in nearly-linear time ˜O(n^3) at τ ≥ n^3/4/ε, while a slower ˜O(n^4) method retains certification.The nearly-linear algorithm lacks certification and can fail under small adversarial perturbations; the certifying algorithm requires the logarithmic signal factor.Source: §1.1 · p. 5
• The results extend to higher-order tensors: odd-order models admit semidefinite-programming recovery and certification, even-order models recover with squared correlation, and odd-order unfolding runs in nearly-linear time.For odd k, the semidefinite-programming algorithms require τ ≥ n^k/4 log(n)^1/4/ε, while the unfolding algorithm requires τ ≥ n^k/4/ε and also works with symmetric noise; the symmetric higher-order nearly-linear implementation remains conjectural for the certification-related result.Source: §1.1 · pp. 5–6

1.2 Techniques

• The technical core nearly characterizes degree-4 certificates for random cubic polynomials, yielding certificates at ˜O(n^3/4) and showing no significantly better degree-four certificate exists.These certificates support three algorithms: a polynomial-time semidefinite program, a ˜O(n^4) partial-certificate method, and tensor unfolding interpreted as rounding a non-optimal SoS solution; the analysis confirms Montanari and Richard’s unfolding conjecture up to logarithmic factors and an extra random rotation for sparse symmetric signals.Source: §1.2 · pp. 6–7

1.3 Related Work

• Relative to prior work, the paper studies dense, fully observed noisy tensors under distributional assumptions, while related SoS tensor-prediction work studies partial observations and worst-case noise.The work is inspired by Montanari and Richard, whose tensor-unfolding analyses found strong noise robustness; it also tightens their odd-order analysis and relates to concurrent results by Zheng and Tomioka [ZT15, Theorem 1].Source: §1.3 · p. 9
• MRZ14 prove that every eigenvalue of perturbed Gaussian matrices or unfolded tensors becomes indistinguishable from pure noise below a precise detection threshold.Their lower bound uses fine-grained information from the full spectrum of a single matrix associated with the detection problem.Source: §1.3 · p. 9
• In contrast, this paper’s degree-4 SoS lower bound examines only the top eigenvalue but applies to all matrices generated by the degree-4 sum-of-squares proof system.The two lower bounds are therefore incomparable: one studies detailed spectral information for one matrix, while the other studies coarser information across many matrices.Source: §1.3 · p. 9

2.1 Notation

• The paper uses entrywise inner products, vector ℓ2 norms, matrix operator norms, squarest-possible tensor unfoldings, and T(v) = ⟨v^⊗k, T⟩ for tensor polynomials.All objects are real; odd- and even-order unfoldings use dimensions n^⌊k/2⌋ × n^⌈k/2⌉ and n^(k/2) × n^(k/2), respectively.Source: §2.1 · p. 10

2.2 Polynomials and Matrices

• Even-degree polynomials can be represented by matrices, and a positive-semidefinite representation expresses the polynomial as a sum of squares.The representation has the form p(x) = ⟨x^⊗d/2, Mx^⊗d/2⟩.Source: §2.2 · p. 10

2.3 The Sum of Squares (SoS) Algorithm

• A degree-d pseudo-expectation is a normalized linear functional on polynomials that models expectations under a pseudo-distribution satisfying polynomial constraints.Such constrained pseudo-distributions can be found, up to negligible numerical-accuracy issues, via semidefinite programming in time and size n^O(d).Source: §2.3 · pp. 10–11

• For even-degree polynomials, square matrix representations yield spectral certificates, and Gaussian order-d tensors satisfy max_{||v||=1} f(v) <= ~O(n^d/4) with high probability.The certificate follows from bounding the matrix representation's maximal eigenvalue.Source: §3 · p. 11
• For degree-3 random polynomials, rectangular spectral representations certify only max_{||v||=1} f(v) <= ~O(n), failing to exploit the lower degree.The top singular value is governed by the longer matrix dimension, producing the same scale as the degree-4 case.Source: §3 · p. 11
• Bounding a multilinear degree-3 polynomial by the degree-4 polynomial ||∇f(x)||^2 produces a bound tight at spherical local maxima and yields the best possible degree-4 SoS-certifiable bound.The construction uses the identity f(x) = 1/3 ||x|| ||∇f(x)|| and associates a suitable degree-4 polynomial with the gradient norm.Source: §3 · pp. 11–12
• If a homogeneous degree-3 polynomial is λ-bounded, then max_{||v||=1} f(v) <= λ, and degree-4 SoS certifies this inequality for every degree-4 pseudo-distribution.λ-boundedness is defined through matrix representations that establish the required sum-of-squares domination.Source: §3 · p. 12
• For a Gaussian order-3 tensor, A(x) is λ-bounded with λ = O(n^3/4 log(n)^1/4) with high probability, so degree-4 SoS certifies max_{||v||=1} A(v) <= O(n^3/4(log n)^1/4).This bound is the backbone of the SoS algorithm for tensor PCA in the spiked tensor model.Source: §3 · pp. 12–13

4 Polynomial-Time Recovery via Sum of Squares

• Algorithm 4.1 maximizes Ẽ T(x) over degree-4 pseudodistributions satisfying Ẽ∥x∥²=1, then outputs the normalized pseudo-expectation Ẽx.The implementation described here solves a large semidefinite program, so it is polynomial-time but not yet nearly linear-time.Source: §4 · p. 13
• For τ ≿ n3/4 log(n)1/4/ε, Algorithm 4.1 outputs v with ⟨v, v0⟩ ≥ 1−O(ε), while Algorithm 4.2 outputs certify with high probability and guarantees T(x) ≤ τ · ⟨v, x⟩3 + O(n3/4 log(n)1/4).Source: §4 · pp. 13–14
• Recovery follows from a degree-4 SoS-certifiable noise bound: controlling ẼA(x) makes the signal term dominate the relaxation and forces the rounded vector close to v0.For Gaussian noise, the required bound holds with high probability, including permutation-symmetrized noise via a union bound.Source: §4 · pp. 14–15

4.1 Semi-Random Tensor PCA

• In the semi-random model, Algorithm 4.1 still achieves ⟨v,v0⟩ ≥ 1−O(ε) with high probability when τ ≥ n^(3/4) log(n)^(1/4)/ε.The model applies an adversarial matrix Q close to identity to the tensor’s flattening; the proof bounds the induced perturbation using operator norms and the SoS noise estimate.Source: §4.1 · p. 15

5 Linear Time Recovery via Further Relaxation

• A single singular-vector computation on a relatively small matrix replaces solving the large SoS semidefinite program to optimality, completing the desired running-time guarantees.The matrix is formed from the tensor slices, and its associated singular vector can be decoded into the planted signal.Source: §5 · p. 16

5.1.1 The SoS Algorithm: Matrix View

• Matrix representations make pseudo-distributions and polynomials dual under the trace inner product, while relaxing symmetry constraints enables a more linear-algebraic SoS formulation.Sphere constraints become kernel conditions on the pseudo-distribution matrix, and asymmetric matrix representations are excluded at optimality by unboundedness.Source: §5.1.1 · pp. 16–17

5.1.2 Relaxing to the Degree-4 Dual

• For Gaussian quadratic forms, spectral SoS matches the full-strength bound, and for p = P_i A_i ⊗ A_i it is at most O(n^3/2 log(n)^1/2) with high probability.The same matrix P_i A_i ⊗ A_i remains a feasible dual solution after projecting to homogeneous degree four.Source: §5.1.2 · p. 18

5.2 Recovery via the P_i T_i ⊗ T_i Spectral SoS Solution

• When τ ≥ n^3/4 log(n)^1/4/ε, Algorithm 5.1 recovers v with ⟨v,v_0⟩^2 ≥ 1 − O(ε), while certification succeeds with high probability for Gaussian noise and both algorithms run in O(n^4 log(1/ε)).Certification guarantees T(x) ≤ τ·⟨v,x⟩^3 + O(n^3/4 log(n)^1/4) regardless of the noise distribution whenever it outputs certify.Source: §5.2 · p. 19

5.3 Nearly-Linear-Time Recovery via Tensor Unfolding and Spectral SoS

• At τ ≥ n^3/4/ε, tensor unfolding recovers v with ⟨v,v_0⟩^2 ≥ 1 − O(ε) in time ˜O(n^3), proving the Montanari–Richard conjecture at this threshold.For odd-order tensors, recovery relies on a second-order spectral effect despite the absence of a spectral gap; its spectral SoS certificate is weaker, giving O(n) rather than O(n^3/4 log(n)^1/4).Source: §5.3 · pp. 21–22
• Algorithm 5.7 is implemented in ˜O(n^3), linear in the input size, by shifting the unfolding matrix to improve its eigenvalue gap before power iteration.Matrix-vector multiplication remains O(n^3), while shifting by n^2 · Id yields an eigenvalue gap Ω(1/ε).Source: §5.3 · p. 22

5.4 Fast Recovery in the Semi-Random Model

• Under the semi-random model, Algorithm 5.7 fails because it relies on second-order spectral behavior, whereas certifying algorithms use only first-order unfolding spectra.For τ = Ω(n^7/8), an adversarial Q with ∥Q − Id∥ ≤ O(n^−1/4) can make (TQ)^T TQ = n^2 · Id, preventing recovery.Source: §5.4 · p. 23
• The semi-random certifying algorithms remain successful: when ε ≥ n^−1/4 and τ ≥ n^3/4 log(n)^1/4/ε, Algorithm 5.1 recovers v with ⟨v, v0⟩^2 ≥ 1 − O(ε) and Algorithm 5.2 certifies.The non-probabilistic certification claims are independent of the input model.Source: §5.4 · p. 23

5.5 Fast Recovery with Symmetric Noise

• For symmetric Gaussian noise, Algorithm 5.14 recovers v with ⟨v, v0⟩ ≥ 1 − O(ε) when τ ≥ n^3/4/ε and ε ≥ log(n)/√n, in almost-linear time.Each matrix power iteration converges within ˜O(−log(ε)) steps, giving total runtime ˜O(n^3 log(1/ε)).Source: §5.5 · p. 25

5.6 Numerical Simulations

• For n = 200, simulations found pronounced runtime differences: naïve Algorithm 5.7 was markedly slower than its linear implementation, while Algorithm 5.1’s n^2 × n^2 matrix caused prohibitive memory requirements beyond n = 100.The experiments measured matrix-vector multiplies and processor time across the three implementations.Source: Figure 1 · p. 26, §5.6 · p. 27

6 Lower Bounds

• Degree-4 SoS lower bounds match the Tensor PCA analysis up to a logarithmic factor, and the constructions also apply to symmetric noise.Maps depending only on the random tensor produce pseudo-distributions from which reliable recovery of the planted vector is impossible.Source: §6 · p. 27
• At τ = Ω(n), a degree-4 pseudo-distribution achieves the degree-4 objective within constant factors of the optimum over unit-sphere pseudo-distributions.This holds with high probability for unit Gaussian 4-tensor noise and every planted unit vector.Source: §6 · p. 27
• At τ = Ω(n^3/4/(log n)^1/4), a degree-4 pseudo-distribution achieves the degree-3 objective within logarithmic factors of the unit-sphere optimum.The construction uses degree-3 moments proportional to the noise tensor and degree-4 moments derived from A A^T and its permutations.Source: §6 · p. 27, §6.0.1 · p. 27

6.0.1 Discussion and Outline of Proof

• The lower-bound construction first correlates pseudo-moments with permutations of A A^T, then projects onto the sphere and repairs positivity by mixing with the uniform sphere distribution.The intermediate linear functional need not be a valid pseudo-distribution, so the repair controls its positivity failure while retaining a large noise objective.Source: §6.0.1 · p. 28

6.1 Polynomials, Vectors, Matrices, and Symmetries, Redux

• Linear functionals correspond to uniquely maximally symmetric matrices, with positive semidefiniteness characterizing nonnegative quadratic pseudo-expectations and normalization yielding pseudo-distributions.Tensor symmetrization and monomial-indexed subspaces connect polynomial representations, matrix forms, and permutation actions.Source: §6.1 · p. 28, §6.1.1 · p. 29, §6.1.3 · p. 30

6.2 Formal Statement of the Lower Bound

• The formal lower bounds require noise correlation, spectral lower bounds for permutations, and moment controls preventing excessive fourth-, first-, and second-degree moments.For degree 3, the spectral conditions additionally involve flattenings of the associated fourth-order tensor representing the quadratic-form polynomial.Source: §6.2 · pp. 30–31

6.2.1 Proof of Theorem 6.2

• For Gaussian noise, regularity conditions hold with high probability at λ = O(n^3/4 log(n)^1/4), making the constructed pseudo-distribution nearly optimal against degree-4 SoS certificates.If regularity fails, the proof uses the uniform sphere distribution instead; the noise operator norm and sphere expectation supply the needed comparison.Source: §6.2.1 · pp. 31–32

6.3 In-depth Preliminaries for Pseudo-Expectation Symmetries

• The symmetry preliminaries decompose S4 through D8 and a 3-cycle subgroup, enabling explicit maximally symmetric matrices and analysis of distinct A A^T permutations.For tensor flattenings, the relevant permutations correspond to switching index pairs via transposition operators.Source: §6.3 · pp. 32–33
• Symmetrized identity matrices yield a canonical sphere moment functional, while σ · Id is rank-one and positive semidefinite.The scaled sum [1/(n2+2n)](Id+σ·Id+σ2·Id) equals expectation under the uniform distribution on the unit sphere.Source: §6.3 · pp. 33–34

6.4 Construction of Initial Pseudo-Distributions

• The initial pseudo-distribution uses symmetrization and spectral techniques to correlate third moments with A(x), but initially fails the unit-sphere constraint.The construction is designed to produce well-defined linear functionals and positive-semidefinite moment matrices before later repair.Source: §6.4 · p. 34

6.4.1 Extending Pseudo-Distributions to Degree Four

• The symmetric Schur complement extends a degree-3 functional to a valid degree-4 pseudo-expectation while preserving maximal symmetry and positive semidefiniteness.For the uniform sphere moments, the minimizing parameter is t = n2/(n2 + 2n), recovering Eµ.Source: §6.4.1 · pp. 34–35

6.4.2 Symmetries at Degree Three

• Decomposing the degree-3 moment matrix into symmetric Schur complements produces a positive-semidefinite, maximally symmetric matrix and therefore a valid pseudo-expectation.This avoids directly controlling the spectrum of the Schur complement associated with coefficients correlated with A(x).Source: §6.4.2 · p. 35, Then the matrix · p. 36

6.5 Getting to the Unit Sphere

• A near-spherical degree-4 pseudo-distribution can be transformed into a functional on the unit sphere by enforcing the constraint polynomial ∥x∥2 − 1 in its kernel.The resulting functional is a sphere pseudo-distribution exactly when its minimum eigenvalue is nonnegative, and the construction bounds its possible negative eigenvalue using the deviations from spherical moments.Source: §6.5 · p. 36
• The repair changes only degree-1 and degree-2 evaluations, leaving degree-3 and degree-4 evaluations unchanged while preserving the constraint kernel.The analysis bounds the nonnegativity defect by expanding quadratic polynomials in the monomial basis and controlling the correction with the assumed moment deviations.Source: §6.5 · pp. 37–38

6.6 Repairing Almost-Pseudo-Distributions

• The repair tool converts a linear functional with minimum eigenvalue −ε into a valid sphere pseudo-distribution, at a slight evaluation cost.The corrected functional preserves normalization and the unit-sphere constraint through convex combination.Source: §6.6 · pp. 38–39

6.7 Putting Everything Together

• Section 6.7 assembles the preceding constructions and repair steps to prove the paper’s degree-4 and degree-3 lower-bound theorems.The degree-4 proof is presented first because it contains many of the ideas used in the degree-3 proof.Source: §6.7 · p. 39

6.7.1 The Degree-4 Lower Bound

• The degree-4 lower-bound proof constructs a pseudo-expectation whose moments remain highly correlated with A while enforcing the unit-sphere constraint.It first forms a biased functional from the uniform sphere expectation and a maximally symmetric tensor-derived functional, then applies the repair lemma.Source: §6.7.1 · pp. 39–40

6.7.2 The Degree-3 Lower Bound

• The degree-3 lower-bound proof begins with moments matching the uniform sphere through degree two and degree-three moments ε-correlated with A.A symmetric Schur-complement extension then produces a valid degree-4 pseudo-expectation under the theorem’s assumptions.Source: §6.7.2 · pp. 41–42
• The degree-3 construction uses tensor flattenings and symmetrized Schur complements to identify a spectrally small extension compatible with the required moment matrices.The analysis exploits permutation symmetry, reducing the argument to the identity permutation and expressing the relevant matrices through A and its flattenings.Source: §6.7.2 · p. 41
• After extension, the degree-3 proof applies the repair lemmas to enforce the sphere constraint and correct a remaining negative eigenvalue.The repair incurs a constant-factor loss in the value assigned to A(x).Source: §6.7.2 · pp. 42–43

Odd-k reduction

• For odd k, substituting y_β = x_β for |β| = (k + 1)/2 reduces the problem to degree 3, with unequal-dimension random-polynomial bounds supplied by Theorem B.5.The substitution is applied after splitting signal and noise so the rounding argument remains valid with only syntactic changes to Lemma A.5.Source: §7 · p. 44

Even-k case

• For even k, degree-k SoS does not improve on Montanari and Richard’s tensor unfolding algorithms [MR14], although an alternative substitution can extract v0 directly from degree-2 pseudo-moments.The recovered vector satisfies ⟨v0, v⟩^2 ≥ 1 − ε, and recovery is only up to sign because the input is invariant under v0 → −v0.Source: §7 · pp. 44–45

General-k guarantees

• For odd k and τ ≿ n^(k/4) log(n)^(1/4)/ε, semidefinite programming recovers v with ⟨v0, v⟩ ≥ 1 − ε and certifies near-optimality with high probability.The certificate bounds T(x) by τ·⟨v, x⟩^k + O(n^(k/4) log(n)^(1/4)) for a suitable unit vector v, implying closeness to a maximum likelihood estimator.Source: §7 · p. 44

Implementation

• The semidefinite programs for odd k can be solved approximately in time ˜O(m^(1+1/k)), where m = n^k is the input size, while even-k algorithms run in nearly-linear time.Source: §7 · pp. 44–45

Tensor unfolding

• For odd k with τ ≿ n^(k/4)/ε, nearly-linear-time tensor unfolding recovers v with ⟨v, v0⟩^2 ≥ 1 − ε under independent Gaussian noise.This partially resolves a conjecture of Montanari and Richard, proving the conjectured signal-to-noise ratio under an asymmetric rather than symmetric noise model.Source: §7 · p. 45

Open Problems

• An open problem is whether degree d > 4 SoS can certify an n^3/4−δ bound for degree-3 Gaussian polynomials, potentially improving tensor PCA signal-to-noise guarantees.The same question is also of independent interest for certifying bounds on homogeneous polynomials with random coefficients.Source: Open Problems · p. 45
• A complementary open problem is extending the lower bound to degree d > 4 SoS and characterizing the degree needed to certify an n^3/4−δ bound.This degree-characterization problem was independently suggested by Boaz Barak.Source: Open Problems · p. 45
• The linear-time tensor PCA algorithm under symmetric noise may be simplifiable by removing its random rotations and submatrix decomposition.Montanari and Richard’s conjecture suggests that the linear-time algorithm for asymmetric noise may already succeed in the symmetric case.Source: Open Problems · p. 45

Quadric Sampling

• A degree-d pseudo-distribution with d ≥ 2 admits a true distribution matching every degree-2 polynomial expectation, and it can be sampled in poly(n) time.This is the quadric-sampling lemma.Source: A Pseudo-Distribution Facts · p. 47

Pseudo-Cauchy–Schwarz

• The section records function, powered-function, and multiplicative-function versions of pseudo-Cauchy–Schwarz for vector-valued polynomials and pseudo-distributions.The powered version follows by tensorizing the vectors and applying the function version.Source: A Pseudo-Distribution Facts · p. 48

Correlation Bound

• If a degree-4 pseudo-distribution satisfies ||x||^2 = 1 and E~⟨x, v_0⟩^3 ≥ 1 − ε, then E~⟨x, v_0⟩ ≥ 1 − 2ε.The proof uses a nonnegative univariate polynomial on [−1,1] together with SoS inequalities implied by the unit-norm constraint.Source: A Pseudo-Distribution Facts · p. 48

Operator-Norm Bound

• For degree-4 pseudo-distributions and M ∈ R^(n^2×n), E~⟨x^⊗2, Mx⟩ ≤ ||M||(E~||x||^4)^(3/4).The bound is obtained by expanding in the monomial basis, applying pseudo-Cauchy–Schwarz, and relating MM^T to the relevant matrix representation.Source: A Pseudo-Distribution Facts · p. 49

B.1 Elementary Random Matrix Review

• The review situates these tools within established random-matrix theory, citing Tao, Vershynin, and Tropp.The covariance and operator-norm results are attributed to, while matrix Bernstein is attributed to.Source: §B.1 · pp. 49–50
• Subgaussianity is defined through the ψ2 norm of random variables and one-dimensional marginals, with Gaussian and independent sign vectors as examples.The presentation follows Vershynin.Source: §B.1 · p. 50
• Empirical covariance matrices of subgaussian vectors concentrate in operator norm when N ≥ C(t/δ)^2m, achieving error at most δ with probability 1 − 2 exp(−t^2m).The constant C depends only on the distribution’s subgaussian norm K.Source: §B.1 · p. 50
• Matrix Bernstein controls sums of independent square random matrices under a uniform deviation bound R and a variance parameter σ^2.The variance parameter is defined using the larger of the two relevant expected matrix-product operator norms; the theorem applies for all t ≥ 0.Source: §B.1 · p. 50
• An n×n Gaussian matrix has operator norm O(√n) with probability 1 − n^−ω(1).This is a special case of a standard random-matrix operator-norm bound.Source: §B.1 · p. 50
• An n^2 × n Gaussian matrix has operator norm O(n) with probability 1 − n^−ω(1).The result provides the rectangular-matrix estimate needed alongside the square-matrix bound.Source: §B.1 · p. 50

Concentration theorem

• Theorem B.5 controls nontrivial permutations of A A^T for independent ±1 or Gaussian matrix entries with probability 1−O(n^−100).The result applies to iid matrices A_1,…,A_n^c and is the section’s main concentration statement.Source: §B.2 · p. 50

Application to Theorem 3.3

• Theorem B.5 implies Theorem 3.3 by identifying E[A⊗A] and the identity as matrix representations of ||x||^4, yielding λ=O(n^3/4 log(n)^1/4).The deduction uses the concentration result for tensor slices and the relation n=O(λ).Source: §B.2 · p. 51

Proof ingredients

• Lemma B.6 gives an exponentially small tail for the operator norm of each random matrix around the scale n^(d/2).For t≥1, the probability that ||A|| exceeds t n^(d/2) is at most 2^(−t^2 n^d/K).Source: §B.2 · p. 51
• The proof truncates the matrices using the norm bound, shows truncation changes expectations only slightly, and applies a non-symmetric matrix Bernstein inequality.A union bound then combines the individual norm control, expectation comparison, and concentration of the truncated summands.Source: §B.2 · pp. 51–53

General odd k

• For odd k, the Gaussian unfolding satisfies A^T A = n^((k+1)/2)I + E with ||E|| <= O(n^(k/2) log(n)).The bound holds with probability 1 − O(n^−100).Source: §B.3 · p. 53
• For the same unfolding, the signal-noise interaction obeys ||A^T V|| <= O(n^((k−1)/4) log(n)^1/2) with probability 1 − O(n^−100).The proof uses the rank-one representation V = uw^T and Gaussian concentration for A^T u.Source: §B.3 · p. 53

Proof strategy

• The concentration argument applies a rectangular Gaussian matrix bound under parameters δ = O(1/√n) and t = 1.These parameters yield the required dimension condition and failure probability at most O(n^−100).Source: §B.3 · p. 53

• The concentration lemmas hold simultaneously over permutations with probability 1−O(n^-50), providing the probabilistic foundation for the lower bounds.For random Gaussian 3-tensors, λ=O(n^3/2/log(n)^1/2); for random Gaussian 4-tensors, λ2=O(n).Source: §B.4 · pp. 53, 54, 56
• For the 3-tensor case, concentration bounds control the projected operator and related polynomial evaluations, including off-diagonal values O(1/n^2) after a union bound.The proof combines Gaussian tail or Chernoff bounds, triangle inequalities, permutation union bounds, and projection onto the relevant subspace.Source: §B.4 · pp. 54, 56
• For diagonal 3-tensor evaluations, concentration yields |O(λ^2)L||x||^4−5n|=O(log^1/2 n) and a normalized error O(log^1/2 n/n).These estimates complete the diagonal part of the 3-tensor concentration argument.Source: §B.4 · p. 56
• For 4-tensors, Gaussian matrix-norm and entrywise concentration with λ2=O(n) imply n^2 max_i,j |L||x||^2x_ix_j|=O(1).The argument treats diagonal and off-diagonal cases together because no special diagonal structure is needed.Source: §B.4 · p. 56