Skip to main content
2 of 2
typo in title
Jukka Kohonen
  • 4.2k
  • 2
  • 21
  • 49

How to solve this minimax matrix optimization problem?

Recently, I want to know how well can a $\ell_1$ ball be approximated by the image of a $\ell_2$ ball under a linear transform. I formulate this problem as the following optimization problem.

\begin{aligned} &\min_{\mathbb{H}\in \mathcal{M}_{n}} \max_{\left\| \mathbf{x}\right\|_2 \le 1} &&\left\|\mathbb{H}\mathbf{x} \right\|_1 \\ &\quad\quad\text{s.t.} &&|\det(\mathbb{H})|=1 \end{aligned} where $\mathbf{x}\in \mathbb{R}^n$ and $\mathcal{M}_{n}$ denotes the set of $n\times n$ square matrices in $\mathbb{R}$.

Asymptotic analysis (in terms of $n \to \infty$) and numerical algorithms are also appreciated.

RyanChan
  • 550
  • 2
  • 10