Maximum radius of an image set after linear transformation

69 Views Asked by At

Let $A \in \mathbb{R}^n$ be an invertible matrix and let $K_1 \subset \mathbb{R}^n$ be some convex and compact set containing the origin. Let $K_2$ be a linear transformation of $K_1$ \begin{align} K_2= \{ x: x= A y, y\in K_1 \}. \end{align}

Let $r$ be the maximum radius of $K_2$ that is \begin{align} r= \max_{ x \in K_2} \|x\|. \end{align}

Can we find an expression for $r$ in terms of set $K_1$ and matrix $A$?

For example, can this be done when $K_1$ is an $n$-dimensional ball or an $n$-dimensional rectangle.

1

There are 1 best solutions below

2
On

I think what you mean is some kind of simplified expression for the radius, rather than just $\sup_{x\in K} \| Ax \|$ or something. I'm not sure this is possible in general, only specific cases. Mainly we can get bounds.

Say $K_1$ is a ball, then

\begin{align} \sup_{x\in K} \| Ax \| &= \|A\|\text{rad}(K_1) \end{align}

by definition. However in general, I think we only have a bound:

\begin{align} \sup_{x\in K_1} \| Ax \| &\leq \|A\|\text{rad}(K_1) \end{align}

However, if $\text{span}(K_1)$ is a strict subspace of $\mathbb{R}^N$, then we have:

\begin{align} \sup_{x\in K_1} \| Ax \| &\leq \|A_{\text{span}(K_1)}\|\text{rad}(K_1) \end{align}

where $\|A_{\text{span}(K_1)}\|$ is the matrix norm of $A$ restricted to $\text{span}(K_1)$.

Say that $K_1$ is a box. There is an expression -- not sure how useful it is. Let

\begin{align} K_1 &= \Pi_{i=1}^N[-a_i,b_i] \end{align}

then

\begin{align} \sup_{x\in K_1} \| Ax \| &= \max_{\lambda_i\in\{-a_i,b_i\}}\sum^N_{i=1}(\lambda_i A(e_i)) \end{align}

where $e_i$ is the standard basis. Essentially the optimal choice for each coordinate is either going to be $-a_i$ or $b_i$. This is because convex functions are maximized on the boundary of their domain. The norm squared $\|Ax\|^2$ is going to be convex in each coordinate. Hence you only have to check a finite number of combinations.