I'm interested in

$$\sup_{x, y} \left\| A x + B y\right\|$$ subject to $$\left\|x\right\| = \left\|y\right\| = 1$$

where $A$, $B$ and $x$, $y$ are real matrices and vectors, respectively, of compatible sizes, and the norms are Euclidean. (Generalizations to more than two terms are also interesting)

Does this problem have a name in the literature? (If not, does it reduce to a well-known one?)


Note that this is a stronger constraint than $\left\|\begin{bmatrix}x\\y\end{bmatrix}\right\| = \sqrt 2$

  • Do you mean Frobenius norm or spectral norm ? – loup blanc Oct 12 at 8:49
  • 1
    @loupblanc The norms are Euclidean (applied to vectors). I tagged "operator-norms", because the problem looks similar (a generalization of induced matrix norm) – Max Oct 12 at 12:02
  • @Max Interesting question which reminds me of eigenvalue of perturbed matrices. See link – BigM yesterday

The sets $\{Ax : \|x\|=1\}$ and $\{By : \|y\|=1\}$ are ellipsoids. Hence the set $\{Ax+By : \|x\|=\|y\|=1\}$ is the Minkowski sum of two ellipsoids. Googling for these terms returned this paper which may be interesting to you (although browsing through it I did not find an immediate solution to your problem).

Yan, Yan; Chirikjian, Gregory S., Closed-form characterization of the Minkowski sum and difference of two ellipsoids, Geom. Dedicata 177, 103-128 (2015). ZBL1321.65033.

I do not know if there is a name for this problem. However, we can view this in terms of the usual operator norm.

Given $A \in \mathrm{Mat}_{k \times n}(\mathbb{R}), B \in \mathrm{Mat}_{k \times m}(\mathbb{R})$, consider for $x \in \mathbb{R}^n, y \in \mathbb{R}^m$:

\begin{align*} \underset{\substack{ \lvert \lvert x \rvert \rvert = 1 \\ \lvert \lvert y \rvert \rvert = 1}}{\mathrm{sup}} \lvert \lvert Ax + By \rvert \rvert &= \underset{\substack{ \lvert \lvert x \rvert \rvert \leq 1 \\ \lvert \lvert y \rvert \rvert \leq 1}}{\mathrm{sup}} \lvert \lvert Ax + By \rvert \rvert \\ &= \underset{\substack{ \lvert \lvert x \rvert \rvert \leq 1 \\ \lvert \lvert y \rvert \rvert \leq 1}}{\mathrm{sup}} \, \left \lvert \left \lvert \begin{pmatrix}A & B\end{pmatrix} \begin{pmatrix}x \\ y\end{pmatrix} \right \rvert \right\rvert \\ &= \underset{\left \lvert \left \lvert \begin{pmatrix} x \\ y \end{pmatrix} \right \rvert \right \rvert_\infty = 1}{\mathrm{sup}} \left \lvert \left \lvert \begin{pmatrix}A & B\end{pmatrix} \begin{pmatrix}x \\ y\end{pmatrix} \right \rvert \right\rvert, \end{align*} where $\left \lvert \left \lvert \begin{pmatrix} x \\ y \end{pmatrix} \right \rvert \right \rvert_\infty := \max(\lvert \lvert x \rvert \rvert, \lvert \lvert y \rvert \rvert)$ is the supremum norm from viewing $\mathbb{R}^{n+m}$ as the product $\mathbb{R}^n \times \mathbb{R}^m$. Observe then that the last expression is $\lvert \lvert (\begin{smallmatrix}A & B\end{smallmatrix}) \rvert \rvert_{\mathrm{op}}$, where $\lvert \lvert \cdot \rvert \rvert_{\mathrm{op}}$ is the operator norm induced from $\lvert \lvert \cdot \rvert \rvert_\infty$ on $\mathbb{R}^{n+m}$ and $\lvert \lvert \cdot \rvert \rvert$ on $\mathbb{R}^k$.

Also note that this characterization $\underset{\lvert \lvert x_i \rvert \rvert = 1}{\mathrm{sup}} \, \lvert \lvert \sum_i A_i x_i \rvert \rvert = \lvert \lvert (\begin{smallmatrix} A_1 & \ldots & A_\ell \end{smallmatrix}) \rvert \rvert_{\mathrm{op}}$ works for any finite sum.

  • 1
    The usual (Euclidean-induced) norm reduces to singular value decomposition. Are there similarly useful insights one can draw from the fact that this is an induced-norm problem (for a rather esoteric norm)? (BTW I don't think the 0s are needed in the block matrices) – Max 2 days ago
  • The supremum norm isn't so esoteric! If both vector norms being considered are supremum norms, then the operator norm is just the row-sum maximum $\max_{i} \sum_{j = 1}^k a_{i,j}$. However, since we have both the Euclidean norm and the supremum norm, I'm not sure what the resulting operator norm should be. (You're right about the zeroes; I've just edited the expression in the answer to remove them. I must have had square matrices in my mind when writing that!) – robinz16 yesterday
  • Sorry, the last comment should have $\max_i \sum_{j=1}^k \lvert a_{i, j} \rvert$ for the row-sum norm. – robinz16 yesterday

Longer than a comment:(A complete answer is essentially given in the link provided by F. poloni)

$2\times2$ matrices: Let say A and B are given by
\begin{pmatrix} a & b \\ c & d \end{pmatrix} \begin{pmatrix} a' & b' \\ c' & d' \end{pmatrix} respectively and $(x,y)=(\cos\theta,\sin\theta)$ and $(x',y')=(\cos\phi,\sin\phi)$. You would like to maximize the following

$$\|A(x,y)+B(x',y')\|^2=(a\cos\theta+b\sin\theta+a'\cos\phi+b'\sin\phi)^2+(c\cos\theta+d\sin\theta+c'\cos\phi+d'\sin\phi)^2.$$

Using $-\sqrt{a^2+b^2}\leq a\cos\theta+b\sin\theta\leq\sqrt{a^2+b^2}$ and so on we obtain $$\|A(x,y)+B(x',y')\|^2\leq\big( \sqrt{a^2+b^2}+\sqrt{a'^2+b'^2}\Big)^2+ \Big(\sqrt{c^2+d^2}+\sqrt{c'^2+d'^2}\Big)^2=(a^2+b^2+c^2+d^2)+(a'^2+b'^2+c'^2+d'^2)+2(\sqrt{a^2+b^2},\sqrt{c^2+d^2})\cdot(\sqrt{a'^2+b'^2},\sqrt{c'^2+d'^2}) $$ And this upper bound is attained.

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.