Theorem 1, proof (converse, first step) — ‖Ax − b‖₂ ≤ 1/2 forces every entry of Ax into [1/2, 3/2]
ProvedSparseApprox.Hardness.entries_between_half_and_three_halvesexact-covernp-hardness-reductionp2o-batch-p200ap2o-gran-per-chapterp2o-plan-paperp2o-v1sparse-approximation
Let be a list of subsets of , let be its incidence matrix and . For every with and every row ,
In particular every entry of is nonzero, so every element lies in some set with . This is the first step of the converse direction in the proof of Theorem 1.
Formalization Note The statement holds for every , with no sparsity assumption and no condition on the sizes of the sets; is the Euclidean norm on EuclideanSpace ℝ (Fin m).
Preamble
import Mathlib import Definitions.Def_SparseApprox_Hardness_Basic
Formal statement
namespace SparseApprox.Hardness
theorem entries_between_half_and_three_halves {m n : ℕ} (C : Fin n → Finset (Fin m))
(x : EuclideanSpace ℝ (Fin n))
(hx : ‖Matrix.toEuclideanLin (incidence C) x - onesVec m‖ ≤ 1 / 2) (i : Fin m) :
1 / 2 ≤ Matrix.toEuclideanLin (incidence C) x i ∧
Matrix.toEuclideanLin (incidence C) x i ≤ 3 / 2 := 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, first sentence ("Since ‖Ax − b‖₂ ≤ 1/2, each entry of Ax must be between 1/2 and 3/2")
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.