Chapter 03 — Convex Sets

Proofs omitted. Hover over highlighted terms to see their Lean types.

Definition 3.1

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Definition 3.1: for a subset C of a real ℝ-module E (hence in particular of a real vector space), convexity is the canonical predicate Convex ℝ C.

universe u open scoped Pointwise variable {E : Type u} [AddCommMonoid E] [Module ℝ E] recall Convex -- Proof sketch: specialize `convex_iff_pointwise_add_subset` to coefficients `a` and `1 - a`, -- then use `0 < a` and `a < 1` to obtain the required nonnegativity hypotheses; conversely, -- recover the textbook one-parameter form from the standard two-parameter characterization.

Definition 3.3

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Definition 3.3: the convex hull of C is the intersection of all convex subsets of the ambient Hilbert space that contain C. This is exactly the canonical mathlib theorem convexHull_eq_iInter.

universe u variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] recall convexHull_eq_iInter

Proposition 3.4

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Proposition 3.4: for a subset C of a real vector space 𝓗, the convex hull convexHull ℝ C is exactly the set of finite convex combinations of points of C, expressed canonically in mathlib by convexHull_eq using finite centers of mass with nonnegative coefficients summing to 1.

universe u open scoped BigOperators variable {𝓗 : Type u} [AddCommGroup 𝓗] [Module ℝ 𝓗] recall convexHull_eq

Proposition 3.5

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Proposition 3.5, image clause: the image of a convex set under an affine map is convex, canonically formalized by Convex.affine_image.

universe u v variable {E : Type u} {F : Type v} variable [AddCommGroup E] [Module ℝ E] variable [AddCommGroup F] [Module ℝ F] recall Convex.affine_image

Proposition 3.6

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Proposition 3.6 (1): the finite Minkowski sum of a family of convex subsets is convex, canonically formalized by convex_sum.

open scoped BigOperators Pointwise universe u v variable {ι : Type u} {E : Type v} [AddCommGroup E] [Module ℝ E] recall convex_sum

Proposition 3.7

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Proposition 3.7: a nonempty convex subset of a real Hilbert space on which every point has the same norm (β : ℝ) is a singleton.

universe u variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] -- Proof sketch: if `C` contained distinct points `x` and `y`, convexity would place their midpoint -- in `C`; applying `norm_combo_lt_of_ne` to the coefficients `1 / 2` and `1 / 2` would then force -- the midpoint to have norm strictly less than the common radius `(β : ℝ)`, contradicting the -- constant-norm hypothesis. Use `hC_nonempty` together with `Set.Subsingleton.eq_singleton_of_mem` -- to turn the resulting subsingleton conclusion into an equality `C = {z}`. theorem exists_eq_singleton_of_nonempty_convex_of_forall_norm_eq (C : Set 𝓗) (β : NNReal) (hC_nonempty : C.Nonempty) (hC_convex : Convex ℝ C) (hC_norm : ∀ x ∈ C, ‖x‖ = (β : ℝ)) : ∃ z : 𝓗, C = {z}

Definition 3.8

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Definition 3.8: a point p is a best approximation to x from C when it lies in C and realizes the distance from x to C.

universe u variable {X : Type u} [PseudoMetricSpace X] abbrev IsBestApproximation (x : X) (C : Set X) (p : X) : Prop := p ∈ C ∧ dist x p = Metric.infDist x C

Example 3.9

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Example 3.9: for a chosen singular value decomposition of A, the rank-q truncation is a best Frobenius approximation among matrices of rank at most q, and it is the unique best approximation exactly when the q-th singular value differs from the next one.

open scoped Matrix.Norms.Frobenius theorem eckart_young_theorem {M N : ℕ} (A : Matrix (Fin M) (Fin N) ℝ) (q : ℕ) (hq_pos : 0 < q) (h_rank : q < A.rank) (U : Matrix.orthogonalGroup (Fin M) ℝ) (V : Matrix.orthogonalGroup (Fin N) ℝ) (hsvd : A = ((U : Matrix (Fin M) (Fin M) ℝ) * singularValueDiagonal A) * Matrix.transpose (V : Matrix (Fin N) (Fin N) ℝ)) : IsBestApproximation A ({B : Matrix (Fin M) (Fin N) ℝ | B.rank ≤ q}) (eckartYoungApproximation A q U V) ∧ ((∀ Q, IsBestApproximation A ({B : Matrix (Fin M) (Fin N) ℝ | B.rank ≤ q}) Q → Q = eckartYoungApproximation A q U V) ↔ (Matrix.toEuclideanLin A).singularValues (q - 1) ≠ (Matrix.toEuclideanLin A).singularValues q)

Example 3.10

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Example 3.10: the projection onto the span of a finite orthonormal family is the orthogonal coordinate sum.

universe u v open scoped InnerProductSpace variable {I : Type v} [Fintype I] [DecidableEq I] variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] [CompleteSpace 𝓗] theorem projectionPoint_finite_orthonormal_span_eq_sum_inner (e : I → 𝓗) (he : Orthonormal ℝ e) (x : 𝓗) : projectionPoint (((Submodule.span ℝ (Set.range e) : Submodule ℝ 𝓗) : Set 𝓗)) (finite_span_range_isChebyshev e) x = ∑ i : I, ⟪x, e i⟫_ℝ • e i

Remark 3.11.1

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Remark 3.11.1: a proximinal set in a metric space is closed.

universe u variable {X : Type u} [MetricSpace X] theorem isClosed_of_isProximinalIn {C : Set X} (hC : IsProximinalIn C) : IsClosed C

Remark 3.11.2

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Remark 3.11.2: every finite-dimensional linear subspace of a real Hilbert space admits a unique best approximation to each point of the ambient space.

universe u open scoped InnerProductSpace variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] theorem finiteDimensionalSubspace_has_unique_best_approximations [CompleteSpace 𝓗] (C : Submodule ℝ 𝓗) [FiniteDimensional ℝ C] : IsChebyshev (C : Set 𝓗)

Proposition 3.12

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Proposition 3.12: in a finite-dimensional real Hilbert space, the metric projection point map onto a Chebyshev set is continuous.

universe u open Filter Bornology open scoped InnerProductSpace variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] [FiniteDimensional ℝ 𝓗] theorem continuous_projectionPoint_of_isChebyshev {C : Set 𝓗} (hC : IsChebyshev C) : Continuous (projectionPoint C hC)

Example 3.13

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Example 3.13 (1): if e is orthonormal and α n > 1 decreases to 1, then the set {α n • e n | n : ℕ} is closed.

universe u open Filter open scoped InnerProductSpace Topology variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] theorem isClosed_scaled_orthonormal_range (e : ℕ → 𝓗) (he : Orthonormal ℝ e) (α : ℕ → ℝ) (hα_gt_one : ∀ n : ℕ, 1 < α n) (_hα_antitone : Antitone α) (_hα_tendsto : Tendsto α atTop (nhds 1)) : IsClosed (Set.range (fun n ↦ α n • e n))

Proposition 3.14

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Proposition 3.14: every nonempty weakly closed subset of a real Hilbert space is proximinal, so every point admits a best approximation in the set.

universe u open scoped InnerProductSpace Pointwise variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] [CompleteSpace 𝓗] theorem exists_bestApproximation_of_nonempty_weaklyClosed {C : Set 𝓗} (hC : C.Nonempty) (hweak : IsClosed ((toWeakSpace ℝ 𝓗) '' C)) : IsProximinalIn C

Corollary 3.15

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Corollary 3.15: in a finite-dimensional real Hilbert space, a nonempty set is proximal if and only if it is closed.

universe u open scoped InnerProductSpace variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] [FiniteDimensional ℝ 𝓗] -- Proof sketch: for the forward implication, use the defining best-approximation condition to show -- that every point in the closure of `C` already belongs to `C`. For the reverse implication, fix -- `x`, choose a minimizing sequence in the nonempty closed set `C`, use compactness of closed -- bounded sets in finite dimensions to extract a convergent subsequence with limit in `C`, and -- show that the limit realizes `Metric.infDist x C`. theorem proximinal_iff_isClosed_of_nonempty {C : Set 𝓗} (hC : C.Nonempty) : IsProximinalIn C ↔ IsClosed C

Proposition 3.15.1

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Proposition 3.15.1: a Chebyshev set is proximinal.

universe u -- Proof sketch: for each `x`, discard the uniqueness part of the Chebyshev hypothesis and keep -- the realizing best approximation. theorem isProximinalIn_of_isChebyshev {X : Type u} [PseudoMetricSpace X] {C : Set X} (hC : IsChebyshev C) : IsProximinalIn C

Proposition 3.15.2

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Proposition 3.15.2: there exists a real normed linear space and a subset of it that is proximinal but not Chebyshev.

universe u variable {X : Type u} [MetricSpace X] theorem exists_proximinal_not_chebyshev_subset : ∃ (X : Type u) (_ : NormedAddCommGroup X) (_ : NormedSpace ℝ X) (C : Set X), IsProximinalIn C ∧ ¬ IsChebyshev C

Theorem 3.16.1

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Theorem 3.16.1: every nonempty closed convex subset of a real Hilbert space is a Chebyshev set, equivalently each point has a unique nearest point in the set.

universe u open scoped InnerProductSpace variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] [CompleteSpace 𝓗] theorem isChebyshev_of_nonempty_isClosed_convex {C : Set 𝓗} (hC_nonempty : C.Nonempty) (hC_closed : IsClosed C) (hC_convex : Convex ℝ C) : IsChebyshev C

Theorem 3.16.2

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Theorem 3.16.2: for a nonempty closed convex subset of a real Hilbert space, a point p is the projection of x onto C exactly when p ∈ C and ⟪y - p, x - p⟫_ℝ ≤ 0 for every y ∈ C. Here the projection is the canonical point projectionPoint C (isChebyshev_of_nonempty_isClosed_convex hC_nonempty hC_closed hC_convex) x, which also realizes Metric.infDist x C.

universe u open scoped InnerProductSpace variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] [CompleteSpace 𝓗] omit [CompleteSpace 𝓗] in -- Proof sketch: rewrite `IsBestApproximation` as the metric equality defining a nearest point, then -- `Mathlib.Analysis.InnerProductSpace.Projection.Minimal.norm_eq_iInf_iff_real_inner_le_zero`, -- rewriting `Metric.infDist` as the corresponding `iInf`. omit [CompleteSpace 𝓗] in -- Proof sketch: combine `projectionPoint_isBestApproximation` with the best-approximation -- characterization above, and conversely use uniqueness in the Chebyshev hypothesis. theorem eq_projectionPoint_iff_mem_and_inner_sub_right_nonpos_of_nonempty_isClosed_convex {C : Set 𝓗} (hC_nonempty : C.Nonempty) (hC_closed : IsClosed C) (hC_convex : Convex ℝ C) {x p : 𝓗} : p = projectionPoint C (isChebyshev_of_nonempty_isClosed_convex hC_nonempty hC_closed hC_convex) x ↔ p ∈ C ∧ ∀ y ∈ C, ⟪y - p, x - p⟫_ℝ ≤ 0

Proposition 3.19

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Proposition 3.19: the metric projection onto the translate y + C = {y + z | z ∈ C} is the translate of the metric projection onto C, namely P_{y+C}(x) = y + P_C(x - y).

universe u open scoped Pointwise InnerProductSpace variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] [CompleteSpace 𝓗] -- Proof sketch: let `p := projectionPoint C _ (x - y)` and `q := y + p`. Then `q ∈ y +ᵥ C`. -- Use the Hilbert-space characterization of projections onto nonempty closed convex sets on `C` -- and transport the variational inequality by translation to show that `q` is the projection of -- `x` onto `y +ᵥ C`. theorem projectionPoint_vadd_set_eq_add_projectionPoint {C : Set 𝓗} (x y : 𝓗) (hC_nonempty : C.Nonempty) (hC_closed : IsClosed C) (hC_convex : Convex ℝ C) : projectionPoint (y +ᵥ C) (isChebyshev_of_nonempty_isClosed_convex (hC_nonempty.vadd_set) (by simpa [vadd_eq_add] using hC_closed.left_addCoset y) (hC_convex.vadd y)) x = y + projectionPoint C (isChebyshev_of_nonempty_isClosed_convex hC_nonempty hC_closed hC_convex) (x - y)

Proposition 3.20

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Proposition 3.20: a decreasing sequence of nonempty bounded closed convex subsets of a real Hilbert space has nonempty intersection.

universe u open scoped InnerProductSpace variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] [CompleteSpace 𝓗] theorem nonempty_iInter_of_nonempty_bounded_isClosed_convex (C : ℕ → Set 𝓗) (h_nonempty : ∀ n, (C n).Nonempty) (h_bounded : ∀ n, Bornology.IsBounded (C n)) (h_closed : ∀ n, IsClosed (C n)) (h_convex : ∀ n, Convex ℝ (C n)) (h_anti : Antitone C) : (⋂ n, C n).Nonempty

Proposition 3.21

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Proposition 3.21: if C is a nonempty closed convex subset of a real Hilbert space, then the projection of every point on the ray starting at P_C x and pointing toward x remains P_C x.

universe u open scoped InnerProductSpace variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] [CompleteSpace 𝓗] variable {C : Set 𝓗} -- Proof sketch: let `p := projectionPoint C hC x`. To show that the projection of -- `p + t • (x - p)` is still `p`, it is enough to verify that `p` is again a best approximation -- for the new point. Use the variational characterization of nearest points on convex Chebyshev -- sets: the defining inequality for `p = projectionPoint C hC x` scales by the nonnegative factor -- `t`, so `p` also satisfies the characterization at `p + t • (x - p)`. theorem projectionPoint_ray_fixed_of_nonempty_isClosed_convex (hC_nonempty : C.Nonempty) (hC_closed : IsClosed C) (hC_convex : Convex ℝ C) (x : 𝓗) {t : ℝ} (ht : 0 ≤ t) : projectionPoint C (isChebyshev_of_nonempty_isClosed_convex hC_nonempty hC_closed hC_convex) (projectionPoint C (isChebyshev_of_nonempty_isClosed_convex hC_nonempty hC_closed hC_convex) x + t • (x - projectionPoint C (isChebyshev_of_nonempty_isClosed_convex hC_nonempty hC_closed hC_convex) x)) = projectionPoint C (isChebyshev_of_nonempty_isClosed_convex hC_nonempty hC_closed hC_convex) x

Corollary 3.22

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Corollary 3.22 (1): for a nonempty closed affine subspace of a real Hilbert space, a point is the metric projection of x exactly when it lies in the affine subspace and the residual x - p is orthogonal to every direction y - z with y, z ∈ C.

universe u open EuclideanGeometry open scoped InnerProductSpace variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] [CompleteSpace 𝓗] variable {C : AffineSubspace ℝ 𝓗} variable (hC_nonempty : (C : Set 𝓗).Nonempty) (hC_closed : IsClosed (C : Set 𝓗)) local notation "P" => projectionPoint (C : Set 𝓗) (isChebyshev_of_nonempty_isClosed_convex hC_nonempty hC_closed C.convex) theorem eq_projectionPoint_iff_mem_and_inner_sub_eq_zero_of_nonempty_isClosed_affineSubspace {x p : 𝓗} : p = P x ↔ p ∈ (C : Set 𝓗) ∧ ∀ y ∈ (C : Set 𝓗), ∀ z ∈ (C : Set 𝓗), ⟪y - z, x - p⟫_ℝ = 0

Example 3.23

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Example 3.23: the metric projection of x onto the hyperplane innerProductLevelSet u η = {z | ⟪z, u⟫_ℝ = η} is obtained by correcting x along the normal vector u.

universe u open scoped InnerProductSpace variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] variable [CompleteSpace 𝓗] -- Proof sketch: the hyperplane is nonempty by the explicit point `((η / ‖u‖ ^ 2) • u)`, it is -- closed by `hyperplane_isClosed`, and it is convex because it is an affine subspace; then apply -- the Hilbert-space nearest-point theorem for nonempty closed convex sets. theorem projectionPoint_hyperplane_eq_explicit (u : 𝓗) (η : ℝ) (hu : u ≠ 0) (x : 𝓗) : projectionPoint (innerProductLevelSet u η) (hyperplane_isChebyshev u η hu) x = x + ((η - ⟪x, u⟫_ℝ) / ‖u‖ ^ 2) • u

Corollary 3.24

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Corollary 3.24 (1): textbook clause (i). A point is the orthogonal projection of x onto the closed subspace V exactly when it lies in V and the residual vector lies in Vᗮ.

universe u open scoped InnerProductSpace variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] [CompleteSpace 𝓗] variable (V : ClosedSubmodule ℝ 𝓗) (x p : 𝓗) -- Proof sketch: use the uniqueness characterization of orthogonal projection onto a complete -- subspace. One direction combines `starProjection_apply_mem` with -- `sub_starProjection_mem_orthogonal`; the converse uses -- `eq_starProjection_of_mem_orthogonal`. theorem starProjection_eq_iff_mem_and_sub_mem_orthogonal : V.starProjection x = p ↔ p ∈ V ∧ x - p ∈ Vᗮ

Proposition 3.25

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Proposition 3.25: the set-valued projector onto C is unchanged after orthogonal projection onto the closed span of C, and consequently C is proximinal in the ambient Hilbert space if and only if it is proximinal in its closed span.

universe u open scoped InnerProductSpace variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] variable [CompleteSpace 𝓗] theorem setValuedProjector_eq_comp_closedSpanProjection_and_isProximinalIn_iff (C : Set 𝓗) (hC : C.Nonempty) : setValuedProjector C = setValuedProjector C ∘ ((Submodule.span ℝ C).topologicalClosure).starProjection ∧ (IsProximinalIn C ↔ IsProximinalIn (Subtype.val ⁻¹' C : Set ((Submodule.span ℝ C).topologicalClosure)))

Definition 3.26

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Definition 3.26 introduces the affine normal-equation solution set C_y = {x | T⋆ (T x) = T⋆ y}.

universe u v open ContinuousLinearMap open scoped InnerProductSpace variable {𝓗 : Type u} {𝓚 : Type v} variable [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] [CompleteSpace 𝓗] variable [NormedAddCommGroup 𝓚] [InnerProductSpace ℝ 𝓚] [CompleteSpace 𝓚] abbrev moorePenroseSolutionSet (T : 𝓗 →L[ℝ] 𝓚) (y : 𝓚) : Set 𝓗 := {x | adjoint T (T x) = adjoint T y}

Proposition 3.27

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Proposition 3.27: if range T is closed, then the least-squares problem min_z ‖T z - y‖ admits a solution, and for every x the following are equivalent: x is a least-squares solution, T x is the orthogonal projection of y onto range T, and T† (T x) = T† y.

open scoped InnerProductSpace open ContinuousLinearMap universe u v variable {H : Type u} {K : Type v} variable [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] variable [NormedAddCommGroup K] [InnerProductSpace ℝ K] [CompleteSpace K] theorem leastSquares_tfae_and_exists_of_closed_range (T : H →L[ℝ] K) (hclosed : IsClosed (T.range : Set K)) (y : K) : (∃ x : H, IsLeastSquaresSolution T y x) ∧ ∀ x : H, List.TFAE [IsLeastSquaresSolution T y x, T x = closedRangeProjection T hclosed y, adjoint T (T x) = adjoint T y]

Definition 3.27.1

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Definition 3.27.1: if the normal-equation solution set {x | T* (T x) = T* y} is nonempty, its minimal-norm element is the metric projection of 0 onto that closed affine set.

universe u v open ContinuousLinearMap open scoped InnerProductSpace variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] [CompleteSpace 𝓗] variable {𝓚 : Type v} [NormedAddCommGroup 𝓚] [InnerProductSpace ℝ 𝓚] [CompleteSpace 𝓚] noncomputable def minimalNormLeastSquaresSolution (T : 𝓗 →L[ℝ] 𝓚) (y : 𝓚) (h_nonempty : (moorePenroseSolutionSet T y).Nonempty) : 𝓗 := projectionPoint (moorePenroseSolutionSet T y) (isChebyshev_moorePenroseSolutionSet_of_nonempty_isClosed_affine T y h_nonempty) 0

Definition 3.28

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Definition 3.28: for a bounded operator T : 𝓗 →L[ℝ] 𝓚 with closed range, the generalized (Moore-Penrose) inverse sends y to the metric projection of 0 onto the affine solution set {x | T* (T x) = T* y}.

universe u v open ContinuousLinearMap open scoped InnerProductSpace variable {𝓗 : Type u} {𝓚 : Type v} variable [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] [CompleteSpace 𝓗] variable [NormedAddCommGroup 𝓚] [InnerProductSpace ℝ 𝓚] [CompleteSpace 𝓚] noncomputable def moorePenroseInverse (T : 𝓗 →L[ℝ] 𝓚) (hT_closed : IsClosed (T.range : Set 𝓚)) : 𝓚 → 𝓗 := fun y ↦ minimalNormLeastSquaresSolution T y (moorePenroseSolutionSet_nonempty_of_closed_range T hT_closed y)

Example 3.29

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Example 3.29: if T†T is invertible, then the operator (T†T)⁻¹ T† is the Moore-Penrose inverse of T.

universe u v open scoped InnerProductSpace open ContinuousLinearMap variable {𝓗 : Type u} {𝓚 : Type v} variable [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] [CompleteSpace 𝓗] variable [NormedAddCommGroup 𝓚] [InnerProductSpace ℝ 𝓚] [CompleteSpace 𝓚] theorem normalEquationPseudoinverse_isMoorePenroseInverse (T : 𝓗 →L[ℝ] 𝓚) [Fact (IsUnit (T.adjoint ∘L T))] : IsMoorePenroseInverse T ((T.adjoint ∘L T).inverse ∘L T.adjoint)

Proposition 3.30

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Proposition 3.30 (1): among the solutions of the normal equation T* (T x) = T* y, the unique one orthogonal to ker T is moorePenroseInverse T hT_closed y.

universe u v open ContinuousLinearMap open scoped InnerProductSpace variable {𝓗 : Type u} {𝓚 : Type v} variable [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] [CompleteSpace 𝓗] variable [NormedAddCommGroup 𝓚] [InnerProductSpace ℝ 𝓚] [CompleteSpace 𝓚] -- Proof sketch: apply the closed-range theorem to transfer the closedness of `range T` to -- `range T*`. theorem moorePenroseSolutionSet_inter_orthogonalKer_eq_singleton (T : 𝓗 →L[ℝ] 𝓚) (hT_closed : IsClosed (T.range : Set 𝓚)) (y : 𝓚) : moorePenroseSolutionSet T y ∩ (T.kerᗮ : Set 𝓗) = {moorePenroseInverse T hT_closed y}

Proposition 3.31

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Proposition 3.31: for bounded operators T : 𝓗 →L[ℝ] 𝓚 and T' : 𝓚 →L[ℝ] 𝓗 with closed ranges, the following are equivalent: (i) T' is the Moore-Penrose inverse of T; (ii) T ∘L T' and T' ∘L T are the orthogonal projections onto range T and range T'; (iii) T' ∘L T is the identity on T.kerᗮ and T' vanishes on T.rangeᗮ.

open scoped InnerProductSpace open ContinuousLinearMap universe u v variable {𝓗 : Type u} {𝓚 : Type v} variable [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] [CompleteSpace 𝓗] variable [NormedAddCommGroup 𝓚] [InnerProductSpace ℝ 𝓚] [CompleteSpace 𝓚] theorem isMoorePenroseInverse_tfae_projection_and_orthogonal_conditions (T : 𝓗 →L[ℝ] 𝓚) (T' : 𝓚 →L[ℝ] 𝓗) (hT_closed : IsClosed (T.range : Set 𝓚)) (hT'_closed : IsClosed (T'.range : Set 𝓗)) : List.TFAE [IsMoorePenroseInverse T T', T ∘L T' = closedRangeProjection T hT_closed ∧ T' ∘L T = closedRangeProjection T' hT'_closed, (∀ x ∈ T.kerᗮ, T' (T x) = x) ∧ ∀ y ∈ T.rangeᗮ, T' y = 0]

Corollary 3.32

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Corollary 3.32 (i): if T has closed range, then the Moore-Penrose inverse of T† is T itself.

open ContinuousLinearMap open scoped InnerProductSpace universe u v variable {𝓗 : Type u} {𝓚 : Type v} variable [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] [CompleteSpace 𝓗] variable [NormedAddCommGroup 𝓚] [InnerProductSpace ℝ 𝓚] [CompleteSpace 𝓚] theorem moorePenroseInverseOperator_moorePenroseInverseOperator (T : 𝓗 →L[ℝ] 𝓚) (hT_closed : IsClosed (T.range : Set 𝓚)) : moorePenroseInverseOperator (moorePenroseInverseOperator T hT_closed) (moorePenroseInverseOperator_range_isClosed T hT_closed) = T

Example 3.33

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Example 3.33: for C = {α n • e n | n : ℕ} coming from an orthonormal sequence and a monotone weight sequence in [1, +∞) tending to +∞ with non-summable inverse squares, C is norm closed and weakly sequentially closed, is not weakly closed, and satisfies 0 ∈ closure ((toWeakSpace ℝ 𝓗) '' C) and 0 ∉ C.

open Filter open scoped Topology InnerProductSpace universe u variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] variable [CompleteSpace 𝓗] theorem scaled_orthonormal_range_weaklySeqClosed_and_not_weaklyClosed (e : ℕ → 𝓗) (he : Orthonormal ℝ e) (α : ℕ → ℝ) (hα_ge_one : ∀ n : ℕ, 1 ≤ α n) (_hα_monotone : Monotone α) (hα_tendsto : Tendsto α atTop atTop) (hα_invSq_not_summable : ¬ Summable (fun n ↦ ((α n)⁻¹)^2)) : IsClosed (Set.range (fun n ↦ α n • e n)) ∧ IsSeqClosed ((toWeakSpace ℝ 𝓗) '' Set.range (fun n ↦ α n • e n)) ∧ ¬ IsClosed ((toWeakSpace ℝ 𝓗) '' Set.range (fun n ↦ α n • e n)) ∧ (0 : WeakSpace ℝ 𝓗) ∈ closure ((toWeakSpace ℝ 𝓗) '' Set.range (fun n ↦ α n • e n)) ∧ (0 : 𝓗) ∉ Set.range (fun n ↦ α n • e n)

Theorem 3.34

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Theorem 3.34, weak-closedness form: for a convex subset C of a real inner-product space, C is closed exactly when its image in WeakSpace ℝ 𝓗 is weakly closed.

universe u open Filter open scoped InnerProductSpace variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] theorem isClosed_iff_weak_image_isClosed_of_convex {C : Set 𝓗} (hC_convex : Convex ℝ C) : IsClosed C ↔ IsClosed ((toWeakSpace ℝ 𝓗) '' C)

Corollary 3.35

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Corollary 3.35: a weak limit of points in a closed convex set of a real inner-product space belongs to the set.

open Filter open scoped InnerProductSpace universe u variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] theorem mem_of_tendsto_weakly_of_isClosed_convex {C : Set 𝓗} (hC_closed : IsClosed C) (hC_convex : Convex ℝ C) {xₙ : ℕ → 𝓗} {x : 𝓗} (hxₙ : ∀ n, xₙ n ∈ C) (hweak : Tendsto (fun n ↦ toWeakSpace ℝ 𝓗 (xₙ n)) atTop (nhds (toWeakSpace ℝ 𝓗 x))) : x ∈ C

Corollary 3.36

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Corollary 3.36: (Mazur's lemma) if a sequence in a real normed space converges weakly to x, then one can choose a sequence of convex combinations of the initial segments xₙ 0, …, xₙ n that converges strongly to x.

open Filter open scoped BigOperators Topology universe u variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] theorem exists_stronglyConvergent_convex_combinations_of_tendsto_weakly (xₙ : ℕ → E) (x : E) (hx : Tendsto (fun n ↦ toWeakSpace ℝ E (xₙ n)) atTop (𝓝 (toWeakSpace ℝ E x))) : ∃ y : ℕ → E, (∀ n, y n ∈ convexHull ℝ (Set.range fun k : Fin (n + 1) ↦ xₙ k)) ∧ Tendsto y atTop (𝓝 x)

Theorem 3.37

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Theorem 3.37: a nonempty bounded closed convex subset of a real Hilbert space is weakly compact. The weak topology is expressed by viewing the set inside WeakSpace ℝ H.

open scoped InnerProductSpace universe u variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] -- Proof sketch: a Hilbert space is reflexive, so closed bounded sets are weakly compact after -- passing to the weak topology. A norm-closed convex subset is weakly closed, hence a weakly -- closed subset of a weakly compact closed ball and therefore weakly compact. theorem weaklyCompact_of_nonempty_bounded_closed_convex {C : Set H} (_hCne : C.Nonempty) (hCbdd : Bornology.IsBounded C) (hCclosed : IsClosed C) (hCconv : Convex ℝ C) : IsCompact (toWeakSpace ℝ H '' C)

Corollary 3.38

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Corollary 3.38: every sequence with values in a bounded closed convex subset of a real Hilbert space admits a weakly convergent subsequence whose weak limit belongs to the set.

open Filter universe u variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] theorem exists_subsequence_tendsto_weakly_mem_of_bounded_isClosed_convex {C : Set H} (hC_bounded : Bornology.IsBounded C) (hC_closed : IsClosed C) (hC_convex : Convex ℝ C) (u : ℕ → H) (hu : ∀ n, u n ∈ C) : ∃ x ∈ C, ∃ φ : ℕ → ℕ, StrictMono φ ∧ Tendsto (fun n ↦ toWeakSpace ℝ H (u (φ n))) atTop (nhds (toWeakSpace ℝ H x))

Proposition 3.39

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Proposition 3.39 (1): the convex hull of a finite family of compact convex subsets of a real topological vector space, hence in particular of a real Hilbert space, is compact.

open scoped InnerProductSpace universe u variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] theorem isCompact_convexHull_iUnion_fin {ι : Type*} [Finite ι] {E : Type*} [AddCommGroup E] [Module ℝ E] [TopologicalSpace E] [IsTopologicalAddGroup E] [ContinuousSMul ℝ E] (C : ι → Set E) (hconv : ∀ i, Convex ℝ (C i)) (hcompact : ∀ i, IsCompact (C i)) : IsCompact (convexHull ℝ (⋃ i, C i) : Set E)

Example 3.40

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Example 3.40: for C = ℝ × {0} and D = {(ξ₁, ξ₂) ∈ ℝ² | 0 ≤ ξ₁ ∧ 0 ≤ ξ₂ ∧ 1 ≤ ξ₁ * ξ₂}, the Minkowski sum is the open upper half-plane ℝ × ℝ_{++}, i.e. Set.univ ×ˢ Set.Ioi (0 : ℝ).

open scoped Pointwise theorem minkowskiCounterexample_sum_eq_upperHalfPlane : minkowskiCounterexample_horizontalAxis + minkowskiCounterexample_positiveProductRegion = Set.univ ×ˢ Set.Ioi (0 : ℝ)

Example 3.41

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Example 3.41 (1): the closed span of the even-indexed vectors is a closed linear subspace.

open scoped Topology InnerProductSpace universe u variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] theorem isClosed_even_indexed_closed_span (e : ℕ → 𝓗) : IsClosed ((even_indexed_closed_span e : Submodule ℝ 𝓗) : Set 𝓗)

Proposition 3.42

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Proposition 3.42 (1): the Minkowski sum of two nonempty subsets is nonempty, canonically formalized by Set.Nonempty.add.

open Filter open scoped InnerProductSpace open scoped Pointwise open scoped Topology universe u variable {E : Type u} [NormedAddCommGroup E] recall Set.Nonempty.add

Proposition 3.44

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Proposition 3.44, pointwise form: if C is convex, x ∈ interior C, y ∈ closure C, and t ∈ [0,1), then the point lineMap x y t lies in interior C.

open Set AffineMap universe u variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] theorem lineMap_mem_interior_of_mem_Ico_of_mem_interior_of_mem_closure {C : Set E} (hC : Convex ℝ C) {x y : E} (hx : x ∈ interior C) (hy : y ∈ closure C) {t : ℝ} (ht : t ∈ Ico (0 : ℝ) 1) : lineMap x y t ∈ interior C

Proposition 3.45

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Proposition 3.45 (1): the closure of a convex subset of a real topological vector space is convex.

universe u variable {E : Type u} variable [TopologicalSpace E] [AddCommGroup E] [Module ℝ E] [IsTopologicalAddGroup E] [ContinuousConstSMul ℝ E] theorem convex_closure_of_convex {C : Set E} (hC : Convex ℝ C) : Convex ℝ (closure C)

Proposition 3.46

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Proposition 3.46 (1): the convex hull of the closure of a subset of a real normed space is contained in the closure of its convex hull.

universe u variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] -- Proof sketch: `convexHull ℝ (closure C)` lies in the closed convex hull of `closure C`, and the -- closed convex hull is unchanged by taking closure. The standard closed-convex-hull identity then -- identifies the target with `closure (convexHull ℝ C)`. theorem convexHull_closure_subset_closure_convexHull (C : Set E) : convexHull ℝ (closure C) ⊆ closure (convexHull ℝ C)

Example 3.47

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Example 3.47: for the closed set C = {(x, r) ∈ ℝ² | 1 / (1 + |x|) ≤ r}, one has convexHull ℝ (closure C) ≠ closure (convexHull ℝ C).

open ERealFunction theorem convexHull_closure_ne_closure_convexHull_of_epigraph_inv_one_add_abs : convexHull ℝ (closure epigraph_inv_one_add_abs) ≠ closure (convexHull ℝ epigraph_inv_one_add_abs)

Proposition 3.48

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Proposition 3.48: if C and D are convex subsets of a real topological vector space, C is closed, and C ∩ interior D is nonempty, then the closure of C ∩ interior D is C ∩ closure D.

universe u variable {E : Type u} [TopologicalSpace E] [AddCommGroup E] [Module ℝ E] [IsTopologicalAddGroup E] [ContinuousSMul ℝ E] theorem closure_inter_interior_eq_inter_closure_of_nonempty {C D : Set E} (hC_conv : Convex ℝ C) (hD_conv : Convex ℝ D) (hC_closed : IsClosed C) (h_nonempty : (C ∩ interior D).Nonempty) : closure (C ∩ interior D) = C ∩ closure D

Definition 3.49

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Definition 3.49: subsets C and D of a real Hilbert space are separated when some nonzero vector u satisfies sup_{c ∈ C} ⟪c, u⟫ ≤ inf_{d ∈ D} ⟪d, u⟫; strong separation and point-from-set separation are obtained by replacing ≤ with < and by taking C = {x}.

universe u open scoped InnerProductSpace variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] def AreSeparated (C D : Set 𝓗) : Prop := ∃ u : 𝓗, u ≠ 0 ∧ innerSupremumOn C u ≤ innerInfimumOn D u -- Proof sketch: unfold `AreSeparated`.

Theorem 3.50

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Theorem 3.50: a point outside a nonempty closed convex set is strongly separated from that set in the orientation used by AreStronglySeparated C ({x} : Set 𝓗).

universe u open scoped InnerProductSpace variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] [CompleteSpace 𝓗] variable {C : Set 𝓗} variable (hC_nonempty : C.Nonempty) (hC_closed : IsClosed C) (hC_convex : Convex ℝ C) local notation "P" => projectionPoint C (isChebyshev_of_nonempty_isClosed_convex hC_nonempty hC_closed hC_convex) theorem areStronglySeparated_singleton_of_nonempty_isClosed_convex_of_not_mem {C : Set 𝓗} (hC_nonempty : C.Nonempty) (hC_closed : IsClosed C) (hC_convex : Convex ℝ C) {x : 𝓗} (hx : x ∉ C) : AreStronglySeparated C ({x} : Set 𝓗)

Corollary 3.51

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Corollary 3.51: if nonempty subsets C and D of a real Hilbert space are disjoint and their Minkowski difference C - D is closed and convex, then C and D are strongly separated.

open scoped InnerProductSpace Pointwise universe u variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] [CompleteSpace 𝓗] theorem areStronglySeparated_of_disjoint_of_isClosed_of_convex_sub {C D : Set 𝓗} (hC : C.Nonempty) (hD : D.Nonempty) (hCD : Disjoint C D) (hclosed : IsClosed (C - D)) (hconvex : Convex ℝ (C - D)) : AreStronglySeparated C D

Corollary 3.52

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Corollary 3.52: two nonempty closed convex disjoint subsets of a real Hilbert space are strongly separated whenever the second set is bounded.

open scoped InnerProductSpace Pointwise universe u variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] [CompleteSpace 𝓗] theorem areStronglySeparated_of_nonempty_isClosed_convex_disjoint_bounded {C D : Set 𝓗} (hC_nonempty : C.Nonempty) (hC_closed : IsClosed C) (hC_convex : Convex ℝ C) (hD_nonempty : D.Nonempty) (hD_closed : IsClosed D) (hD_convex : Convex ℝ D) (hCD : Disjoint C D) (hD_bounded : Bornology.IsBounded D) : AreStronglySeparated C D

Theorem 3.53

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Theorem 3.53: in a finite-dimensional real Hilbert space, two nonempty closed convex sets with empty intersection are separated in the sense of AreSeparated.

open scoped InnerProductSpace open Filter universe u variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] [FiniteDimensional ℝ 𝓗] theorem finiteDimensional_closed_convex_areSeparated_of_disjoint {C D : Set 𝓗} (hC_nonempty : C.Nonempty) (hC_closed : IsClosed C) (hC_convex : Convex ℝ C) (hD_nonempty : D.Nonempty) (hD_closed : IsClosed D) (hD_convex : Convex ℝ D) (hCD : Disjoint C D) : AreSeparated C D

Proposition 3.54

Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.

Source header · Attribution source

Proposition 3.54: an infinite-dimensional real Hilbert space contains disjoint closed affine subspaces that are not separated.

open scoped Pointwise InnerProductSpace universe u variable {𝓗 : Type u} [NormedAddCommGroup 𝓗] [InnerProductSpace ℝ 𝓗] [CompleteSpace 𝓗] theorem exists_disjoint_closed_affineSubspaces_not_separated (hinfdim : ¬ FiniteDimensional ℝ 𝓗) : ∃ U V : AffineSubspace ℝ 𝓗, IsClosed (U : Set 𝓗) ∧ IsClosed (V : Set 𝓗) ∧ Disjoint (U : Set 𝓗) (V : Set 𝓗) ∧ ¬ AreSeparated (U : Set 𝓗) (V : Set 𝓗)