§8.5, p. 174 — L is good for z iff L ∩ C_z = {0}
ProvedMatousekLP.SparseRecovery.good_iff_kernel_inter_coneconvex-geometrylinear-programmingp2o-batch-b23bp2o-gran-per-chapterp2o-plan-bookp2o-v1sparse-recovery
Let be a real matrix with kernel , let , and let be a boundary point of the crosspolytope , i.e. , with . Let
Say that is good for if . Then
Together with Lemma 8.5.4, this recasts BP-exactness as the condition that the kernel avoids the cones at the sparse boundary points of the crosspolytope, which is the starting point of the probabilistic proofs of Theorem 8.5.2.
Formalization Note The hypotheses and are the book's "for as above"; is the kernel of , as in the book's setting of a random matrix .
Preamble
import Mathlib import Definitions.Def_MatousekLP_SparseRecovery_BasisPursuit
Formal statement
namespace MatousekLP.SparseRecovery
open Matrix
/-- **§8.5, p. 174** ("Intuition for BP-exactness"), Matoušek & Gärtner, *Understanding and
Using Linear Programming*, Springer 2007. Let `z` be a boundary point of the crosspolytope
(`‖z‖₁ = 1`) with `|supp(z)| ≤ r`, and let `C_z = {t(x − z) : t ≥ 0, x ∈ B₁ⁿ}`. Then "`L`
good for `z`" (`(L + z) ∩ B₁ⁿ = {z}`) "means exactly that `L ∩ C_z = {0}`", for `L` the
kernel of `A`. -/
theorem good_iff_kernel_inter_cone {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ) (r : ℕ)
(z : Fin n → ℝ) (hz : l1Norm z = 1) (hsupp : (supp z).card ≤ r) :
IsGoodFor (kernel A) z ↔ kernel A ∩ coneAt z = {0} := by sorry
end MatousekLP.SparseRecovery
Source
Matoušek & Gärtner, Understanding and Using Linear Programming, Springer 2007, p. 174, §8.5 "Intuition for BP-exactness" ("Then L good for z means exactly that L ∩ C_z = {0}")
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.