Convex Optimization · Problem 7.2

Geometric problems — Boyd & Vandenberghe

Mathematics — Optimization · ml-estimation-linf-norm-approximation

Problem

ML estimation and

\ell_\infty

-norm approximation. We consider the linear measurement model

y = Ax + v

of page 352, with a uniform noise distribution of the form

p(z) = \begin{cases} 1/(2\alpha) & |z| \leq \alpha \\ 0 & |z| > \alpha. \end{cases}

As mentioned in example 7.1, page 352, any

x

that satisfies

\|Ax - y\|_\infty \leq \alpha

is a ML estimate. Now assume that the parameter

\alpha

is not known, and we wish to estimate

\alpha

, along with the parameters

x

. Show that the ML estimates of

x

and

\alpha

are found by solving the

\ell_\infty

-norm approximation problem

\text{minimize} \quad \|Ax - y\|_\infty,

where

a_i^T

are the rows of

A