§3, pp.4–5 — the matrix (4) has a nonnegative factorization of size (corrected: )
ProvedPSDPolyApprox.slack_submatrix_factorizationextension-complexityhypercontractivityp2o-correctedp2o-gran-per-chapterp2o-plan-paperp2o-v1polyhedral-approximationpositive-semidefinite-cone
Let , , and let be a polytope with
Then the matrix (4),
can be written as a sum of entrywise nonnegative rank-one matrices; that is, .
This is the step of the proof that turns a small polytope between and , , into a small nonnegative factorization: the rows of are the points of , the columns are the valid inequalities of , and the entries are the slacks.
Differences from the source:
- correction: the hypercube submatrix (4) of the slack matrix of ((1 − ǫ)C, C) has nonnegative rank at most xc(Q), for every n → the same for n ≥ 2; reason: at n = 1, C = {0}, so Q = {0} has xc(Q) = 0, while (4) is the nonzero all-ones 2 × 2 matrix
- reading: "we are thus led to study the nonnegative rank of" (3) and its submatrix (4), via Theorem 4 → an explicit statement that (4) has a nonnegative factorization of size xc(Q); reason: this is the inequality the text uses; it is stated separately because C is not full-dimensional in ℝ^{n×n}, so Theorem 4 does not apply verbatim
- encoding: rows and columns indexed by {−1/√n, +1/√n}^n → rows and columns indexed by {−1, 1}^n with the entry (1 − ǫ)(1/n)(xᵀy)² + ǫ; reason: the paper's own rescaling in (4)
- encoding: sets of n × n matrices → their images in ℝ^{n×n} under the flattening Matrix.vec; reason: vec is a linear isomorphism carrying the trace inner product to the dot product; extension complexity is invariant under it (equations are free)
- encoding: extension complexity = smallest number of facets of a polytope whose linear image is P (Definition 1) → smallest number of inequalities of an extended formulation of P (ExtensionComplexity.TSP.extensionComplexity); reason: the two minima coincide for polytopes of dimension ≥ 1 (Fiorini et al., J. ACM 2015, Theorem 3, published as ExtensionComplexity.TSP.yannakakis_factorization), and every polytope in this statement has dimension ≥ 1
Preamble
import Mathlib import Definitions.Def_ExtensionComplexity_TSP_Polytope import Definitions.Def_ExtensionComplexity_TSP_extensionComplexity import Definitions.Def_ExtensionComplexity_TSP_SlackMatrix import Definitions.Def_PSDPolyApprox_shiftedDensity import Definitions.Def_PSDPolyApprox_slackSubmatrix open ExtensionComplexity.TSP open scoped Pointwise
Formal statement
namespace PSDPolyApprox
/-- **The matrix (4) has a nonnegative factorization of size `xc(Q)`.**
Fawzi, arXiv:1811.09649v1, §3, pp.4–5: "By checking that
1 − ⟨(1 − ǫ)(xxT − 1/n In), In − nyyT⟩ = (1 − ǫ)n(xT y)2 + ǫ we are thus led to study the
nonnegative rank of the following infinite matrix … It will be enough for us to consider the
submatrix indexed by elements of the hypercube {−1/√n, +1/√n}n" — the matrix (4).
For `n ≥ 2`, `0 < ε < 1` and a polytope `Q` with `(1 − ε)(D − (1/n)Iₙ) ⊆ Q ⊆ D − (1/n)Iₙ`, the
`2ⁿ × 2ⁿ` matrix `(x, y) ↦ (1 − ε)(1/n)(xᵀy)² + ε` has a nonnegative factorization with
`xc(Q)` rank-one terms, i.e. `rank₊ ≤ xc(Q)`.
**Formalization Note.** This is the "rank₊ ≤ xc" half of Theorem 4 for the pair
`((1 − ε)C, C)`, `C = D − (1/n)Iₙ`, restricted to the hypercube rows and columns; it is a separate
statement because `C` is not full-dimensional in `ℝ^{n×n}`. `n ≥ 2` is needed: at `n = 1`,
`Q = {0}` has `xc = 0` while the matrix is the nonzero all-ones `2 × 2` matrix. -/
theorem slack_submatrix_factorization (n : ℕ) (hn : 2 ≤ n) (ε : ℝ) (hε0 : 0 < ε) (hε1 : ε < 1)
(Q : Set (Fin n × Fin n → ℝ)) (hQ : IsPolytope Q)
(hin : (1 - ε) • shiftedDensity n ((n : ℝ)⁻¹ • (1 : Matrix (Fin n) (Fin n) ℝ)) ⊆ Q)
(hout : Q ⊆ shiftedDensity n ((n : ℝ)⁻¹ • (1 : Matrix (Fin n) (Fin n) ℝ))) :
HasNonnegFactorization (slackSubmatrix ε n) (extensionComplexity Q) := by sorry
end PSDPolyApprox
Source
Fawzi, On polyhedral approximations of the positive semidefinite cone, arXiv:1811.09649v1, §3, pp.4–5, the slack-matrix computation and equation (4)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.