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.
 A: $\newcommand{\1}{\mathbf 1}\newcommand{\ep}{\varepsilon}\newcommand{\tr}{\operatorname{tr}}$The min-max value is $\sqrt n$.
Indeed, take any real $n\times n$ matrix $H$ with $|\det H|=1$. By the singular value decomposition,
\begin{equation}
    H=U^TDV,  
\end{equation}
where $U$ and $V$ are some orthogonal matrices and $D$ is the diagonal matrix with diagonal entries $d_1,\dots,d_n$ such that $d_1\cdots d_n=1$. Then
\begin{equation}
    \max_{\|x\|_2\le1}\|Hx\|_1=\max_{\|z\|_2\le1}\|U^TDz\|_1. 
\end{equation}
So,
\begin{equation}
\begin{aligned}
    &\min_{H\colon\,|\det H|=1}\max_{\|x\|_2\le1}\|Hx\|_1 \\ 
    &=\min_{U,D}\max_{\|z\|_2\le1}\,\max_{\ep\in\{-1,1\}^n}\sum_{i=1}^n e_i^T D_\ep U^TDz \\ 
    &=\min_{U,D}\max_{\ep\in\{-1,1\}^n}\,\max_{\|z\|_2\le1}\,\sum_{i=1}^n e_i^T D_\ep U^TDz \\ 
    &=\min_{U,D}\max_{\ep\in\{-1,1\}^n}\,\|DUD_\ep\1\|_2, 
\end{aligned}   
\end{equation}
where (i) $\min_{U,D}$ denotes the minimum over all orthogonal matrices $U$ and all diagonal matrices $D$ with diagonal entries $d_1,\dots,d_n$ such that $d_1\cdots d_n=1$; (ii) the $e_i$'s are the standard basis vectors; (iii)  $\ep:=(\ep_1,\dots,\ep_n)\in\{-1,1\}^n$ and $D_\ep$ is the diagonal matrix with diagonal entries $\ep_1,\dots,\ep_n$; and (iv) $\1:=\sum_{i=1}^n e_i$.
Now the crucial point: considering $\ep$ as a random point uniformly distributed on $\{-1,1\}^n$, we get the expected value of $E\|DUD_\ep\1\|_2^2$:
\begin{equation}
E\|DUD_\ep\1\|_2^2=\1^T ED_\ep U^T D^2 U D_\ep \1   
=\tr U^T D^2 U=\tr D^2=\sum_{i=1}^n d_i^2\ge n,
\end{equation}
since $d_1\cdots d_n=1$. Hence,
\begin{equation}
    \max_{\ep\in\{-1,1\}^n}\,\|DUD_\ep\1\|\ge 
E\|DUD_\ep\1\|_2\ge\sqrt n. 
\end{equation}
So,
\begin{equation}
    \min_{H\colon\,|\det H|=1}\max_{\|x\|_2\le1}\|Hx\|_1\ge\sqrt n.
\end{equation}
On the other hand,
\begin{equation}
    \min_{H\colon\,|\det H|=1}\max_{\|x\|_2\le1}\|Hx\|_1\le
\max_{\|x\|_2\le1}\|x\|_1=\sqrt n.
\end{equation}
Thus,
\begin{equation}
    \min_{H\colon\,|\det H|=1}\max_{\|x\|_2\le1}\|Hx\|_1=\sqrt n,
\end{equation}
as claimed.
