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.
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.
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.
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]).asERealExample 12.4
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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.asERealDefinition 12.5
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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.
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 gExample 12.7
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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.
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.
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.univRemark 12.10
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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.
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.
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.
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.
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 HProposition 12.15
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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.
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.
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.
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.asERealCorollary 12.19
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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 = hDefinition 12.20
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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.
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).toERealExample 12.21
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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.
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) • {}^[(γ * μ)] fDefinition 12.23
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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.
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.
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.
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.
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.
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.
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.asERealProposition 12.30
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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)) xCorollary 12.31
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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)) xProposition 12.32
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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.
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.
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 infimalPostcompositionExample 12.35
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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).toERealProposition 12.36
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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 fProposition 12.37
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
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.
-
ProximityOperator.lean(Documentation) (Lean source)
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
-
ScaledProximityOperator.lean(Documentation) (Lean source)
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.