The proximal operator of the l1 norm

ProofBeginner⏱ 15 minAdvanced Optimizationproximalsoft thresholdseparability

Theory: Projected, Proximal and Constrained First-Order Methods →

Problem

Show that $\prox_{\eta\|\cdot\|_1}(v)$ is coordinatewise soft thresholding, and verify it is firmly non-expansive: $\|\prox(u)-\prox(v)\|_2\le\|u-v\|_2$ .

Write a complete argument. Every inequality you use should be one you could state precisely.

Solution

Opening this before you have a real attempt on paper is the fastest way to feel like you understand something you cannot reproduce.

Related problems

All problems

Problem	Field	Type	Difficulty	Time
XOR is not linearly separable	Deep Learning	Proof	Foundation	15 min
Derive the soft-thresholding operator	High-Dim Statistics	Proof	Intermediate	30 min
Logistic regression diverges on separable data	Classical ML	Proof	Intermediate	30 min
The Frank–Wolfe duality gap certificate	Advanced Optimization	Proof	Intermediate	30 min
Projection onto the probability simplex	Advanced Optimization	Proof	Advanced	1 hour