Theorem 1, proof (forward direction) — an exact cover gives x = 1_J with Ax = b and exactly m/3 nonzeros
ProvedSparseApprox.Hardness.exactCover_gives_exact_solutionexact-covernp-hardness-reductionp2o-batch-p200ap2o-gran-per-chapterp2o-plan-paperp2o-v1sparse-approximation
Let and let be a list of 3-element subsets of . Let be the incidence matrix of ( if , else ) and . If the sub-collection is an exact cover of , then the indicator vector ( for , otherwise) satisfies
that is, solves the system exactly and has exactly nonzero entries.
This is the forward direction of the equivalence behind Theorem 1: an exact cover yields a solution of the SAS instance (with any tolerance, in particular ) with nonzero entries.
Formalization Note "Exactly nonzero entries" is written , avoiding natural-number division; it contains the paper's remark that must be a multiple of when an exact cover exists. The number of nonzeros of is .
Preamble
import Mathlib import Definitions.Def_SparseApprox_Hardness_Basic
Formal statement
namespace SparseApprox.Hardness
theorem exactCover_gives_exact_solution {m n : ℕ} (C : Fin n → Finset (Fin m))
(hC : ∀ j, (C j).card = 3) (J : Finset (Fin n)) (hJ : IsExactCover C J) :
Matrix.toEuclideanLin (incidence C) (indicatorVec J) = onesVec m ∧
3 * nnz (indicatorVec J) = m := by sorry
end SparseApprox.Hardness
Source
Natarajan, Sparse Approximate Solutions to Linear Systems, SIAM J. Comput. 24 (1995), p. 228, proof of Theorem 1, second-to-last paragraph ("If the X3C instance has a solution, then consider the vector x …")
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.