§8.5, p. 170 — basis pursuit (BP) is the linear program (BP′)
ProvedMatousekLP.SparseRecovery.bp_iff_bp_primebasis-pursuitlinear-programmingp2o-batch-b23bp2o-gran-per-chapterp2o-plan-bookp2o-v1sparse-recovery
Let be a real matrix and . Consider basis pursuit
Then:
- in every optimal solution of (BP′), for every ;
- is an optimal solution of (BP) if and only if is an optimal solution of (BP′), where .
This is what makes basis pursuit solvable by linear programming.
Formalization Note The book's sentence ("in an optimal solution of (BP′) we have for every ") is part 1; the equivalence of the two problems that the book draws from it is formalized as part 2. Optimality is stated against every feasible point.
Preamble
import Mathlib import Definitions.Def_MatousekLP_SparseRecovery_BasisPursuit
Formal statement
namespace MatousekLP.SparseRecovery
open Matrix
/-- **Equivalence of (BP) and (BP′)**, §8.5, p. 170, Matoušek & Gärtner, *Understanding and
Using Linear Programming*, Springer 2007: "in an optimal solution of (BP′) we have `uᵢ = |xᵢ|`
for every `i`". Formalized as: (1) every optimal solution `(x, u)` of (BP′) has `uᵢ = |xᵢ|`
for all `i`; (2) `x` is an optimal solution of (BP) if and only if `(x, |x|)` is an optimal
solution of (BP′), where `|x|` is the componentwise absolute value. -/
theorem bp_iff_bp_prime {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ) (b : Fin m → ℝ) :
(∀ x u : Fin n → ℝ, IsBPPrimeOptimal A b x u → ∀ i, u i = |x i|) ∧
(∀ x : Fin n → ℝ, IsBPOptimal A b x ↔ IsBPPrimeOptimal A b x (fun i => |x i|)) := by sorry
end MatousekLP.SparseRecovery
Source
Matoušek & Gärtner, Understanding and Using Linear Programming, Springer 2007, p. 170, §8.5 (equivalence of (BP) and (BP′), unnumbered)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.