Chapter 12 — Infimal Convolution

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

Definition 12.1

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

Source header · Attribution source

Definition 12.1 (1): the infimal convolution of two ]-∞,+∞]-valued functions.

universe u namespace ERealFunction variable {H : Type u} [AddGroup H] noncomputable def infimalConvolution (f g : H → EReal) : H → EReal := fun x ↦ ⨅ y : H, f y + g (x - y)

Example 12.2

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

Source header · Attribution source

Example 12.2: the distance to C is the infimal convolution of the indicator of C with the norm.

universe u open Set open ERealFunction variable {H : Type u} [NormedAddCommGroup H] namespace ERealFunction -- Proof sketch: compare the source-faithful `EReal` infimum over `C` with the canonical -- extended distance `Metric.infEDist`. theorem distanceToSet_eq_indicator_infimalConvolution_norm (C : Set H) : (fun x ↦ (Metric.infEDist x C : EReal)) = ι[C] □ scaledNormKernel (1 : NNReal)

Example 12.3

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

Source header · Attribution source

Example 12.3: the infimal convolution of the extended-real indicators of C and D is the indicator of the Minkowski sum C + D.

universe u open Set open scoped Pointwise variable {H : Type u} [AddCommGroup H] namespace ERealFunction -- Proof sketch: if `x ∈ C + D`, choose a decomposition `x = c + d` with `c ∈ C` and `d ∈ D`, so -- one admissible infimal-convolution value is `0`; if `x ∉ C + D`, every decomposition has either -- `y ∉ C` or `z ∉ D`, forcing the summand to be `⊤`, hence the infimum is `⊤`. theorem indicator_infimalConvolution_eq_indicator_add (C D : Set H) : infimalConvolution (fun x ↦ (ι[C] x : EReal)) (fun x ↦ (ι[D] x : EReal)) = (ι[C + D]).asEReal

Example 12.4

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

Source header · Attribution source

Example 12.4: the infimal convolution of the singleton indicator at y with f is the translate of f by y.

open scoped translate open ERealFunction universe u namespace ERealFunction variable {H : Type u} [AddCommGroup H] -- Proof sketch: unfold the defining infimum for `ι[{y}] □ f`. The singleton indicator is `0` -- exactly at `y` and `⊤` elsewhere, so the only finite contribution comes from the decomposition -- using `y`, yielding the translate of the canonical `EReal` view `f.asEReal`. theorem indicator_singleton_infimalConvolution_eq_translate (f : H → Set.Ioi (⊥ : EReal)) (y : H) : infimalConvolution (ι[{y}]).asEReal f.asEReal = τ y f.asEReal

Definition 12.5

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

Source header · Attribution source

Definition 12.5: f has a continuous affine minorant with slope u if it dominates a function of the form x ↦ ⟪x, u⟫ + η.

open scoped InnerProductSpace universe u namespace ERealFunction variable {H : Type u} [Inner ℝ H] def HasContinuousAffineMinorantWithSlope (f : H → EReal) (u : H) : Prop := ∃ η : ℝ, ∀ x : H, (((⟪x, u⟫_ℝ + η : ℝ) : EReal) ≤ f x) -- Proof sketch: expand `HasContinuousAffineMinorantWithSlope f u` using its defining real -- constant `η`, then rearrange the inequality `⟪x,u⟫ + η ≤ f x` into -- `η ≤ f x - ⟪x,u⟫`; the converse reverses the same algebra.

Proposition 12.6

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

Source header · Attribution source

Proposition 12.6 (ii): for extended-real-valued functions that never take the value -∞, the domain of the infimal convolution is the Minkowski sum of the domains.

open scoped Pointwise InnerProductSpace open ERealFunction universe u namespace ERealFunction variable {H : Type u} [AddGroup H] theorem dom_infimalConvolution (f g : H → Set.Ioi (⊥ : EReal)) : dom (f □ g) = effectiveDomain f + effectiveDomain g

Example 12.7

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

Source header · Attribution source

Example 12.7: for f(ξ) = ξ and g = -f on ℝ, the infimal convolution f □ g is identically -∞, so the conclusion of Proposition 12.6(i) can fail without the common-minorant hypothesis.

namespace ERealFunction theorem id_infimalConvolution_neg_id_eq_bot : infimalConvolution id.toEReal.asEReal (-id).toEReal.asEReal = (⊥ : ℝ → EReal)

Proposition 12.8

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

Source header · Attribution source

Proposition 12.8 (1): the pointwise sum of the real-height epigraphs of f and g is contained in the real-height epigraph of their infimal convolution.

open scoped Pointwise universe u namespace ERealFunction variable {H : Type u} [AddGroup H] variable (f g : H → Set.Ioi (⊥ : EReal)) -- Proof sketch: unpack membership in the pointwise sum of the two epigraphs, rewrite each -- epigraph condition with `mem_epigraph_iff`, and compare the defining infimum of `f □ g` with the -- single decomposition coming from the chosen summands. theorem add_epigraph_subset_epigraph_infimalConvolution : epigraph f.asEReal + epigraph g.asEReal ⊆ epigraph (f □ g)

Proposition 12.9

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

Source header · Attribution source

Proposition 12.9 (1): clause (i), the p-power envelope has full domain, equivalently it never attains the value +∞.

universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] theorem dom_normPowerEnvelope_eq_univ (f : H → Set.Ioi (⊥ : EReal)) (hdom : (effectiveDomain f).Nonempty) (p : Set.Ici (1 : ℝ)) (γ : Set.Ioi (0 : ℝ)) : dom (normPowerEnvelope f p γ) = Set.univ

Remark 12.10

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

Source header · Attribution source

Remark 12.10: the p-power envelope of a discontinuous real linear functional is identically -∞.

universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [NormedSpace ℝ H] theorem normPowerEnvelope_eq_bot_of_not_continuous_linearFunctional (f : H →ₗ[ℝ] ℝ) (hf : ¬ Continuous f) (p : Set.Ici (1 : ℝ)) (γ : Set.Ioi (0 : ℝ)) : normPowerEnvelope ((f : H → ℝ).toEReal) p γ = (⊥ : H → EReal)

Proposition 12.11

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

Source header · Attribution source

Proposition 12.11: if f and g are convex ]-∞,+∞]-valued functions, then the real-height epigraph of their infimal convolution is convex.

open Set universe u namespace ERealFunction variable {H : Type u} [AddCommGroup H] [Module ℝ H] theorem convex_epigraph_infimalConvolution (f g : H → Set.Ioi (⊥ : EReal)) (hf : ConvexOn f (effectiveDomain f)) (hg : ConvexOn g (effectiveDomain g)) : Convex ℝ (epigraph (infimalConvolution f.asEReal g.asEReal))

Corollary 12.12

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

Source header · Attribution source

Corollary 12.12: if C is convex, then the extended-real distance function d_C is convex on the ambient space.

universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [NormedSpace ℝ H] -- Proof sketch: use Example 12.2 to rewrite `fun x ↦ (Metric.infEDist x C : EReal)` as the -- infimal convolution of the indicator of `C` with the norm, observe from Example 8.3 and -- Example 8.9 that these two functions are convex when `C` is convex, and apply Proposition -- 12.11. theorem convex_epigraph_distanceToSet (C : Set H) (hC : Convex ℝ C) : Convex ℝ (epigraph (fun x ↦ (Metric.infEDist x C : EReal)))

Example 12.13

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

Source header · Attribution source

Example 12.13: the reciprocal barrier and its canonical Fenchel conjugate both belong to Γ₀(ℝ).

open Set open scoped Pointwise namespace ERealFunction theorem positiveReciprocalBarrier_and_conjugate_mem_gammaZero : reciprocalBarrier = (inversePowerIoiExtension 1).asEReal ∧ reciprocalBarrier∗ = (gammaZeroConjugate (inversePowerIoiExtension 1) (inversePowerIoiExtension_mem_gammaZero 1 le_rfl)).asEReal ∧ inversePowerIoiExtension 1 ∈ Γ₀(ℝ) ∧ gammaZeroConjugate (inversePowerIoiExtension 1) (inversePowerIoiExtension_mem_gammaZero 1 le_rfl) ∈ Γ₀(ℝ)

Proposition 12.14

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

Source header · Attribution source

Proposition 12.14: if f, g ∈ Γ₀(H) and either (i) f is supercoercive or (ii) f is coercive while g is bounded below, then the raw infimal convolution f □ g is proper, convex, and lower semicontinuous. In the project's owner-level API this is expressed as IsProper (f □ g) together with (f □ g) ∈ gamma H.

open scoped InnerProductSpace universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] variable (f g : H → Set.Ioi (⊥ : EReal)) variable (hf : f ∈ Γ₀(H)) (hg : g ∈ Γ₀(H)) -- Clause (ii) is kept in the source-facing bounded-below form; the zero-slope affine-minorant -- owner is only an internal bridge. variable (hcase : Supercoercive f.asEReal ∨ (Coercive f.asEReal ∧ ∃ η : ℝ, ∀ x : H, (η : EReal) ≤ g.asEReal x)) theorem isProper_and_mem_gamma_infimalConvolution_of_supercoercive_or_coercive_bddBelow : IsProper (f □ g) ∧ (f □ g) ∈ gamma H

Proposition 12.15

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

Source header · Attribution source

Proposition 12.15 (1): if f ∈ Γ₀(H), γ ∈ ℝ_{++}, and p > 1, then the real-valued representative of the p-power envelope is convex on H.

universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] variable (f : H → Set.Ioi (⊥ : EReal)) (γ : PosReal) (p : Set.Ici (1 : ℝ)) -- Proof sketch: specialize Proposition 12.14 to `normPowerKernel p γ`. This places -- `normPowerEnvelope f p γ` in `gamma H`; combine that with Proposition 12.9 (1), -- `dom (normPowerEnvelope f p γ) = Set.univ`, to rewrite convexity on the effective domain as -- convexity on all of `H` and then pass to `toReal`. theorem convexOn_univ_toReal_normPowerEnvelope_of_mem_gammaZero (hf : f ∈ Γ₀(H)) (hp : (1 : ℝ) < p) : _root_.ConvexOn ℝ Set.univ (fun x : H ↦ (normPowerEnvelope f p γ x).toReal)

Definition 12.16

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

Source header · Attribution source

Definition 12.16: the β-Pasch--Hausdorff envelope of f is the infimal convolution of f with the scaled norm x ↦ β ‖x‖.

universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] noncomputable def paschHausdorffEnvelope {α : Type*} [CoeTC α EReal] (f : H → α) (β : NNReal) : H → EReal := f □ scaledNormKernel β

Proposition 12.17

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

Source header · Attribution source

Proposition 12.17: for the β-Pasch--Hausdorff envelope of a proper ]-∞,+∞]-valued function, exactly one of the following holds: (i) the envelope is the greatest β-Lipschitz continuous minorant, or (ii) there is no β-Lipschitz continuous minorant and the envelope is identically -∞.

universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] -- Proof sketch: specialize the Pasch--Hausdorff envelope formula to the norm kernel -- `x ↦ β ‖x‖`. If `f` admits a `β`-Lipschitz minorant, compare that minorant with the defining -- infimum to show the envelope is real-valued, `β`-Lipschitz, and maximal among such minorants. -- If no such minorant exists, any finite envelope value would itself produce one, so the envelope -- must be identically `-∞`. The hypothesis `hf` is the properness assumption specialized to -- `f : H → ]-∞,+∞]`, where only the existence of a finite point remains nonredundant. theorem paschHausdorffEnvelope_greatestBetaLipschitzMinorant_or_eq_bot (f : H → Set.Ioi (⊥ : EReal)) (β : NNReal) (hf : ∃ x : H, (f x : EReal) < ⊤) : Xor' (∃ h : H → ℝ, paschHausdorffEnvelope f β = h.toEReal.asEReal ∧ IsGreatest (betaLipschitzMinorants f β) h) (¬ (betaLipschitzMinorants f β).Nonempty ∧ paschHausdorffEnvelope f β = (⊥ : H → EReal))

Corollary 12.18

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

Source header · Attribution source

Corollary 12.18: a real-valued β-Lipschitz function coincides with its own β-Pasch--Hausdorff envelope.

universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] theorem paschHausdorffEnvelope_eq_self_of_lipschitz (f : H → ℝ) (β : NNReal) (hf : LipschitzWith β f) : paschHausdorffEnvelope f β = f.toEReal.asEReal

Corollary 12.19

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

Source header · Attribution source

Corollary 12.19: if h : C → ℝ is β-Lipschitz, then the Pasch--Hausdorff envelope of the function equal to h on C and +∞ outside C is realized by a real-valued β-Lipschitz extension of h.

universe u namespace ERealFunction variable {H : Type u} variable [NormedAddCommGroup H] theorem paschHausdorffEnvelope_realizes_lipschitz_extension (C : Set H) (hC : C.Nonempty) (β : NNReal) (h : C → ℝ) (hh : LipschitzWith β h) : ∃ g : H → ℝ, paschHausdorffEnvelope (extendWithTopOutside C h) β = g.toEReal.asEReal ∧ LipschitzWith β g ∧ g ∘ Subtype.val = h

Definition 12.20

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

Source header · Attribution source

Definition 12.20: the Moreau envelope of parameter γ ∈ ℝ_{++} is the infimal convolution of f with the quadratic kernel x ↦ (1 / (2γ)) ‖x‖^2. The source-facing Lean notation is {}^[γ] f.

universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] noncomputable abbrev moreauEnvelope {α : Type*} [CoeTC α EReal] (f : H → α) (γ : Set.Ioi (0 : ℝ)) : H → EReal := f □ moreauQuadraticKernel γ

Definition 12.20.Core

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

Source header · Attribution source

The quadratic kernel x ↦ (1 / (2γ)) ‖x‖^2 used in the definition of the Moreau envelope.

universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] noncomputable def moreauQuadraticKernel (γ : Set.Ioi (0 : ℝ)) : H → Set.Ioi (⊥ : EReal) := (fun x : H ↦ (1 / (2 * (γ : ℝ))) * ‖x‖ ^ 2).toEReal

Example 12.21

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

Source header · Attribution source

Example 12.21: the γ-Moreau envelope of the indicator ι[C] is the scaled squared extended-distance function x ↦ d(x, C)^2 / (2γ), with value ⊤ when C = ∅.

universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] theorem indicator_moreauEnvelope_eq_scaled_sq_infEDist (C : Set H) (γ : Set.Ioi (0 : ℝ)) : {}^[γ] ι[C] = fun x : H ↦ (Metric.infEDist x C : EReal) ^ 2 / (2 * (γ : ℝ) : EReal)

Proposition 12.22

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

Source header · Attribution source

Proposition 12.22 (1): clause (i), scaling f by the positive real γ scales its μ-Moreau envelope, with the envelope parameter changing from μ to γμ.

universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] -- Proof sketch: unfold `moreauEnvelope_apply`, factor the positive scalar `γ` out of the defining -- infimum, and rewrite the quadratic coefficient `1 / (2 * μ)` as `γ / (2 * (γ * μ))`. theorem moreauEnvelope_smul_eq_smul_moreauEnvelope (f : H → Set.Ioi (⊥ : EReal)) (γ μ : PosReal) : {}^[μ] (γ • f) = (γ : EReal) • {}^[(γ * μ)] f

Definition 12.23

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

Source header · Attribution source

Definition 12.23: the proximal points of f at x are the minimizers of the regularized objective y ↦ f y + (1 / 2) ‖x - y‖^2.

universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] def proximalPoints (f : H → Set.Ioi (⊥ : EReal)) (x : H) : Set H := Argmin (proximalObjective f x)

Remark 12.24

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

Source header · Attribution source

Remark 12.24: equation (12.24) states that for f ∈ Γ₀(H), γ ∈ ℝ_{++}, and x ∈ H, the γ-Moreau envelope equals f (Prox_{γ f} x) plus the quadratic term ‖x - Prox_{γ f} x‖² / (2γ).

universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] -- Proof sketch: apply Proposition 12.22(i) with `μ = 1` to rewrite `{}¹(γ f)` as -- `γ ({}^γ f)`, then combine this with the proximal-point formula from Definition 12.23 for the -- scaled function `γ f` and simplify the quadratic coefficient. theorem moreauEnvelope_eq_proxValue_add_scaled_sqDist_of_mem_gammaZero (f : H → Set.Ioi (⊥ : EReal)) (hf : f ∈ Γ₀(H)) (γ : PosReal) (x : H) : ({}^[γ] f) x = (f (Prox[γ, f, hf] x) : EReal) + ((((‖x - Prox[γ, f, hf] x‖ ^ 2) / (2 * (γ : ℝ)) : ℝ) : EReal))

Example 12.25

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

Source header · Attribution source

Example 12.25: for a nonempty closed convex subset C of a real Hilbert space, the proximity operator of the indicator ι_C is the metric projection P_C.

universe u open scoped InnerProductSpace namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] variable {C : Set H} -- Proof sketch: closed convex subsets of a complete real Hilbert space are Chebyshev by -- `isChebyshev_of_nonempty_isClosed_convex`; apply `hasUniqueProxPoint_indicator`. theorem proximityOperator_indicator_eq_projectionPoint_of_nonempty_isClosed_convex (hC_nonempty : C.Nonempty) (hC_closed : IsClosed C) (hC_convex : Convex ℝ C) : proximityOperator (ι[C]) (hasUniqueProxPoint_indicator_of_nonempty_isClosed_convex hC_nonempty hC_closed hC_convex) = projectionPoint C (isChebyshev_of_nonempty_isClosed_convex hC_nonempty hC_closed hC_convex)

Proposition 12.26

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

Source header · Attribution source

Proposition 12.26: if f is convex on its effective domain (in particular if f ∈ Γ₀(H)), then a point p is a proximal point of f at x exactly when it satisfies the textbook variational inequality (12.25), ⟪y - p, x - p⟫ + f(p) ≤ f(y) for every y ∈ H.

universe u open scoped InnerProductSpace namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] -- Proof sketch: use the primitive convexity hypothesis on `effectiveDomain f`, unfold -- `IsProxPoint` through the canonical owner `Argmin` of `proximalObjective f x`, rewrite the -- resulting minimizer condition as the corresponding pointwise inequality, and expand the -- quadratic term on both sides. theorem isProxPoint_iff_forall_inner_add_le (f : H → Set.Ioi (⊥ : EReal)) (hconv : ConvexOn f (effectiveDomain f)) (x p : H) : IsProxPoint f x p ↔ ∀ y, (⟪y - p, x - p⟫_ℝ : EReal) + (f p : EReal) ≤ (f y : EReal)

Proposition 12.27

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

Source header · Attribution source

Proposition 12.27 (1): for f ∈ Γ₀(H) and x ∈ H, the proximal value function γ ↦ f (Prox_{γ f} x) is decreasing on ℝ_{++}.

universe u open scoped InnerProductSpace namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] -- Proof sketch: the scaled proximity operator is the ordinary proximity operator of `γ • f`; a -- proximal point of a proper function cannot have value `⊤`, since the proximal objective would -- then be `⊤` and hence could not attain the finite minimum value guaranteed by properness. theorem antitone_proxValue_along_parameter_of_mem_gammaZero (f : H → Set.Ioi (⊥ : EReal)) (hf : f ∈ Γ₀(H)) (x : H) : Antitone (fun γ : PosReal ↦ (f (Prox[γ, f, hf] x) : EReal).toReal)

Proposition 12.28

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

Source header · Attribution source

Proposition 12.28 (1): for f ∈ Γ₀(H), the proximity operator Prox_f is firmly nonexpansive.

open SubtypeFirmness -- Declarations for this item will be appended below by the statement pipeline. universe u open scoped InnerProductSpace namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] variable (f : H → Set.Ioi (⊥ : EReal)) -- Proof sketch: apply Proposition 12.26 at the proximal points of `x` and `y`, add the two -- resulting variational inequalities, and rewrite the conclusion with the whole-space criterion -- for firm nonexpansiveness. theorem proximityOperator_firmlyNonexpansive_of_mem_gammaZero (hf : f ∈ Γ₀(H)) : FirmlyNonexpansive (Prox[f, hf])

Proposition 12.29

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

Source header · Attribution source

Proposition 12.29: for f ∈ Γ₀(H), the fixed points of the proximity operator Prox_f coincide with the global minimizers of f.

universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] -- Proof sketch: use Proposition 12.26 to rewrite `x = Prox_f x` as the variational inequality -- `∀ y, f x ≤ f y`, since the inner-product term vanishes at a fixed point. Then identify the -- latter condition with membership in `Argmin`. theorem fixedPoints_proximityOperator_eq_argmin_of_mem_gammaZero (f : H → Set.Ioi (⊥ : EReal)) (hf : f ∈ Γ₀(H)) : Function.fixedPoints (Prox[f, hf]) = Argmin f.asEReal

Proposition 12.30

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

Source header · Attribution source

Proposition 12.30: for f ∈ Γ₀(H) and γ ∈ ℝ_{++}, the γ-Moreau envelope, viewed as the real-valued function x ↦ ({}^γ f x).toReal, is Fréchet differentiable at every point with gradient γ⁻¹ • (x - Prox_{γ f} x).

open scoped Gradient InnerProductSpace universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] variable (f : H → Set.Ioi (⊥ : EReal)) (γ : PosReal) -- Proof sketch: combine the pointwise envelope identity from Proposition 12.26 with the firm -- nonexpansiveness of the residual map from Proposition 12.28 to identify the first-order term -- with `γ⁻¹ • (x - Prox_{γ f} x)`. theorem moreauEnvelope_toReal_hasGradientAt_of_mem_gammaZero (hf : f ∈ Γ₀(H)) (x : H) : HasGradientAt (fun y : H ↦ (({}^[γ] f) y).toReal) ((γ : ℝ)⁻¹ • (x - Prox[γ, f, hf] x)) x

Corollary 12.31

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

Source header · Attribution source

Corollary 12.31: if C is a nonempty closed convex subset of a real Hilbert space, then the squared distance function x ↦ Metric.infDist x C ^ 2 is Fréchet differentiable at every point, with gradient 2 • (x - P_C x).

open scoped Gradient InnerProductSpace open ERealFunction universe u variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] variable {C : Set H} 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 sq_infDist_hasGradientAt_of_nonempty_isClosed_convex (x : H) : HasGradientAt (fun y : H ↦ Metric.infDist y C ^ 2) ((2 : ℝ) • (x - P x)) x

Proposition 12.32

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

Source header · Attribution source

Proposition 12.32 (1): for a nonempty closed convex cone K in a real Hilbert space, the gradients of q ∘ P_K and (1 / 2) d_{Kᵒ⊖}^2 agree.

open scoped Gradient InnerProductSpace Pointwise Set universe u variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] variable {K : Set H} variable (hK_nonempty : K.Nonempty) (hK_closed : IsClosed K) variable (hK_convex : Convex ℝ K) local notation "Pₖ" => projectionPoint K (isChebyshev_K hK_nonempty hK_closed hK_convex) local notation "Pᵒ⊖" => projectionPoint (Kᵒ⊖ : Set H) (isChebyshev_polarCone hK_nonempty hK_closed hK_convex) theorem gradient_half_norm_sq_projectionPoint_eq_gradient_half_sq_infDist_polarCone (hK_cone : IsCone K) : ∇ (fun x : H ↦ (1 / 2 : ℝ) * ‖Pₖ x‖ ^ 2) = ∇ (fun x : H ↦ (1 / 2 : ℝ) * Metric.infDist x (Kᵒ⊖) ^ 2)

Proposition 12.33

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

Source header · Attribution source

Proposition 12.33 (1): for f : H → ]-∞,+∞] and x ∈ H, the Moreau-envelope net γ ↦ ({}^[γ] f) x is decreasing on ℝ_{++}.

universe u namespace ERealFunction variable {H : Type u} [NormedAddCommGroup H] theorem antitone_moreauEnvelope_along_parameter (f : H → Set.Ioi (⊥ : EReal)) (x : H) : Antitone (fun γ : PosReal ↦ ({}^[γ] f) x)

Definition 12.34

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

Source header · Attribution source

Definition 12.34: the infimal postcomposition of a function f by a map L is the canonical owner infimalPostcomposition, written L ▷ f.

open Set universe u v namespace ERealFunction variable {H : Type u} {K : Type v} infixr:70 " ▷ " => fun L f y ↦ ERealFunction.infimalPostcomposition L (fun x ↦ (f x : EReal)) y recall infimalPostcomposition

Example 12.35

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

Source header · Attribution source

Example 12.35: on a finite coordinate ℓ^p space with 1 ≤ p < ∞, the latent group lasso penalty is the infimal postcomposition of the source-facing real-valued cost x ↦ ∑ k, ‖x_k‖_p by the synthesis map (x_k) ↦ ∑ k, x_k. The textbook ℝ^N case is recovered by taking ι = Fin N and E = ℝ. The nonemptiness and covering hypotheses on the groups enter later analytic properties, not this defining infimal-postcomposition construction.

open scoped BigOperators namespace ERealFunction variable {ι κ : Type*} [Fintype ι] [Fintype κ] variable {E : Type*} [NormedAddCommGroup E] variable {p : ENNReal} open latentGroupLassoDecompositionSpace noncomputable def latentGroupLassoPenalty (p : TextbookExponent) (groups : κ → Set ι) : PiLp p.1 (fun _ : ι ↦ E) → EReal := synthesis E p.1 groups ▷ (cost E p groups).toEReal

Proposition 12.36

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

Source header · Attribution source

Proposition 12.36 (1): the effective domain of the infimal postcomposition is the image under L of the effective domain of f.

open Set universe u v namespace ERealFunction variable {H : Type u} {K : Type v} theorem dom_infimalPostcomposition (L : H → K) (f : H → Set.Ioi (⊥ : EReal)) : dom (L ▷ f) = L '' effectiveDomain f

Proposition 12.37

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

Source header · Attribution source

Proposition 12.37: infimal convolution is the infimal postcomposition of the separable sum (y, z) ↦ f y + g z by the product-sum map (y, z) ↦ y + z.

universe u namespace ERealFunction variable {H : Type u} [AddCommGroup H] -- Proof sketch: `f ⊕ g` is the project owner for the separable sum `(y, z) ↦ f y + g z`, and -- `Prod.fst + Prod.snd` is the canonical product-sum map. -- The fiber over `x` is parameterized by `y ↦ (y, x - y)`, so the defining `sInf` is exactly the -- infimum in the infimal-convolution formula. theorem infimalConvolution_eq_infimalPostcomposition_separableSum (f g : H → Set.Ioi (⊥ : EReal)) : infimalConvolution f.asEReal g.asEReal = (Prod.fst + Prod.snd) ▷ (f ⊕ g)

Supporting modules

These source modules support the indexed items and are listed separately so the chapter inventory remains complete.

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

Source header · Attribution source

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

Source header · Attribution source