Proof of Lemma 8.5.4, p. 173 — the solution set of Ax = b is L + z
ProvedMatousekLP.SparseRecovery.solutions_eq_translate_kernellinear-algebralinear-programmingp2o-batch-b23bp2o-gran-per-chapterp2o-plan-bookp2o-v1sparse-recovery
Let be a real matrix, its kernel, , and let satisfy . Then the set of all solutions of is exactly the affine subspace :
This step turns the uniqueness of the (BP) optimum into a statement about how the affine subspace meets an -ball.
Preamble
import Mathlib import Definitions.Def_MatousekLP_SparseRecovery_BasisPursuit
Formal statement
namespace MatousekLP.SparseRecovery
open Matrix
/-- **Step in the proof of Lemma 8.5.4**, §8.5, p. 173, Matoušek & Gärtner, *Understanding and
Using Linear Programming*, Springer 2007: "the set of all solutions of `Ax = b` is exactly the
affine subspace `L + z`", where `L = {x : Ax = 0}` and `z` is a solution of `Ax = b`. -/
theorem solutions_eq_translate_kernel {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ)
(b : Fin m → ℝ) (z : Fin n → ℝ) (hz : A *ᵥ z = b) :
{x : Fin n → ℝ | A *ᵥ x = b} = translate (kernel A) z := by sorry
end MatousekLP.SparseRecovery
Source
Matoušek & Gärtner, Understanding and Using Linear Programming, Springer 2007, p. 173, proof of Lemma 8.5.4 ("the set of all solutions of Ax = b is exactly the affine subspace L + z")
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.