Lemma 1, pp. 5–6 — a basic-procedure certificate z gives x_i ≤ ‖x‖∞/2 on L ∩ ℝⁿ₊, and σ_i(DL) = 2σ_i(L), σ_j(DL) = σ_j(L) for D = I + e_ie_iᵀ
ProvedProjRescale.MaxSupport.lemma_1condition-measureorthogonal-projectionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1rescaling-algorithm
Let be a linear subspace and the orthogonal projection onto . Suppose and satisfy
Then
- every satisfies (equation (4));
- for (the diagonal matrix with and all other diagonal entries ), the rescaled subspace satisfies ;
- for every .
Here and is the positive part of . This lemma is the quantitative effect of one rescaling step of Algorithm 1: a certificate returned by the basic procedure doubles the condition coordinate and leaves the others unchanged.
Formalization Note is Mathlib's orthogonal projection onto viewed as a map ; and are written coordinatewise, and the hypothesis "" is stated literally.
Differences from the source: none.
Preamble
import Mathlib import Definitions.Def_ProjRescale_MaxSupport_Setting
Formal statement
namespace ProjRescale.MaxSupport
/-- Lemma 1, pp. 5–6. Let `P` be the orthogonal projection onto `L`, and let `z ∈ ℝⁿ₊ \ {0}` satisfy
`‖(Pz)⁺‖₁ ≤ ½‖z‖∞ = ½z_i`. Then every `x ∈ L ∩ ℝⁿ₊` has `x_i ≤ ‖x‖∞/2` (4), and for
`D = I + e_i e_iᵀ` the rescaled subspace satisfies `σ_i(DL) = 2σ_i(L)` and `σ_j(DL) = σ_j(L)` for
`j ≠ i`. -/
theorem lemma_1 {n : ℕ} (L : Submodule ℝ (E n)) (z : E n) (i : Fin n)
(hz : z ∈ nonneg n) (hz0 : z ≠ 0) (hzi : supNorm z = z i)
(hP : posL1 (L.starProjection z) ≤ supNorm z / 2) :
(∀ x ∈ L, x ∈ nonneg n → x i ≤ supNorm x / 2) ∧
sigmaI (diagScale (Function.update (fun _ => 1) i 2) L) i = 2 * sigmaI L i ∧
∀ j, j ≠ i → sigmaI (diagScale (Function.update (fun _ => 1) i 2) L) j = sigmaI L j := by sorry
end ProjRescale.MaxSupport
Source
Peña & Soheili, Projection and rescaling algorithm for finding maximum support solutions to polyhedral conic systems, arXiv:2003.08911v3, pp. 5–6, Lemma 1 (Equation (4))
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.