Convex Optimization · Problem 6.5

Statistical estimation — Boyd & Vandenberghe

Mathematics — Optimization · minimum-length-approximation

Problem

Minimum length approximation. Consider the problem

\begin{aligned} \text{minimize} & \quad \text{length}(x) \\ \text{subject to} & \quad \|Ax - b\| \leq \epsilon, \end{aligned}

where

\text{length}(x) = \min\{k \mid x_i = 0 \text{ for } i > k\}

. The problem variable is

x \in \mathbf{R}^n

; the problem parameters are

A \in \mathbf{R}^{m \times n}

b \in \mathbf{R}^m

, and

\epsilon > 0

. In a regression context, we are asked to find the minimum number of columns of

A

, taken in order, that can approximate the vector

b

within

\epsilon

. Show that this is a quasiconvex optimization problem.