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.
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.
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_iInterProposition 3.4
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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_eqProposition 3.5
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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_imageProposition 3.6
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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_sumProposition 3.7
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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.
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 CExample 3.9
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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.
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 iRemark 3.11.1
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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 CRemark 3.11.2
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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.
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.
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.
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 CCorollary 3.15
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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 CProposition 3.15.1
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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 CProposition 3.15.2
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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 CTheorem 3.16.1
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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 CTheorem 3.16.2
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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⟫_ℝ ≤ 0Proposition 3.19
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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.
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).NonemptyProposition 3.21
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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) xCorollary 3.22
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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⟫_ℝ = 0Example 3.23
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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) • uCorollary 3.24
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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.
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.
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.
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.
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)
0Definition 3.28
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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.
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.
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.
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.
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) = TExample 3.33
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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.
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.
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 ∈ CCorollary 3.36
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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.
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.
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.
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.
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.
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.
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.addProposition 3.44
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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 CProposition 3.45
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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.
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.
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.
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 DDefinition 3.49
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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.
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.
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 DCorollary 3.52
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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 DTheorem 3.53
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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 DProposition 3.54
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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 𝓗)