§8.5, p. 169 — condition (ii) of Observation 8.5.1 forces m ≥ 2r
ProvedMatousekLP.SparseRecovery.two_r_le_mlinear-algebralinear-programmingp2o-batch-b23bp2o-gran-per-chapterp2o-plan-bookp2o-v1sparse-recovery
Let be a real matrix with (the standing assumption of the sparse-solution problem in §8.5), and let be an integer. Suppose every or fewer columns of are linearly independent (condition (ii) of Observation 8.5.1). Then
Combined with Observation 8.5.1, this says that uniqueness of -sparse solutions requires at least equations.
Formalization Note Column of is Aᵀ j; the hypothesis is the book's standing assumption on page 168 ("an matrix with "), without which the claim fails (e.g. , , ).
Preamble
import Mathlib import Definitions.Def_MatousekLP_SparseRecovery_BasisPursuit
Formal statement
namespace MatousekLP.SparseRecovery
open Matrix
/-- **§8.5, p. 169** (remark after Observation 8.5.1), Matoušek & Gärtner, *Understanding and
Using Linear Programming*, Springer 2007: "(ii) implies that, in particular, `m ≥ 2r`".
Condition (ii) of Observation 8.5.1 says that every `2r` or fewer columns of the `m × n` matrix
`A` are linearly independent. The standing assumption `m < n` of §8.5 (p. 168, "an `m × n`
matrix `A` with `m < n`") is a hypothesis. -/
theorem two_r_le_m {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ) (r : ℕ) (hmn : m < n)
(hii : ∀ S : Finset (Fin n), S.card ≤ 2 * r →
LinearIndependent ℝ (fun j : S => Aᵀ (j : Fin n))) :
2 * r ≤ m := by sorry
end MatousekLP.SparseRecovery
Source
Matoušek & Gärtner, Understanding and Using Linear Programming, Springer 2007, p. 169, §8.5 (remark after Observation 8.5.1: "(ii) implies that, in particular, m ≥ 2r"); standing assumption m < n from the box on p. 168
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.