Theorem 1, proof (converse, second step) — a 1/2-approximate solution has at least m/3 nonzeros
ProvedSparseApprox.Hardness.nnz_ge_thirdexact-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 . Every with has at least nonzero entries:
This is the step "since each column of has only three nonzero entries, must have at least entries" of the proof of Theorem 1; combined with the sparsity assumption it shows that has exactly nonzero entries.
Formalization Note "At least " is written multiplicatively, , to avoid natural-number division. The hypothesis that every has exactly elements is the paper's "3-element subsets".
Preamble
import Mathlib import Definitions.Def_SparseApprox_Hardness_Basic
Formal statement
namespace SparseApprox.Hardness
theorem nnz_ge_third {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) :
m ≤ 3 * nnz x := 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, second sentence ("Since each column of A has only three nonzero entries, x must have at least m/3 entries")
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.