Observation 8.5.1 — uniqueness of sparse solutions iff every 2r columns are independent
ProvedMatousekLP.SparseRecovery.sparse_unique_iff_columns_linIndeplinear-algebralinear-programmingp2o-batch-b23bp2o-gran-per-chapterp2o-plan-bookp2o-v1sparse-recovery
Fix integers and let be a real matrix. Call a sparse solution of if and , where . Then the following two conditions are equivalent:
- for every , the system has at most one sparse solution;
- every or fewer columns of are linearly independent, i.e. for every set of column indices with , the columns are linearly independent in .
This is the linear-algebra criterion for sparse solutions to be unique, independent of how they are computed.
Formalization Note Column of is Aᵀ j, and "every or fewer columns" ranges over finsets of distinct column indices. Indices are . At condition 2 is vacuous and condition 1 holds trivially, as on the page.
Preamble
import Mathlib import Definitions.Def_MatousekLP_SparseRecovery_BasisPursuit
Formal statement
namespace MatousekLP.SparseRecovery
open Matrix
/-- **Observation 8.5.1**, Matoušek & Gärtner, *Understanding and Using Linear Programming*,
Springer 2007, p. 168. With `n, m, r` fixed, for an `m × n` matrix `A` the following are
equivalent: (i) the system `Ax = b` has at most one sparse solution `x` (i.e. `Ax = b`,
`|supp(x)| ≤ r`) for every `b`; (ii) every `2r` or fewer columns of `A` are linearly
independent. Column `j` of `A` is `Aᵀ j`. -/
theorem sparse_unique_iff_columns_linIndep {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ) (r : ℕ) :
(∀ (b : Fin m → ℝ) (x' x'' : Fin n → ℝ),
IsSparseSolution A b r x' → IsSparseSolution A b r x'' → x' = x'') ↔
(∀ S : Finset (Fin n), S.card ≤ 2 * r →
LinearIndependent ℝ (fun j : S => Aᵀ (j : Fin n))) := by sorry
end MatousekLP.SparseRecovery
Source
Matoušek & Gärtner, Understanding and Using Linear Programming, Springer 2007, p. 168, Observation 8.5.1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.