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.



How to solve this minimax matrix optimization problem?
$\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.


