Convex Optimization · Problem 6.4

Statistical estimation — Boyd & Vandenberghe

Mathematics — Optimization · differentiable-approximation-l1-norm

Problem

A differentiable approximation of ℓ1\ell_1-norm approximation. The function ϕ(u)=(u2+ϵ)1/2\phi(u) = (u^2 + \epsilon)^{1/2}, with parameter ϵ>0\epsilon > 0, is sometimes used as a differentiable approximation of the absolute value function ∣u∣|u|. To approximately solve the ℓ1\ell_1-norm approximation problem minimize∥Ax−b∥1,(6.26)\text{minimize} \quad \|Ax - b\|_1, \tag{6.26} where A∈Rm×nA \in \mathbf{R}^{m \times n}, we solve instead the problem minimize∑i=1mϕ(aiTx−bi),(6.27)\text{minimize} \quad \sum_{i=1}^m \phi(a_i^T x - b_i), \tag{6.27} where aiTa_i^T is the iith row of AA. We assume rank A=n\mathbf{rank}\, A = n. Let p⋆p^\star denote the optimal value of the ℓ1\ell_1-norm approximation problem (6.26). Let x^\hat{x} denote the optimal solution of the approximate problem (6.27), and let r^\hat{r} denote the associated residual, r^=Ax^−b\hat{r} = A\hat{x} - b. (a) Show that p⋆≥∑i=1mr^i2/(r^i2+ϵ)1/2p^\star \geq \sum_{i=1}^m \hat{r}_i^2 / (\hat{r}_i^2 + \epsilon)^{1/2}. (b) Show that ∥Ax^−b∥1≤p⋆+∑i=1m∣r^i∣(1−∣r^i∣(r^i2+ϵ)1/2).\|A\hat{x} - b\|_1 \leq p^\star + \sum_{i=1}^m |\hat{r}_i| \left(1 - \frac{|\hat{r}_i|}{(\hat{r}_i^2 + \epsilon)^{1/2}}\right). (By evaluating the righthand side after computing x^\hat{x}, we obtain a bound on how suboptimal x^\hat{x} is for the ℓ1\ell_1-norm approximation problem.)
Intuitive explanation

The key insight is that ϕ(u)\phi(u) smoothly approximates ∣u∣|u| from below, and this gap between the smooth approximation and the true absolute value creates both a lower bound on the original problem and an upper bound on the suboptimality of the approximate solution. At optimality of the smooth problem, the gradient condition tells us something useful about the residuals r^i\hat{r}_i; you'll use the relationship between ϕ(r^i)\phi(\hat{r}_i) and ∣r^i∣|\hat{r}_i| to bound how far the approximate solution is from the true ℓ1\ell_1 optimum. The error bound in part (b) quantifies exactly where the approximation "loses" optimality—in the difference between ∣r^i∣|\hat{r}_i| and its smooth proxy.

Intuitive explanation

The key insight is that ϕ(u)\phi(u) smoothly approximates ∣u∣|u| from below, and this gap between the smooth approximation and the true absolute value creates both a lower bound on the original problem and an upper bound on the suboptimality of the approximate solution. At optimality of the smooth problem, the gradient condition tells us something useful about the residuals r^i\hat{r}_i; you'll use the relationship between ϕ(r^i)\phi(\hat{r}_i) and ∣r^i∣|\hat{r}_i| to bound how far the approximate solution is from the true ℓ1\ell_1 optimum. The error bound in part (b) quantifies exactly where the approximation "loses" optimality—in the difference between ∣r^i∣|\hat{r}_i| and its smooth proxy.

Related theory

Browse the problem library