Theorem 23.6: for ε < 1 and W (ε,2s)-RIP, every ‖·‖₀-minimizer v with Wv = Wx equals x when ‖x‖₀ ≤ s
ProvedUnderstandingML.rip_exact_recoverycompressed-sensingrestricted-isometrysparse-recovery
Theorem 23.6. Let and let be an -RIP matrix. Let be a vector s.t. , let be the compression of , and let be a reconstructed vector. Then, .
Preamble
import Definitions.Def_UnderstandingML_DimReduction open MeasureTheory ProbabilityTheory
Formal statement
namespace UnderstandingML
/-- **Theorem 23.6** (p. 331). Let `ε < 1` and let `W` be an `(ε, 2s)`-RIP matrix. Let `x` be a
vector s.t. `‖x‖₀ ≤ s`, let `y = Wx` be the compression of `x`, and let
`x̃ ∈ argmin_{v : Wv = y} ‖v‖₀` be a reconstructed vector. Then `x̃ = x`. -/
theorem rip_exact_recovery {n d s : ℕ} (ε : ℝ) (hε : ε < 1) (W : Matrix (Fin n) (Fin d) ℝ)
(hW : IsRIP ε (2 * s) W) (x xt : Fin d → ℝ) (hx : l0Norm x ≤ s)
(hy : W.mulVec xt = W.mulVec x) (hmin : ∀ v, W.mulVec v = W.mulVec x → l0Norm xt ≤ l0Norm v) :
xt = x := by sorry
end UnderstandingML
Source
Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms, Cambridge University Press 2014, doi:10.1017/CBO9781107298019, §23.3 pp. 331-332, Theorem 23.6 with its proof
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.