# $\sup \left\| A x + B y\right\|$ subject to $\left\|x\right\| = \left\|y\right\| = 1$

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
• @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.

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