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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.