The geometry of l1 versus l2 constraints

ProofIntermediate⏱ 30 minHigh-Dim Statisticslassogeometrysparsityconvex envelope

Problem

Describe the extreme points of the $\ell^1$ ball $\{x:\|x\|_1\le t\}$ in $\R^p$ and of the $\ell^2$ ball.
Explain, using the fact that a linear functional over a compact convex set attains its maximum at an extreme point, why $\ell^1$ -constrained problems produce sparse solutions and $\ell^2$ -constrained ones do not.
Show that $\|x\|_1$ is the convex envelope of $\|x\|_0$ on the unit $\ell^\infty$ ball, i.e. the largest convex function below it there.

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

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

Problem	Field	Type	Difficulty	Time
The geometric margin	Classical ML	Proof	Foundation	15 min
Derive the soft-thresholding operator	High-Dim Statistics	Proof	Intermediate	30 min
Covering numbers of the set of sparse unit vectors	High-Dim Probability	Proof	Advanced	1 hour
Gaussian width of the sphere and of the sparse set	High-Dim Probability	Proof	Advanced	30 min
Implement ISTA and verify the lasso rate run	High-Dim Statistics	Coding	Advanced	3 hours