Theorem 1, proof (converse, conclusion) — the sets c_j with x_j ≠ 0 form an exact cover
ProvedSparseApprox.Hardness.support_isExactCoverexact-covernp-hardness-reductionp2o-batch-p200ap2o-gran-per-chapterp2o-plan-paperp2o-v1sparse-approximation
Let be a list of 3-element subsets of , let be its incidence matrix and . Suppose satisfies
Then the sub-collection is an exact cover of : every element of lies in exactly one set with .
This is the conclusion of the converse direction of the proof of Theorem 1: a sparse approximate solution of the constructed SAS instance yields an exact cover.
Formalization Note "At most nonzero entries" is written , avoiding natural-number division. is given by its index set , so repeated sets in are distinct indices.
Preamble
import Mathlib import Definitions.Def_SparseApprox_Hardness_Basic
Formal statement
namespace SparseApprox.Hardness
theorem support_isExactCover {m n : ℕ} (C : Fin n → Finset (Fin m))
(hC : ∀ j, (C j).card = 3) (x : EuclideanSpace ℝ (Fin n))
(hx : ‖Matrix.toEuclideanLin (incidence C) x - onesVec m‖ ≤ 1 / 2)
(hsparse : 3 * nnz x ≤ m) :
IsExactCover C (Finset.univ.filter (fun j => x j ≠ 0)) := by sorry
end SparseApprox.Hardness
Source
Natarajan, Sparse Approximate Solutions to Linear Systems, SIAM J. Comput. 24 (1995), p. 228, proof of Theorem 1, last paragraph, last two sentences ("Now consider the subcollection Ĉ … It is clear that Ĉ is an exact cover for S")
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.