4
$\begingroup$

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.

$\endgroup$

1 Answer 1

6
$\begingroup$

$\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.

$\endgroup$
2
  • $\begingroup$ Thank you for your answer. Is there any ituition or motivation for the above probabilistic method of deriving the upperbound? $\endgroup$
    – RyanChan
    Commented Nov 25, 2021 at 13:18
  • 1
    $\begingroup$ @RyanChen : This is a standard trick: If you want to show that $\|f\|_\infty\ge c$, it is enough to show that $\|f\|_2\ge c$, provided that the corresponding measure is a probability one. $\endgroup$ Commented Nov 25, 2021 at 17:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .